1. 代碼倉庫

https://github.com/Chufeng-Jiang/Graph-Theory

2. 廣度優(yōu)先遍歷圖解

3.主要代碼

1. 原點(diǎn)入隊(duì)列
2. 原點(diǎn)出隊(duì)列的同時(shí)，將與其相鄰的頂點(diǎn)全部入隊(duì)列
3. 下一個(gè)頂點(diǎn)出隊(duì)列
4. 出隊(duì)列的同時(shí)，將與其相鄰的頂點(diǎn)全部入隊(duì)列

private void bfs(int s){ //使用循環(huán)Queue<Integer> queue = new LinkedList<>();queue.add(s);visited[s] = true;while(!queue.isEmpty()){ //只要不是空就不停地出隊(duì)int v = queue.remove(); // v記錄隊(duì)首元素 | 相鄰頂點(diǎn)入隊(duì)后，重新進(jìn)入while循環(huán)，隊(duì)首出隊(duì)order.add(v); //添加到order數(shù)組中，order數(shù)組裝的是按照BFS順序遍歷的頂點(diǎn)for(int w: G.adj(v))if(!visited[w]){queue.add(w); // 相鄰的頂點(diǎn)入隊(duì)列visited[w] = true;}}
}

復(fù)雜度：O（V+E）

4. 完整代碼

輸入文件

7 9
0 1
0 3
1 2
1 6
2 3
2 5
3 4
4 5
5 6

package Chapt04_BFS_Path._0401_Graph_BFS_Queue;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;public class GraphBFS {private Graph G;private boolean[] visited;private ArrayList<Integer> order = new ArrayList<>(); // 存儲(chǔ)遍歷順序public GraphBFS(Graph G){this.G = G;visited = new boolean[G.V()];//遍歷所有連通分量for(int v = 0; v < G.V(); v ++)if(!visited[v])bfs(v);}private void bfs(int s){ //使用循環(huán)Queue<Integer> queue = new LinkedList<>();queue.add(s);visited[s] = true;while(!queue.isEmpty()){ //只要不是空就不停地出隊(duì)int v = queue.remove(); // v記錄隊(duì)首元素 | 相鄰頂點(diǎn)入隊(duì)后，重新進(jìn)入while循環(huán)，隊(duì)首出隊(duì)order.add(v); //添加到order數(shù)組中，order數(shù)組裝的是按照BFS順序遍歷的頂點(diǎn)for(int w: G.adj(v))if(!visited[w]){queue.add(w); // 相鄰的頂點(diǎn)入隊(duì)列visited[w] = true;}}}//取出遍歷順序public Iterable<Integer> order(){return order;}public static void main(String[] args){Graph g = new Graph("g1.txt");GraphBFS graphBFS = new GraphBFS(g);System.out.println("BFS Order : " + graphBFS.order());}
}