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

接下来两篇文章将深入探索图搜索算法的方方面面，不再局限于做出简单的图搜索算法，而是站在图搜索算法上深入思考。本问将证明广度优先搜索求最短路的正确性。而下一篇文章将使用深度优先搜索实现强连通分量算法的正确性。

算法描述

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

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

BFS(G, s)for v in G.V:v.color = whitev.d = Infv.Π = nils.color = grays.d = 0s.Π = nilque = emptyque.push(s)while !que.empty()u = que.pop()for v in G.adj[v]:if v.color == white:v.color = grayv.d = u.d + 1v.Π = uque.push(v)u.color = black

复杂度分析

算法主要在执行que.pop和que.push操作。由于每个节点只会入队，出队一次，所以队列操作的复杂度为$O(V)$。此外，对每个节点还遍历了其临界链表。对无向图邻接表会遍历两次。将其看成双向图后，对临界链表遍历的总操作的复杂度为$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)>\delta (s,u)+1$，那么s到v的路径完全可以选择先到$u$，再到$v$得到一个更小值，这与$\delta (s,v)$的定义矛盾。

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

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

				v.color = grayv.d = u.d + 1v.Π = uque.push(v)

假设，此时$u.d$此时满足$u.d\ge \delta (s,u)$,再根据最短路径的性质，$\delta (s,v)\le \delta (s,u)+1$，可以得到，
$$v.d=u.d+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$。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：$v.d=\delta (s,v)$，并且v的最短路径为$v.\pi$的最短路径加边$<v.\pi ,v>$

  使用反证法：假设算法结束后，有一些$v.d$ 不满足 $v.d\ne \delta (s,v)$。我们精心挑选一个$v$,他是所有不满足 $v.d\ne \delta (s,v)$的节点中， $\delta (s,v)$最小的一个。根据定理1，可知$v.d>\delta (s,v)$。假设节点$u$为$s$到$v$的最短路径上，$v$的直接前驱节点。因此 $\delta (s,v)=\delta (s,u)+1$，即$\delta (s,u)<\delta (s,v)$，因为$v$是$v.d\ne \delta (s,u)$的最小节点，因此 $u.d=\delta (s,u)$。于是有不等式
  $$v.d>\delta (s,v)=\delta (s,u)+1=u.d+1$$
  考虑 $u$ 从队列 $Q$中取出的时间。此时 $v$ 可以是任何颜色。

  • 如果$v$是白色，那么本轮循环会将v.d设置为u.d + 1，与$v.d>\delta (s,v)=\delta (s,u)+1$矛盾。
  • 如果$v$是灰色，那么$v$此时在队列中，根据定理2，$v.d\le u.d+1$，依然与上式矛盾
  • 如果$v$是黑色，那么$v$此时已经不在队列中，根据推论2.1，$v.d\le u.d$，仍然矛盾。

  因此算法结束后$v.d=\delta (s,v)$。根据算法伪代码，如果$v.\pi =u$,则必有$v.d=u.d+1$，即$\delta (s,v)=\delta (s,u)+1$，因此，$v$的最短路径为 $u$的最短路径加边$<v.\pi ,v>$，证毕。

广度优先树

定义：考虑图G的一个子图$G_{\pi }$。如果$G_{\pi }$的节点由s节点可达的所有节点构成。且对每一个$G_{\pi }$中的节点v，$G_{\pi }$中都有唯一一条s到节点v的简单路径，并且该简短路径是原图G中的最短路径，则$G_{\pi }$是一个广度优先树。
显然，以广度优先搜索生成的 $v.\pi$为边，生成的图$G_{\pi }$是广度优先树。