22.2 广度优先搜索

广度优先搜索

发现

前驱 父节点

BFS(G,s)

for each vertx u ∈ G.V - {s}
	u.color = WHITE
    u.d = ∞
    u.Π = NIL
s.color = GRAY
s.d = 0
s.Π = NIL
Q = Ø
ENQUEUE(Q,s)
while Q ≠ Ø
	u = DEQUEUE(Q)
    for each v ∈ G.Adj[u]
    	if v.color == WHITE
        	v.color = GRAY
            v.d = u.d + 1
            v.Π = u
            ENQUEUE(Q,v)
    u. color = BLACK

图 22-3 BFS在一个样本图上的推进过程

分析

最短路径

最短路径距离 最短路径

引理 22.1

证明

引理 22.2

证明

引理 22.3 在任意时刻，队列里面最多包含两个不同的d值

证明

推论 22.4 在结点加入到队列时，d值随时间推移单调增长

证明

证明根据引理22.3，以及每个结点获得的d值都是有限的且BFS过程中最多只取一次d值的性质，可以立即得到推论22.4。

定理 22.5 广度优先搜索算法能够正确计算出最短路径距离

证明

前驱子图

广度优先树 树边

引理 22.6 BFS过程所生成的前驱子图是一棵广度优先树

证明

PRINT-PATH(G,s,v)

下面的伪代码将打印出从源结点s到结点v的一条最短路径上的所有结点，这里假定BFS已经计算出一棵广度优先树。

if v == s
	print s
else if v.Π == NIL
	print "no path from" s "to" v "exists"
else PRINT-PATH(G,s,v,Π)
	print v

因为每次递归调用时的路径都比前一次调用中的路径少一个结点，所以该过程的运行时间是关于所输出路径上顶点数的一个线性函数。

练习

22.2-6

给出一个有向图G=（V，E）的例子，一个源顶点s∈V、 和一组树边使得对于每个顶点v∈V、 图中从s到V的唯一简单路径是G中的最短路径，但是在G上运行BFS无法生成边集，无论顶点在每个邻接列表中的顺序如何。

Solution

设G为第一幅图中所示的图，是第二张图片中显示的图形，s是源顶点。

我们可以看到，在G上运行BFS永远不会产生Eπ。

• 如果Adj[s]中y在v之前。我们先把y排在v前面，所以u.π和x.π都是y。然而，情况并非如此。

• 如果v在Adj[s]中位于y之前。我们先把v排在y前面，所以u.π和x.π都是v，这同样不是真的。

然而，中从s到任意顶点的唯一简单路径是G中的最短路径。