算法导论第22章
本章讨论广度优先搜索和深度优先搜索，和深度优先搜索的两个应用：有向图的拓扑排序和将有向图分解为强连通子图。
广度优先搜索
基础定义：
- color[v]:灰白黑。结点未被发现，初始时所有节点都被置为白色。第一次发现一个结点，将其置为灰色。当一个结点被搜索完，置为黑色。
-
δ
[
v
]
\delta[v]
δ[v]:当前s到v的最短路将长度
-
π
[
v
]
\pi[v]
π[v]：当前已知的s到v的最短路上v的前驱点
BFS算法描述：
BFS（G,s）
1 for each veertex u
∈
\in
∈ G.V - {s}
2
\quad
u.color = WHITE
3
\quad
u.d =
∞
\infty
∞
4
u
.
π
\quad u.\pi
u.π = NIL
5 s.color = GRAY
6 s.d = 0
7 s.
π
\pi
π = NIL
8 Q =
?
\phi
?
9 ENQUEUE(Q,s)
10 while(Q
≠
?
\neq \phi
?=?)
11
u
=
D
E
Q
U
E
U
E
(
Q
)
\quad u = DEQUEUE(Q)
u=DEQUEUE(Q)
12
f
o
r
e
a
c
h
v
∈
G
.
a
d
j
[
u
]
\quad for each v \in G.adj[u]
foreachv∈G.adj[u]
13
i
f
v
.
c
o
l
o
r
=
=
W
H
I
T
E
\quad \quad if v.color == WHITE
ifv.color==WHITE
14
v
.
c
o
l
o
r
=
G
R
A
Y
\quad \quad \quad v.color = GRAY
v.color=GRAY
15
E
N
Q
U
E
U
E
(
Q
,
v
)
\quad \quad \quad ENQUEUE(Q,v)
ENQUEUE(Q,v)
16
v
.
d
=
v
.
d
+
1
\quad \quad \quad v.d = v.d+1
v.d=v.d+1
17
v
.
π
=
u
\quad \quad \quad v.\pi = u
v.π=u
18
u
.
c
o
l
o
r
=
B
L
A
C
K
\quad u.color = BLACK
u.color=BLACK
最短路径
证明广度优先搜索可以正确计算出最短路径距离
引理22.1
给定G = （V,E），G为一个有向图或者无向图，设
s
∈
V
s\in V
s∈V为任意节点，则对任意边
(
u
,
v
)
∈
E
,
δ
(
s
,
v
)
≤
δ
(
s
,
u
)
+
1
(u,v)\in E,\delta (s,v)\leq \delta (s,u)+1
(u,v)∈E,δ(s,v)≤δ(s,u)+1
证明 ：
1、如果u是s可达的，则v也是，从s出发沿s到u的最短路，再经边（u，v）到v是一条s到v的普通路，则该路的长度为
δ
(
s
,
u
)
+
1
>
=
δ
(
s
,
v
)
\delta(s,u) +1>=\delta(s,v)
δ(s,u)+1>=δ(s,v)
2、如果u不是s可达的，
δ
(
s
,
u
)
=
∞
\delta(s,u) = \infty
δ(s,u)=∞
δ
(
s
,
v
)
<
=
δ
(
s
,
u
)
+
1
\delta(s,v) <= \delta(s,u) + 1
δ(s,v)<=δ(s,u)+1
引理22.2
设G（V,E）是一个有向图，无向图，BFS是以给定节点
s
∈
V
s \in V
s∈V作为源点在图G上运行，那么在BFS算法终结的时候，对每一个节点
v
∈
V
v\in V
v∈V,BFS所计算出来的v.d满足
v
.
d
≥
δ
(
s
,
v
)
v.d \geq \delta(s,v)
v.d≥δ(s,v)
证明 对算种种的入队操作次数进行归纳
1、归纳基础：s.d =
δ
(
s
,
s
)
=
0
\delta(s,s) = 0
δ(s,s)=0
2、归纳假设：第k次入队后，KaTeX parse error: Undefined control sequence: \inV at position 10: \forall v\?i?n?V?,v.d \beq\delta…
3、虚证明对第k+1次入队操作，
?
v
∈
V
,
v
.
d
≥
δ
(
s
,
v
)
\forall v\in V,v.d\geq\delta(s,v)
?v∈V,v.d≥δ(s,v)
设第k+1次入队的是v，
π
[
v
]
=
u
.
d
[
v
]
=
d
[
u
]
≥
δ
(
s
,
u
)
+
1
≥
δ
(
s
,
v
)
\pi[v] = u. d[v] = d[u]\geq \delta(s,u) + 1\geq\delta(s,v)
π[v]=u.d[v]=d[u]≥δ(s,u)+1≥δ(s,v)
引理 22.3
假定BFS在图G = （V,E）上运行的过程中，队列Q包含的的节点为
<
u
1
,
v
2
,
.
.
.
,
v
r
>
<u_1,v_2,...,v_r>
<u1?,v2?,...,vr?>,这里
v
1
v_1
v1?是队列Q的头，
v
r
v_r
vr?是队列Q的尾。那么
v
r
.
d
≤
v
1
.
d
+
1
(
1
)
v_r.d \leq v_1.d+1\quad(1)
vr?.d≤v1?.d+1(1)
v
i
≤
v
i
+
1
(
2
)
v_i \leq v_{i+1}\quad(2)
vi?≤vi+1?(2)
证明对队列的变化数进行归纳证明：
1、归纳基础; Q = < s >
2、归纳假设 假设第k次队列变化后，条件(1)(2)成立，证明第k+1次变化后条件（1）（2）依然成立
3、：
3.1 第k+1次是出队操作
Q =
<
v
2
,
v
3
,
.
.
.
,
v
r
>
<v_2,v_3,...,v_r>
<v2?,v3?,...,vr?>
d
[
v
r
]
≤
d
[
v
1
]
+
1
≤
d
[
v
2
]
+
1
d[v_r] \leq d[v_1] + 1\leq d[v_2] + 1
d[vr?]≤d[v1?]+1≤d[v2?]+1
d
[
v
i
]
≤
d
[
v
i
+
1
]
d[v_i] \leq d[v_{i+1}]
d[vi?]≤d[vi+1?]
3.2 第k+1次是入队操作
Q =
<
v
1
,
v
2
,
.
.
.
,
v
r
,
v
r
+
1
>
<v_1,v_2,...,v_r,v_{r+1}>
<v1?,v2?,...,vr?,vr+1?>
v
r
+
1
v_{r+1}
vr+1?入队，那么一定有结点u被扫描邻接链表，则u是刚从队列中出队，在u从队列中出队前瞬间，队列状态
{
<
u
,
v
1
,
v
2
,
.
.
.
,
v
r
>
(
1
)
<
u
,
v
1
,
v
2
,
v
k
>
k
<
r
(
2
)
<
u
>
(
3
)
\left\{\begin{matrix} <u,v_1,v_2,...,v_r>\quad(1)\\ <u,v_1,v_2,v_k>\quad k < r\quad(2)\\ <u>\quad(3) \end{matrix}\right.
????<u,v1?,v2?,...,vr?>(1)<u,v1?,v2?,vk?>k<r(2)<u>(3)?
情况（1）：
d
[
v
r
]
≤
d
[
u
]
+
1
=
d
[
v
r
+
1
]
d[v_r] \leq d[u] + 1 = d[v_{r+1}]
d[vr?]≤d[u]+1=d[vr+1?]
d
[
u
]
≤
d
[
v
1
]
→
d
[
v
r
+
1
]
≤
d
[
v
1
]
+
1
d[u]\leq d[v_1]\rightarrow d[v_{r+1}]\leq d[v_1]+1
d[u]≤d[v1?]→d[vr+1?]≤d[v1?]+1
情况（2）：
d
[
u
]
≤
d
[
v
1
]
→
d
[
v
r
+
1
]
=
d
[
u
]
+
1
≤
d
[
v
1
]
+
1
d[u] \leq d[v_1]\rightarrow d[v_{r+1}] = d[u]+1 \leq d[v_1]+1
d[u]≤d[v1?]→d[vr+1?]=d[u]+1≤d[v1?]+1
d
[
v
k
]
≤
d
[
u
]
=
d
[
v
k
+
1
]
=
.
.
.
=
d
[
v
r
+
1
]
d[v_k] \leq d[u] = d[v_{k+1}] =...=d[v_{r+1}]
d[vk?]≤d[u]=d[vk+1?]=...=d[vr+1?]
情况（3）
d
[
v
1
]
=
d
[
v
2
]
=
.
.
.
=
d
[
v
r
+
1
]
d[v_1] = d[v_2] = ... = d[v_{r+1}]
d[v1?]=d[v2?]=...=d[vr+1?]
推论 22.4 在执行BFS时，结点
V
i
V_i
Vi?和节点
v
j
v_j
vj?都加入到队列中，并且
v
i
v_i
vi?在
v
j
v_j
vj?前面入队，则入队时
d
[
v
i
]
≤
d
[
v
j
]
d[v_i] \leq d[v_j]
d[vi?]≤d[vj?]
易证
定理 22.5 对
?
v
∈
V
,
δ
(
s
,
v
)
=
d
[
v
]
\forall v \in V,\delta(s,v) = d[v]
?v∈V,δ(s,v)=d[v]
证明（反证法）假设存在某些点使得
d
[
?
]
>
δ
(
s
,
?
)
d[*] > \delta(s,*)
d[?]>δ(s,?),设v是这些点中
δ
(
s
,
v
)
\delta(s,v)
δ(s,v)最小的点，且
δ
(
s
,
v
)
≠
∞
\delta(s,v) \neq \infty
δ(s,v)?=∞,否则
d
[
v
]
<
=
δ
(
s
,
v
)
d[v] <= \delta(s,v)
d[v]<=δ(s,v),则存在从s到v的最短路，
v
≠
s
(
d
[
s
]
=
δ
(
s
,
s
)
=
0
)
v\neq s(d[s] = \delta(s,s) = 0)
v?=s(d[s]=δ(s,s)=0)
u是s到v的最短路上v之前的一点，
δ
(
s
,
v
)
=
δ
(
s
,
u
)
+
1
,
δ
(
s
,
u
)
<
δ
(
s
,
v
)
\delta(s,v) = \delta(s,u)+1,\delta(s,u) < \delta(s,v)
δ(s,v)=δ(s,u)+1,δ(s,u)<δ(s,v)
因为根据对结点v的要求和定义，
d
[
u
]
=
δ
[
u
]
d[u] = \delta[u]
d[u]=δ[u]
d
[
v
]
>
δ
(
s
,
v
)
>
d
[
u
]
+
1
d[v] > \delta(s,v) > d[u]+1
d[v]>δ(s,v)>d[u]+1
考虑u出对前瞬间v的颜色
{
白
d
[
v
]
=
d
[
u
]
+
1
灰
d
[
v
]
≤
d
[
u
]
黑
d
[
v
]
≤
d
[
u
]
\left\{\begin{matrix} 白 d[v] = d[u] + 1 \\ 灰 d[v] \leq d[u]\\ 黑 d[v] \leq d[u] \end{matrix}\right.
????白d[v]=d[u]+1灰d[v]≤d[u]黑d[v]≤d[u]?
因此假设不成立，则
?
v
∈
V
,
δ
(
s
,
v
)
=
d
[
v
]
\forall v \in V,\delta(s,v) = d[v]
?v∈V,δ(s,v)=d[v]
时间复杂度
O(V+E)
深度优先搜索
拓扑排序
强联通分解
|