广度优先搜索按距离层探索图;深度优先搜索(DFS)则沿一条路径走到尽头才回头。这种次序对最短路径用处不大,却能揭示图的结构:环、后代关系,以及任务的合法先后次序。分析之前必须先确定图如何存储,因为所有图算法的代价都取决于这个选择。前面的广度优先搜索单元已默认使用邻接表,本单元说明这一选择的理由。
表示方法
设 为有限有向图,有 个顶点 及 条弧。无向边以两条弧存储。
定义 13.2.1
(邻接矩阵与邻接表)
邻接矩阵是 数组 :若存在弧 则 ,否则为 。邻接表为每个顶点 存储一个列表,列出所有满足弧 的顶点 。
| 操作 | 矩阵 | 邻接表 |
|---|---|---|
| 空间 | ||
| 是否为弧? | ||
| 列出 的所有出邻居 | ||
| 遍历每条弧一次 |
其中 是离开 的弧数。若 ,图称为稀疏图(路线图、依赖关系图多属此类);若 则称为稠密图。稀疏图用邻接表占用空间小得多,遍历也快得多;稠密图两者空间同阶,而矩阵可在常数时间内查询弧。遍历需要逐个扫描每个顶点的邻居,所以 DFS 与 BFS 默认使用邻接表。
算法
DFS 为每个顶点记录颜色:白色(未发现)、灰色(已发现但未完成,即正在递归栈上)、黑色(已完成)。全局时钟记录两个时间戳:发现时间 与完成时间 。
def dfs_all(graph):
n = len(graph)
color = [0] * n # 0 white, 1 gray, 2 black
d = [0] * n
f = [0] * n
clock = 0
finish_order = []
back_edges = []
def visit(u):
nonlocal clock
color[u] = 1
clock += 1
d[u] = clock
for v in graph[u]:
if color[v] == 0:
visit(v)
elif color[v] == 1:
back_edges.append((u, v))
color[u] = 2
clock += 1
f[u] = clock
finish_order.append(u)
for s in range(n):
if color[s] == 0:
visit(s)
return d, f, finish_order, back_edges
外层循环从每个白色顶点重新开始,整个图因而都被覆盖,得到由若干 DFS 树组成的森林。每个顶点只被访问一次,因为它在检查邻居之前已经着色;每条弧只被检查一次,即展开其起点时。使用邻接表时,运行时间为 ;使用矩阵则为 。递归深度可达 ,所以递归深度上限较小的语言处理长路径时需要显式栈。
概念视角结构
灰色顶点构成当前路径
任何时刻,灰色顶点恰好就是由当前 DFS 树的根走到正被展开的顶点的那条树路径上的顶点,按发现次序排列。每次调用 visit 把该顶点加入这条路径,顶点变为黑色时才移出。因此黑色顶点构成已完成的子树,白色顶点则尚未触及。这是对同一个搜索的另一种读法:指向灰色顶点的弧沿当前路径往回指,指向黑色顶点的弧则指向已经完成的部分。
搜索的结构
定理 13.2.2
(括号性质)
对任意两个顶点 ,区间 与 要么不相交,要么其中一个包含另一个。顶点 是 在 DFS 树中的后代,当且仅当 。
证明
(调用像栈一样嵌套)
所有时间戳都互不相同,所以对 可设 。若 ,则 在 仍为灰色时被发现,即发生在调用 visit(u) 期间。调用像栈一样嵌套进行,所以 visit(v) 先于 visit(u) 返回,即 。若 ,两区间不相交。关于后代的叙述: 的后代都在 visit(u) 期间被发现,因此区间互相嵌套;反过来,若 ,则 在 visit(u) 期间被发现,所以它属于由 开始的调用所形成的子树。 与 对调的情形对称。
检查弧 时,由 的颜色和时间戳判断其类型:
- 树弧: 为白色(它成为 的子节点);
- 回边: 为灰色( 是 的祖先,也可能就是 本身);
- 前向弧: 为黑色且 ( 是 的非子节点的后代);
- 横跨弧: 为黑色且 (没有祖孙关系; 在 开始前已完成)。
定理 13.2.3
(环与回边)
有限有向图含有有向环,当且仅当对它作深度优先搜索时找到回边。
证明
(回边给出环,环必产生回边)
若有回边 ,则 为灰色,所以 是 的祖先(或 ),从 到 的树路径加上弧 就是一个环。
反之,设 为一个环, 为 上发现时间最小的顶点。把 写成 ,其中 ( 即 上的自环)。 被发现时, 全是白色。对 作归纳,证明每个 都在 visit(w) 期间被发现。 显然成立。设结论对 成立。调用 visit() 位于 visit(w) 之内,并在返回之前检查弧 。若此刻 是白色,它成为 的子节点;否则它已在 之后被发现(因为当时它是白色),所以是在 visit(w) 期间被发现。两种情形下 都在 visit(w) 期间被发现。
特别地, 是 或 的后代,并在 visit(w) 之内检查弧 。此时 尚未完成,仍是灰色,所以弧 是回边。
证明透视
为什么要取最先被发现的顶点
逆向的证明取决于一个选择: 是 上最先被发现的顶点。这个选择有两个作用:使 的其余顶点在时间 都是白色,归纳由此开始;也保证通往 的闭合弧是在 仍未完成时被检查,所以 是灰色。环上其他顶点都不行。例如 、 从 0 开始搜索, 虽在环上,却在 0 之后才被发现,所以在时间 ,顶点 0 是灰色而不是白色,白色路径的论证无从开始。此时回边是 ,它指向最先被发现的顶点。自环的情形 不需另行论证:,检查 自己的弧时 是灰色。
定理 13.2.4
(由完成时间得拓扑序)
若有向图无环,则把顶点按完成时间从大到小列出,便得到拓扑序:对每条弧 , 都排在 之前。
证明
(每条弧的终点先完成)
考虑在 visit(u) 期间检查的弧 。 不可能是灰色,否则它是回边,图便有环。若 为白色,它成为 的后代并先完成,故 。若 为黑色,它已完成,同样 。两种情形下 都先于 完成,所以在完成时间递减的次序中 在前。
反例模式
发现次序不是拓扑序
有人会想按发现时间从小到大列出无环图的顶点。取 、、,先从 0 再从 2 搜索,得 、,发现次序为 。弧 在其中指向后方,因为 2 比 1 晚发现。按完成时间从大到小则得 ,弧 与 都指向前方。较晚开始的顶点仍可排在较早的前面,所以只有完成时间才有保证。
例题
例题 13.2.5
(六个顶点的有向无环图上的 DFS)
邻接表为 、、、、、。从 0 出发,时钟为 0。访问 0(),然后 1()、3()、5()。5 没有邻居,所以 。回到 3,;回到 1,。返回 0,检查 2:。它的第一个邻居 3 是黑色且 ,所以 是横跨弧。第二个邻居 4 是白色:;4 的邻居 5 是黑色且发现时间较小,是横跨弧;,,。
完成次序为 ,按完成时间递减得 。逐条弧检查:、、、、、、 全部由此列表中较前的顶点指向较后的顶点。树弧为 、、、、。
例题 13.2.6
(以回边找出环)
取 、、、。DFS 依次发现 ,。在顶点 2,第一个邻居是 0,它是灰色,所以 是回边。栈上的灰色顶点为 ,沿栈从 0 走到 2,再加上回边,得到环 。搜索继续:3 是白色,,;然后 ,,。
再加入前向弧:若图中还有弧 ,列在 之后,则 0 在完成 1 之后继续时,顶点 2 是黑色,且 ,所以 是前向弧。
例题 13.2.7
(自环与多棵搜索树)
取 、、。外层循环从 开始。顶点 0 变为灰色,,它唯一的邻居就是 0 本身,而 0 是灰色,所以 是回边,图含有长度为一的环。然后 。顶点 1 仍是白色,外层循环便开始第二棵树:,白色邻居 2 得 、,再 。结果是由两棵树(根分别为 0 和 1)组成的森林,另有一条回边。
两个边界情形都在此出现。自环是颜色判断不需特别处理就能检测出的环,因为检查 自己的弧时 是灰色。此外,若只从一个起点搜索,就会漏掉顶点 1 和 2,这正是外层循环属于算法一部分的原因。
常见错误
反例模式
无向图:父节点不构成环
把含边 、 的无向路径以双向弧存储,并使用“灰色邻居即有环”的判断。在顶点 1,邻居 0 是灰色,因为它是我们到达 1 时所经的父节点,于是判断错误地报告有环。在无向简单图中,应跳过一次通往树父节点的弧;此后任何其他灰色邻居才表示有环。若有平行边,通往父节点的第二条边确实构成环,所以应按边的身份而非按顶点来跳过父边。
常见错误
(把完成次序顺着读)
取单独一条弧 。从 0 搜索得 、、、,完成次序是 ,弧在其中指向后方。拓扑次序是它的反转,即 。若图有环,则根本不存在拓扑次序,所以须先检查定理的前提,例如看看有没有回边。
常见错误
(顶点到完成时才标记)
顶点必须在进入时着色,而不是在完成时。对 、,若 0 到结束才被标记,则 visit(1) 会把 0 视为白色,再次调用 visit(0),递归永不停止。进入时着色才有灰色状态,回边检测也才可能。
习题与解答
快速检查
(有向图有 n = 1000 个顶点、m = 3000 条弧。比较矩阵与邻接表存储的项数,以及在两者上作 DFS 的代价。)
解答 · 答案
矩阵存储 项;邻接表存储 个表头加 个弧项,约 个单元。在邻接表上 DFS 需 步;在矩阵上,1000 个顶点各扫描一行 1000 项,需 步。此图稀疏,所以邻接表更优。
快速检查
(对 0:[2]、1:[0]、2:[1,3]、3:[ ] 从 0 出发作 DFS。求 d、f、各弧类型及环。)
解答 · 答案
访问 0(),然后 2(),再 1()。弧 发现 0 为灰色:回边。。回到 2,顶点 3 是白色:,。然后 ,。弧的类型:、、 是树弧, 是回边。环为 。所有顶点均已完成,外层循环不会再从别处开始。
快速检查
(区间:A=[1,8]、B=[2,5]、C=[3,4]、D=[6,7]。分类弧 A 到 C、C 到 A、D 到 B、A 到 D。)
解答 · 答案
从区间可见 在 内, 在 内, 在 内但与 不相交。弧 : 是 的后代但不是子节点(它在 内),检查时它是黑色且 :前向弧。弧 : 是祖先,为灰色:回边。弧 : 在 开始前已完成(),为黑色且 :横跨弧。弧 : 与 之间没有别的顶点包含 ,所以 是 的子节点:树弧。
快速检查
(以完成时间为 0:[3]、1:[3,4]、2:[4]、3:[ ]、4:[ ] 求一个拓扑序,DFS 按 0、1、2 的次序开始。)
解答 · 答案
从 0:,访问 3:,,然后 。从 1:;3 为黑色;访问 4:,;。从 2:;4 为黑色;。完成次序为 ,反转得 。每条弧都向前:(位置 4 与 5)、(2 与 5)、(2 与 3)、(1 与 3)。
快速检查
(无向图有边 {0,1} 与 {1,2}。为何“灰色邻居即有环”会误报,如何修正?)
解答 · 答案
每条无向边以两个方向存储。DFS 由 0 到达 1 时,邻居 0 是灰色,因为它是树父节点,而不是因为有环。修正方法是忽略那条经由发现当前顶点时所用的边、通往父节点的弧。只有经由另一条边到达的灰色邻居,才表示有环。