全国送花网站,莆田市的网站建设公司,免费数据库网站空间,WordPress页面生成时间文章目录 1. 代码仓库2. 广度优先遍历图解3.主要代码4. 完整代码 1. 代码仓库 https://github.com/Chufeng-Jiang/Graph-Theory 2. 广度优先遍历图解 3.主要代码 原点入队列原点出队列的同时#xff0c;将与其相邻的顶点全部入队列下一个顶点出队列出队列的同时#xff0c;将… 文章目录 1. 代码仓库2. 广度优先遍历图解3.主要代码4. 完整代码 1. 代码仓库 https://github.com/Chufeng-Jiang/Graph-Theory 2. 广度优先遍历图解 3.主要代码 原点入队列原点出队列的同时将与其相邻的顶点全部入队列下一个顶点出队列出队列的同时将与其相邻的顶点全部入队列 private void bfs(int s){ //使用循环QueueInteger queue new LinkedList();queue.add(s);visited[s] true;while(!queue.isEmpty()){ //只要不是空就不停地出队int v queue.remove(); // v记录队首元素 | 相邻顶点入队后重新进入while循环队首出队order.add(v); //添加到order数组中order数组装的是按照BFS顺序遍历的顶点for(int w: G.adj(v))if(!visited[w]){queue.add(w); // 相邻的顶点入队列visited[w] true;}}
}复杂度OVE
4. 完整代码
输入文件
7 9
0 1
0 3
1 2
1 6
2 3
2 5
3 4
4 5
5 6package 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 ArrayListInteger order new ArrayList(); // 存储遍历顺序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){ //使用循环QueueInteger queue new LinkedList();queue.add(s);visited[s] true;while(!queue.isEmpty()){ //只要不是空就不停地出队int v queue.remove(); // v记录队首元素 | 相邻顶点入队后重新进入while循环队首出队order.add(v); //添加到order数组中order数组装的是按照BFS顺序遍历的顶点for(int w: G.adj(v))if(!visited[w]){queue.add(w); // 相邻的顶点入队列visited[w] true;}}}//取出遍历顺序public IterableInteger 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());}
}
