以走迷宫为例,就是一群人一起出发,然后遇到叉路口就分开走,只要有一个人走出就把所有人带走
下面的宽度优先搜索过程BFS假定输入图G=(V,E)采用邻接表表示,对于图中的每个顶点还采用了几种附加的数据结构,对每个顶点u∈V,其色彩存储于变量color[u]中,结点u的父母存于变量n[u]中.如果u没有父母(例如u=s或u还没有被检索到),则 n[u]=NIL,由算法算出的源点s和顶点u之间的距离存于变量d[u]中,算法中使用了一个先进先出队列Q来存放灰色节点集合.其中head[Q]表示队列Q的队头元素,Enqueue(Q,v)表示将元素v入队, Dequeue(Q)表示对头元素出队；Adj[u]表示图中和u相邻的节点集合.
BFS(G,S)
foreachu∈V[G]-{s}
do
color[u]←White;
d[u]←◆;
n[u]←NIL;
end;
color[s]←Gray;
d[s]←0;
n[s]←NIL;
Q←{s}
while(Q≠◆)
u←head[Q];
for each v∈Adj[u]
if(color[v]=White)
then
color[v]←Gray;
d[v]←d[u]◆1;
n[v]←u;
Enqueue(Q,v);
Dequeue(Q);
color[u]←Black;
图1 BFS在一个无向图上的执行过程
在单词关系图建立完成以后,需要继续在图中寻找词梯问题的最短序列,需要用到"宽度优先搜索Breadth First Search"算法对单词关系图进行搜索
BFS是搜索图的最简单算法之一,也是其它一些重要的图算法的基础给定图G,以及开始搜索的起始顶点s.BFS搜索所有从s可到达顶点的边而且在达到更远的距离k◆1的顶点之前,BFS会找到全部距离为k的顶点可以想象为以s为根,构建一棵树的过程,从顶部向下逐步增加层次宽度优先搜索能保证在增加层次之前,添加了所有兄弟节点到树中.
BFS算法过程
①距离distance：从起始顶点到此顶点路径长度；
还需要用一个队列Queue来对已发现的顶点进行排列
决定下一个要探索的顶点（队首顶点）
从起始顶点s开始,作为刚发现的顶点,标注为灰色,距离为0,前驱为None,加入队列,此时此刻呢是个循环迭代过程：
从队首取出一个顶点作为当前顶点；遍历当前顶点的邻接顶点,如果是尚未发现的白
色顶点,则将其颜色改为灰色（已发现）,距离增加1,前驱顶点为当前顶点,加入到队列中遍历完成后,将当前顶点设置为黑色（已探索过）,循环回到步骤1的队首取当前顶点
算法分析
BFS算法主体是两个循环的嵌套
while循环对每个顶点访问一次,所以是O(|V|),而嵌套在while中的for,由于每条边只有在其起始顶点u出队的时候才会被检查一次,而每个顶点最多出队1次,所以边最多被检查1次,一共是O(|E|)综合起来BFS的时间复杂度为O(V◆E)
词梯问题还包括两个部分算法
以上就是土嘎嘎小编为大家整理的宽度优先搜索代码java相关主题介绍,如果您觉得小编更新的文章只要能对粉丝们有用,就是我们最大的鼓励和动力,不要忘记讲本站分享给您身边的朋友哦！！