图论04-【无权无向】-图的广度优先遍历

本文主要是介绍图论04-【无权无向】-图的广度优先遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

1. 代码仓库
2. 广度优先遍历图解
3.主要代码
4. 完整代码

1. 代码仓库

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

2. 广度优先遍历图解

在这里插入图片描述

3.主要代码

原点入队列
原点出队列的同时，将与其相邻的顶点全部入队列
下一个顶点出队列
出队列的同时，将与其相邻的顶点全部入队列

private void bfs(int s){ //使用循环Queue<Integer> 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;}}
}

复杂度：O（V+E）

4. 完整代码

输入文件

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<>(); // 存储遍历顺序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){ //使用循环Queue<Integer> 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 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());}
}