package com.rao.graph; import java.util.LinkedList; /**
* @author Srao
* @className BFS_DFS
* @date 2019/12/10 19:16
* @package com.rao.graph
* @Description 深度优先搜索 和 广度优先搜索
*/
public class BFS_DFS { /**
* 图的顶点
*/
private static class Vertex{
int data;
Vertex(int data){
this.data = data;
}
} /**
* 图（邻接表）
*/
private static class Graph{
private int size;
private Vertex[] vertices;
//存放每个顶点的链表
private LinkedList<Integer>[] adj; Graph(int size){
this.size = size;
vertices = new Vertex[size];
adj = new LinkedList[size];
for (int i = ; i < size; i++) {
vertices[i] = new Vertex(i);
adj[i] = new LinkedList();
}
}
} /**
* DFS（深度优先搜索）
* @param graph：图
* @param start：起始访问点
* @param visited：是否被访问过,true表示被访问过
*/
public static void dfs(Graph graph, int start, boolean[] visited){
System.out.println(graph.vertices[start].data);
visited[start] = true;
for (int index : graph.adj[start]){
if (!visited[index]){
dfs(graph, index, visited);
}
}
} /**
* BFS（广度优先搜索）
* @param graph：图
* @param start：起始访问点
* @param visited：是否被访问过,true表示被访问过
* @param queue：队列里面存放被遍历过的元素
*/
public static void bfs(Graph graph, int start, boolean[] visited, LinkedList<Integer> queue){
//队列的插入操作
queue.offer(start);
while (!queue.isEmpty()){
int front = queue.poll();
if (visited[front]){
continue;
}
System.out.println(graph.vertices[front].data);
visited[front] = true;
for (int index : graph.adj[front]){
queue.offer(index);
}
}
} public static void main(String[] args) {
Graph graph = new Graph(); graph.adj[].add();
graph.adj[].add();
graph.adj[].add(); graph.adj[].add();
graph.adj[].add();
graph.adj[].add(); graph.adj[].add(); graph.adj[].add();
graph.adj[].add();
graph.adj[].add();
graph.adj[].add(); graph.adj[].add();
graph.adj[].add();
graph.adj[].add(); graph.adj[].add();
graph.adj[].add(); System.out.println("图的深度优先遍历：");
dfs(graph, , new boolean[graph.size]); System.out.println("图的广度优先遍历：");
bfs(graph, , new boolean[graph.size], new LinkedList<>());
} }
输出结果如下：
图的深度优先遍历： 图的广度优先遍历：