Breadth-first search

Why so named

粗翻为“宽度优先搜索”，本质是搜索算法

（网上博客什么“广度优先遍历”也是绝了，遍历是traverse，岂不是BFT？）

按所谓的“广度优先遍历”的顺序其实就是接下来要讲到的BLACK顶点的出现顺序

为什么这么取名呢？

Breadth-first search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier

在边界的宽度上均匀扩展在已发现顶点和未发现顶点之间的边界

讲解

为了跟踪整个过程，我们约定好顶点有三种颜色表示：BLACK，GRAY，WHITE

WHITE表示还未发现的顶点，所以一开始所有顶点都是白的，之后会染成另外两种颜色

GRAY是中间色，表示已发现，但是它的邻接点还有白色的，实际上灰色代表着上面提到的边界

BLACK表示已发现，并且它的邻接点都已染灰或黑，没有白色的

为了记录路径，我们给每个顶点赋予一个属性表示前驱：$v.\pi$（无前驱记为NIL），除此之外还给顶点赋予颜色和距离：$v.color$和$v.d$，如果无法到达，距离记为$\infty$。实际上这些属性根据自己的想法可以用数组保存，不一定要赋予给顶点），

为了管理灰色顶点，用一个队列保存，第一个进来的灰色顶点第一个出去（实际上，队列中自始至终都只含有灰色节点）

伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
BFS(G,s)	//s is a source vertex
for each vertex 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)	//等价于front之后再pop
 for each v ∈ G.Adj[u]	//G.Adj[u]表示u的邻接边
  if v.color = WHITE
   then v.color ← GRAY
        v.d ← u.d+1
        v.π ← u
        ENQUEUE(Q,v)
 u.color ← BLACK			//所有邻接边均已考察，染黑

算法复杂度

实际上，每个顶点最多入队和出队一次，所以ENQUEUE和DEQUEUE的时间复杂度为$O(1)$，实际上这就是摊还开销，因此总的时间复杂度为$O(V)$,假设这里采用的是邻接表，那么邻接边共有$\Theta(E)$,所以总时间复杂度为$O(V+E)$

如果采用邻接矩阵，那么$\Theta(E)=\Theta(V^2)$，所以$T_n=O(V+V^2)$

最短路径证明

我们记$s$到$v$的最短路径为$\delta(s,v)$,我们将证明$v.d=\delta(s,v)$

Lemma 1

Let G=(V,E) be a directed or undirected graph,and let s $\in$ V be an arbinary vertex.Then,for any edge (u,v) $\in$ E,

​ $\delta(s,v) \le \delta (s,u) +1$

$Proof$

这个建议画图

  • 当u可到达时，到v的最短路径不可能比到u的最短路径加上(u,v)还长
  • 当u不可到达时，到u的最短路径为$\infty$，依然满足不等式

Lemma 2

Let G=(V,E) be a directed or undirected graph,and suppose that BFS is aon G from a given source vertex s $\in$ V.Then upon termination,for each vertex v $\in$ V,the value v.d computed by BFS satifies $v.d\ge \delta(s,v)$

$Proof$

我们对ENQUEUE进行数学归纳证明$v.d \ge \delta(s,v)$

  • basis：$s.d=\delta(s,s)=0,v.d=\infty \ge \delta(s,v)$，命题成立

  • inductive hypothesis：在$u$进行搜索时，白色顶点被发现，假设$u.d \ge \delta(s,u)$成立（相当于n=m)

  • inductive step：

    由16行得：

    $v.d=u.d+1 \ge \delta (s,u)+1 \ge \delta(s,v) $

对于$v$，ENQUEUE只有一次，在Q中不会改变其距离，因此在Q中$v.d$得以保持 $\blacksquare$

Lemma 3
Suppose that during the execution of BFS on a graph G=(V,E),the queue Q contains the vertices <$v_1,v_2,…,v_r$>,where $v_1$ is the head of Q and $v_r$ is the tail.Then,$v_r.d \le v_1.d+1$ and $v_i.d \le v_{i+1}.d$,for i=1,2,…,r-1

$Proof$

对队列ENQUEUE和DEQUEUE进行数学归纳：

  • basis：只包含源点s

  • inductive hypothesis：假设对于<$v_1,v_2,…,v_r$>命题成立，有$v_r.d \le v_1.d$,$v_i.d \le v_{i+1}.d$

  • inductive step：

    当$v_1$出队时，$v_2$成为新的head，$v_i.d \le v_{i+1}.d$即使去掉$v_1$依然保持，而$v_r.d \le v_1.d+1 \le v_2.d+1$

    当$v_{r+1}$入队时，假设$u$出队，$v_1$成为新的head，$v_{r+1}.d =u.d+1 \le v_1.d+1$，$v_r.d \le u.d+1 =v_{r+1}.d$

这样队列得ENQUEUE和DEQUEUE依次进行，依然保持该性质 $\blacksquare$

实际上，这里要证两个性质的维持，但是前一个性质只是辅助证明后一个性质，因为后一个性质揭示了队列中顶点的单调性，结合两个性质可以知道队列中最多有两种d($0 \le v_r.d -v_1.d \le 1$)，下面这个推论就是队列的单调性：

Corollary

Suppose that vertices $v_i$ and $v_j$ are enqueued during the execution of BFS,and that $v_i$ is enqueued before $v_j$.Then $v_i.d \le v_j.d$ at the time that $v_j$ is enqueued

$Proof$

由引理3可知：不论$v_i$比$v_j$多先入队，先入队的距离均小于等于后入队的距离

这个推论告诉我们随着新顶点入队，其距离呈现不严格单调增加

Theorem(Correctness of breadth-first search)

Let G=(V,E) be a directed or undirected graph,and suppose that BFS is run on G from a given source vertex s $\in$ V,that is reachable from the source s,and upon termination,$v.d=\delta(s,v)$ for all v $\in $ V.Moreover,for any vertex v $\ne$ s that is reachable from s,one of the shortest paths from s to v is a shortest path from s to v.$\pi$ followed by the edge (v.$\pi$,v)

$Proof$

我们可以用反证法证明该定理：由引理2得：$v.d \ge \delta(s,v)$，故假设$v.d > \delta(s,v)$

我们取u为s到v的最短路径上的最近前驱，那么$\delta(s,v)=\delta(s,u)+1$，

由$\delta(s,u) < \delta(s,v)$以及我们对$v$的选择，存在u满足$u.d=\delta(s,u)$

这样我们得到：$v.d > \delta(s,v)=\delta(s,u)+1=u.d+1 \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

我们根据$v$（第13行）的颜色进行分类讨论：

  • 白色：$v.d=u.d+1$与$(*)$矛盾
  • 灰色：存在顶点$w$在$u$之前就发现了$v$，所以$v.d=w.d+1$,而$w$先于$u$出队，那么由推论可知$w.d \le u.d$,所以$v.d=w.d+1 \le u.d+1$与$(*)$矛盾
  • 黑色：$v$已经出队，那么$v.d \le u.d$与$(*)$矛盾

综上，$v.d>\delta(s,v)$不可能，由引理2得：$v.d=\delta(s,v)$

对于$v.d=\delta(s,v)$，所有的v都是可到达的，假设$v$是不可到达的，其前驱为NIL，$v.d= \infty <\delta(s,v)$，与上述结论矛盾

$v.\pi =u,v.d=u.d+1$，存在一条从s到u经由(u,v)到达v的最短路径

证明思路

证明$v.d \ge \delta(s,v)$,反证$v.d >\delta(s,v)$不可能，从而得到$v.d=\delta(s,v)$

而引理1为引理2服务，引理3为推论服务，引理2和推论为最后定理的反证服务，如此相辅而成

Breadth-first trees

我们定义前驱图（predecessor subgraph）：

即除源点以外均有前驱的所有顶点组成前驱顶点集，而它们(除s)与其前驱构成的边组成前驱边集

源点到所有顶点的最短路径构成一颗宽度优先树（Breadth-first tree），因为$|V_\pi|=|E_\pi|+1$，正好是二叉树

我们打印最短路径可以用：

1
2
3
4
5
6
7
PRINT-PATH(G,s,v)
if v = s
 then print s
 elseif v.π = NIL
  then print "no path from" s "to" v "exists"
  else PRINT-PATH(G,s,v.π)
  	   print v

通过回溯要搜索的顶点的前驱得到最短路径

BFS的局限性

BFS求最短路径限制在了无权图中，如果是有权图，不适合BFS，举一个简单的例子：

1
2
3
A---(3)-----B
|           |
\-(1)-C--(1)/

按照BFS的逻辑，A到B的最短路径会是3，但实际是2

那么有权图的最短路径怎么求呢？

后面我们会单独讲解其他的最短路径算法，比如Dijkstra，Bellman-Ford算法，但它们的思想与BFS有相似之处

因此掌握BFS的算法思想对于其他的图算法是大有裨益的