宽度优先搜索算法(pascal)

以走迷宫为例,就是一群人一起出发,然后遇到叉路口就分开走,只要有一个人走出就把所有人带走

目前创新互联已为上千多家的企业提供了网站建设、域名、雅安服务器托管、网站托管运营、企业网站设计、南明网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

宽度优先搜索的伪代码实现

下面的宽度优先搜索过程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弹出队列并置成黑色。

7.3实现宽度优先搜索

在单词关系图建立完成以后，需要继续在图中寻找词梯问题的最短序列，需要用到“宽度优先搜索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)