甜橘子，专注成都网站制作网站设计与营销型网站建设与优化
QQ :532337155
电话：028-86922220
以走迷宫为例,就是一群人一起出发,然后遇到叉路口就分开走,只要有一个人走出就把所有人带走
目前创新互联已为上千多家的企业提供了网站建设、域名、雅安服务器托管、网站托管运营、企业网站设计、南明网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。
下面的宽度优先搜索过程BFS假定输入图G=(V,E)采用邻接表表示，对于图中的每个顶点还采用了几种附加的数据结构，对每个顶点u∈V，其色彩存储于变量color[u]中，结点u的父母存于变量π[u]中。如果u没有父母(例如u=s或u还没有被检索到)，则 π[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]←∞;
π[u]←NIL;
end;
color[s]←Gray;
d[s]←0;
π[s]←NIL;
Q←{s}
while(Q≠φ)
do
u←head[Q];
for each v∈Adj[u]
do
if(color[v]=White)
then
color[v]←Gray;
d[v]←d[u]+1;
π[v]←u;
Enqueue(Q,v);
end;
Dequeue(Q);
color[u]←Black;
end;
end;
end;
图1展示了用BFS在例图上的搜索过程。黑色边是由BFS产生的树 枝。每个节点u内的值为d[u]，图中所示的队列Q是第9-18行while循环中每次迭代起始时的队列。队列中每个结点下面是该结点与源结点的距离。
图1 BFS在一个无向图上的执行过程
过程BFS按如下方式执行，第1-4行置每个结点为白色，置d[u]为无穷大，每个结点的父母置为NIL，第5行置源结点S为灰色，即意味着过程开始时源结点已被发现。第6行初始化d[s]为0，第7行置源结点的父母结点为NIL，第8行初始化队列0，使其仅含源结点s，以后Q队列中仅包含灰色结点的集合。
程序的主循环在9-18行中，只要队列Q中还有灰色结点，即那些已被发现但还没有完全搜索其邻接表的结点，循环将一直进行下去。第10行确定队列头的灰色结点为u。第11-16行的循环考察u的邻接表中的每一个顶点v。如果v是白色结点，那么该结点还没有被发现过，算法通过执行第13-16行发现该结点。首先它被置为灰色，距离d[v]置为d[u]+1，而后u被记为该节点的父母，最后它被放在队列Q的队尾。当结点u的邻接表中的所有结点都被检索后，第17 -18行使u弹出队列并置成黑色。
在单词关系图建立完成以后，需要继续在图中寻找词梯问题的最短序列，需要用到“宽度优先搜索Breadth First Search”算法对单词关系图进行搜索
BFS是搜索图的最简单算法之一，也是其它一些重要的图算法的基础给定图G，以及开始搜索的起始顶点s。BFS搜索所有从s可到达顶点的边而且在达到更远的距离k+1的顶点之前，BFS会找到全部距离为k的顶点可以想象为以s为根，构建一棵树的过程，从顶部向下逐步增加层次宽度优先搜索能保证在增加层次之前，添加了所有兄弟节点到树中。
BFS算法过程
❖为了跟踪顶点的加入过程，并避免重复顶点，要为顶点增加3个属性
1.距离distance：从起始顶点到此顶点路径长度；
2.前驱顶点predecessor：可反向追溯到起点；
3.颜色color：标识了此顶点是尚未发现（白色）、已经发现（灰色）、还是已经完成探索（黑色）
❖还需要用一个队列Queue来对已发现的顶点进行排列
决定下一个要探索的顶点（队首顶点）
❖从起始顶点s开始，作为刚发现的顶点，标注为灰色，距离为0，前驱为None，加入队列，接下来是个循环迭代过程：
从队首取出一个顶点作为当前顶点；遍历当前顶点的邻接顶点，如果是尚未发现的白
色顶点，则将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中遍历完成后，将当前顶点设置为黑色（已探索过），循环回到步骤1的队首取当前顶点
算法分析
BFS算法主体是两个循环的嵌套
while循环对每个顶点访问一次，所以是O(|V|)，而嵌套在while中的for，由于每条边只有在其起始顶点u出队的时候才会被检查一次，而每个顶点最多出队1次，所以边最多被检查1次，一共是O(|E|)综合起来BFS的时间复杂度为O(V+E)
词梯问题还包括两个部分算法
建立BFS树之后，回溯顶点到起始顶点的过程，最多为O(|V|)，创建单词关系图也需要时间，最多为O(|V|2)