一.概述
所谓的广度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点 ！
如图：
从0开始，想找与0相同通的所有顶点。
从0开始，搜索到6， 6有兄弟节点 2、1、5， 找完了兄弟节点再找子节点，找到6的邻接表，0搜过，找4的子节点
然后分别遍历2、1、5邻接表 …
回顾二叉树的层序遍历：
从上到下打印二叉树
- nodes先存root节点
- 开始循环： poll()弹出nodes的一个节点，其key放que中
- 将弹出节点的左、右子结点放入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()) {
//弹出一个待搜索的顶点curr
Integer 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;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89346.html
