无向图的广度优先搜索（BFS）

本文主要是介绍无向图的广度优先搜索（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一.概述

所谓的广度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点 ！

如图：

从0开始，想找与0相同通的所有顶点。
从0开始，搜索到6， 6有兄弟节点 2、1、5， 找完了兄弟节点再找子节点，找到6的邻接表，0搜过，找4的子节点
然后分别遍历2、1、5邻接表 …

回顾二叉树的层序遍历：
从上到下打印二叉树

1. nodes先存root节点
2. 开始循环： poll()弹出nodes的一个节点，其key放que中
3. 将弹出节点的左、右子结点放入nodes

二.概述

 public class graphBFS {private boolean[] marked;private int count;private Queue<Integer> nodes;   //辅助队列public graphBFS(graph g, int s) {this.count = 0;this.marked = new boolean[g.V()];nodes = new LinkedList<Integer>(); //辅助队列bfs(g, s);}public void bfs(graph g, int v) {    //使用广度优先搜索找出与v相通的顶点//标记当前顶点为已搜索marked[v] = true;//让v进入队列待搜索nodes.add(v);//通过循环，如果队列不为空则从队列中弹出一个待搜索的顶点进行搜索while (!nodes.isEmpty()) {//弹出一个待搜索的顶点currInteger curr= nodes.poll();//遍历curr顶点的邻接表for (Integer k : g.adj(curr)) {if (!marked(k)) {nodes.add(k); //将未搜索过的顶点添加至nodes队列marked[k]=true;   //对搜索过的节点进行标记}}}count++;}public boolean marked(int w) {return marked[w];  //返回数组中那个顶点是否与s顶点相同}public int count() {  //获取与顶点s相通的所有顶点的总数return count;}
}

这篇关于无向图的广度优先搜索（BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---