【算法证明六】深入理解广度优先搜索-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法证明六】深入理解广度优先搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

看了算法导论，才知道自己理解的深搜、广搜有多肤浅。

搜索算法非常直观，容易理解。只要简单学过其思想，都能在做算法题时自己写出来，或者模板背出来。但是这些是图论算法的基础，如果不把搜索算法的方方面面研究透彻，很难再学习更难得图论算法。接下来两篇文章将探索图搜索算法的方方面面。本问将证明广度优先搜索求最短路的正确性，证明过程中会导出广搜算法中得一些重要性质。而下一篇文章将使用深度优先搜索实现强连通分量算法的正确性。

算法描述

为了全面的考察广度优先搜索算法，我们将给节点加入一些状态。

$v . co l or ：初始状态为白色，被发现时改为灰色，其所有的邻接节点都被发现时，变为黑色。所以灰色代表被发现节点和未被发现的节点的边界。$
$v . d ：初始 s 节点到 v 节点的距离 (算法发现 v 时得到得 s 到 v 的简单路径的边的数量)$
$v.\pi: v的前驱节点，也就是说是从哪个节点发现v的，初始化为 nil$

BFS(G, s)
	for v in G.V:
		v.color = white
		v.d = Inf
		v.Π = nil
	s.color = gray
	s.d = 0
	s.Π = nil
	que = empty
	que.push(s)
	while !que.empty()
		u = que.pop()
		for v in G.adj[v]:
			if v.color == white:
				v.color = gray
				v.d = u.d + 1
				v.Π = u
				que.push(v)
		u.color = black

复杂度分析

算法使用聚合分析的思想。队列中存放的是节点v。根据代码，每个节点只会入队、出队一次，所以队列操作的复杂度为 $O (V)$ 。此外，算法 13 行对每个节点遍历了其临接边，但所有的边只会遍历一次。因此对边的遍历的总操作的复杂度为 $O (E)$ ，因此广度优先搜索的复杂度 $O (V + E)$

最短路径证明

为了证明方便，先定义s到v的最短距离为 $\delta(s,v)$ 时s到v的所有路径中最少的边数，相应的路径称为最短路径。对于最短路径 $\delta(s,v)$ 有一个重要的性质：给定 $G = (V, E)$ ，对于任意的边 $(u,v)\in E$ ，有 $\delta(s,v) \le \delta(s,u)+1$ 。该性质还是比较直观的：如果 $\delta(s,v) \gt \delta(s,u)+1$ ，那么s到v的路径完全可以选择先到 $u$ ，再到 $v$ 得到一个更小值，这与 $\delta(s,v)$ 的定义矛盾。

我们将通过夹逼的方式，证明算法运行结束后， $\delta(s,v)$ ，即先证明 $\ge \delta(s,v)$ ，再证明 $v.d\le\delta(s,v)$ 。此外，还将证明 $s$ 到 $v$ 的一条最短路径为 $s$ 到 $v.\pi$ 的最短路径加上边 $(v . p i, v)$ ，这个结论对恢复 $s$ 到 $v$ 最短路径很重要。

定理1：算法结束后， $v.d\ge \delta(s,v)$
证明：使用数学归纳法证明。先证明基本状态成立：算法开始时， $\delta(s,s)$ ，而对于其他节点， $v . d = I n f$ ，所以基本状态成立。考虑算法的14~18行

				v.color = gray
				v.d = u.d + 1
				v.Π = u
				que.push(v)

假设，此时 $u . d$ 此时满足 $u.d\ge \delta(s,u)$ ,再根据最短路径的性质， $\delta(s,v) \le \delta(s,u)+1$ ，可以得到，
$\ge \delta(s,u) + 1 \ge\delta(s,v)$ 。
此时v被图上了灰色，不会被再次入队，因此 $v . d$ 不会再次改变，因此基本状态与归纳均证毕，原命题成立。

定理2：对于算法运行中的队列中的节点 $v_1, ...,v_r>$ ，有 $v_r.d\le v_1.d+1$ ，且队列中的 $v_i.d$ 单调递增

仍然使用数学归纳法。开始时，队列中只有 $s$ ，命题成立。
当 $v_1$ 从队列中删除时，对原命题没有影响，原命题依然成立。
当 $v_{r+1}$ 入队时， $v_0$ 刚从队列中移除。此时 $v_{r+1}.d$ 被设置为 $v_{0}.d+1$ 。
- 由于 $v_r.d\le v_0.d + 1$ （上一轮的假设），所以 $v_{r}.d\le v_{r+1}.d$ ，单调性成立。
- 因为 $v_0.d +1 \le v_1.d +1$ (上一轮的单调性假设)，因此 $v_{r+1}.d \le v_1.d +1$ 。因此基本状态和归纳均成立，命题得证。
推论2.1：算法运行中，当 $v_i$ 在 $v_j$ 之前入队时，必有 $v_i.d\le v_r.d$ ，d 随着算法的运行单调递增的。

定理2已保证了这一点
定理3： $\delta(s,v)$ ，并且v的最短路径为 $v.\pi$ 的最短路径加边 $<v.\pi, v>$

使用反证法：假设算法结束后，有一些 $v . d$ 不满足 $\neq \delta(s,v)$ 。我们精心挑选一个 $v$ ,他是所有 $\neq \delta(s,v)$ 的节点中， $\delta(s,v)$ 最小的一个。根据定理1，可知 $\delta(s,v)$ 。假设节点 $u$ 为 $s$ 到 $v$ 的最短路径上， $v$ 的直接前驱节点。因此 $\delta(s,v)= \delta(s,u) + 1$ ，即 $\delta(s,u) \lt \delta(s,v)$ 。因为 $v$ 是 $v.d\neq \delta(s,u)$ 的最小节点，因此 $\delta(s,u)$ 。于是有不等式
$v.d\gt \delta(s,v) = \delta(s,u) + 1 = u.d + 1$
考虑 $u$ 从队列 $Q$ 中取出的时间。此时 $v$ 可以是任何颜色。
- 如果 $v$ 是白色，那么本轮循环会将v.d设置为u.d + 1，与 $v.d\gt \delta(s,v) = \delta(s,u) + 1$ 矛盾。
- 如果 $v$ 是灰色，那么 $v$ 此时在队列中，根据定理2， $\le u.d +1$ ，依然与上式矛盾
- 如果 $v$ 是黑色，那么 $v$ 此时已经不在队列中，根据推论2.1， $\le u.d$ ，仍然矛盾。
因此算法结束后 $\delta(s,v)$ 。根据算法伪代码，如果 $v.\pi=u$ ,则必有 $v . d = u . d + 1$ ，即 $\delta(s,v)= \delta(s,u) + 1$ ，因此， $v$ 的最短路径为 $u$ 的最短路径加边 $<v.\pi, v>$ ，证毕。

广度优先树

根据广度优先搜索算法的性质，算法结束后，可以通过每个节点的 $v.\pi$ 属性来恢复最短路径。事实上使用 $v.\pi$ 属性为边，加上其关联的节点，可以形成一个树形结构。称之为：广度优先树 $G.\pi$ 文章来源地址https://www.toymoban.com/news/detail-510478.html