CSCI3160 L11 深度优先搜索与白路径定理

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L11 深度优先搜索与白路径定理 · 原件 L11-Graph-01-DFS-White-Path-Theorem-未核-隐藏.pdf（本地课件） p.1–18 定位：用栈、颜色和搜索树理解 DFS，为强连通分量证明准备工具。

p.1–3：DFS 同时维护三种状态【新】

p.1 是标题页；p.2 指出本讲要复习 white path theorem，而不是只记搜索顺序。

p.3 In the beginning, color all vertices in the graph white and create an empty DFS tree T.

p.3 的输入是有向简单图 $G=(V,E)$；V 是顶点集合，E 是有向边集合，出邻居 u 表示存在边 v→u。白色表示尚未发现，灰色表示已发现但尚未完成，黑色表示出边已经检查完。栈保存当前仍在处理的顶点；栈顶决定下一步。把起点染灰并压栈，就产生一棵 DFS 树的根。以后首次发现的顶点以发现它的顶点为父亲。原图可以有很多边，搜索树只保留首次发现边，不能把两者混为一谈。

p.4–5：推进和退栈是两种不同动作

p.5 Let v be the vertex that currently tops the stack S (do not remove v from S).

p.4 原图的完整出邻接表为：a:{b,d}，b:{c}，c:{d,e}，d:{g}，e:{d}，f:{e}，g:{f,i}，h:{d,g}，i:{f}。这列出了图上所有有向边；交叉处没有新增顶点。

p.4 从 a 开始，栈为 (a)。p.5 的规则是：若栈顶 v 有白色出邻居 u，就把 u 染灰、压栈并设父亲为 v；若没有，就把 v 染黑并弹出。只有白色邻居可以生成新的树边；遇到灰色或黑色邻居不再递归。栈空但仍有白点时另选根，最终得到森林。

p.5 的循环可完整写为：

把每个顶点设为白色，父亲为空
对任意仍为白色的根 r：
  r 设灰，压栈；为 r 初始化出边扫描位置
  当栈不空：
    v = 栈顶（此时不弹出）
    从 v 尚未扫描的出边继续寻找白色邻居 u
    若找到：记录 parent[u]=v；把 u 染灰压栈
    若出边已经全部扫描：弹出 v；染黑；记录完成事件

“继续寻找”包括跳过灰或黑邻居；每条边只推进扫描位置一次。父亲数组与各根构成 DFS 森林，原图本身不因此删边。

邻接表实现中，每个点入栈出栈一次，每条出边扫描一次，所以总时间 $O(V+E)$。若每次从头重新扫描邻接表，不能直接引用这个实现界；需保存扫描位置或使用递归调用中的循环。

p.6–8：为什么一直深入

图（p.6–8）：a、b、c、d 等顶点和逐步增长的 DFS 树。元素：有向边代表原图可走方向，灰色顶点在活动栈上，右侧树记录父子关系。看什么：p.6 由 a 发现 b，p.7 由 b 发现 c，p.8 c 在 d、e 中先选 d，于是栈从 (a,b) 到 (a,b,c,d)。

这里的邻居选择是本次演示的约定，不是 DFS 的唯一合法顺序。c 虽然也能直接到 e，但此时先挂起 c 的后续检查，处理 d 的整段搜索。

p.9–11：发现次序不能替代完成次序

p.9 d 发现 g，p.10 g 先发现 f，p.11 f 发现 e。此时栈为 (a,b,c,d,g,f,e)，每一项都是下一项的树祖先。e 有到 d 的边，但 d 已灰，不能再次压栈；否则环会造成重复搜索。

图（p.10–11）：g 的两个可能分支是 f 和 i。元素：本次先走 g→f→e。看什么：原图的边不保证成为搜索树边；例如 c→e 最终也不会成为树边，因为 e 已通过另一条路径发现。

p.12–14：黑色意味着这一轮处理完毕

p.12 e 无白色出邻居，先变黑；f 随后也完成。栈退回 (a,b,c,d,g)。p.13 g 尚有白色出邻居 i，故父亲为 g，而不是此前刚完成的 f。p.14 i 检查完后，依次完成 g、d、c、b、a。

把事件写全更容易检查：本棵树的发现顺序是 a,b,c,d,g,f,e,i，完成顺序是 e,f,i,g,d,c,b,a。发现早不意味着完成早；祖先总在后代完成之后才完成。

p.15–16：有边连向已访问区域，也可能是新树

p.15 仍白的 h 成为第二个根。h 的出边到 d、g，但两者已经黑，因此 p.16 直接完成 h。森林有两棵树，不代表原图有两个弱连通分量；有向可达性和启动顺序都影响 DFS 树的数量。

补充：栈帧不只是顶点名字。 递归实现的每个活动调用还隐含保存“下一条尚未检查的出边”。迭代实现若只存顶点、不保存这个位置，退回父亲后可能把旧邻接表从头反复扫描；为了维持线性时间，应保存 (顶点,下一邻边索引)。灰色表示这个栈帧仍存在，黑色表示它的整个出边循环已完成，不能在刚压栈时就涂黑。

自取小图 a→b、a→c、b→c，邻居按 b 再 c 检查，完整事件如下：

a→c 这条原图边被检查，但不成为树边。若给发现和完成事件统一递增编号，a 为(1,6)，b为(2,5)，c为(3,4)：后代的整个时间区间包含在祖先区间内。

p.17–18：白路径定理锁定一个时间截面

p.17 Consider the moment when u enters the stack.

在 u 刚被发现、进入栈的那个时刻，v 是 u 的真后代，当且仅当存在从 u 到 v 的路径，其余顶点在该时刻全为白色。u 此刻已灰，所以“白路径”要理解为发现前的快照，或把起点 u 单独豁免；不能要求当下 u 仍白。

图（p.18）：g 入栈时的快照。元素：a,b,c,d,g 已在灰色栈上，f,e,i 仍白，h 也白但不是从 g 沿白点可达。看什么：g 的真后代恰为 f,e,i；不能沿 e→d 穿过灰色 d 再推断额外后代。

为什么成立？若 v 是后代，从 u 到 v 的树路径在 u 发现时尚未发现，否则 DFS 不会再次发现这些点。反过来，假设有白路径却存在某点未在 u 完成前被发现，取路径上第一个这样的点，其前驱在 u 的搜索内完成前必检查这条边，便会发现它，产生矛盾。这说明定理约束的是整段将来的搜索，不是只看下一条边。

白路径的考试应用见附录 A1。

对应往年题见附录 A2。

本讲核心考点

• （C 级 通识）给定邻居次序，分别写发现、完成次序和 DFS 森林。
• （C 级 通识）用白、灰、黑解释环边为什么不会再次入栈。
• （A 级：Final-2024T1 Q5）在指定时刻沿白色顶点求某点的必然后代。

附录

A1 作业/往年题演练（非讲义内容）：Final-2024T1 第 5 题的白路径

题面（Final-2024T1-缺判断-题目.pdf · Problem 5 · p.4；扫描件，视觉读取）

p.4 “Problem 5 (5 marks). Let G be the following directed graph.”

“Suppose that Prof. Goofy runs DFS on G for a while and then pauses the algorithm. He tells us the following information:”

“c is the vertex that will be pushed into the stack next.”

“Currently, all vertices except for j, k, and l are colored white.”

“Which vertices will become descendants of c in the DFS-forest that will eventually be returned when the DFS finishes? You need to justify your answers.”

图（题面，p.4）：十二点有向图。 元素：边a→c、a→e、e→c、c→b、b→d、d→c、c→g、g→f、f→h、h→g、c→j、j→k、k→l、l→j、i→c、i→d、i→j。 看什么：c即将压栈，此时j、k、l已经不是白色。白色出发路径只可使用白色点。

题源：Final-2024T1-缺判断-题目.pdf（本地课件） p.4 Q5。题目给的是 c 即将压栈之前的快照，紧接着发现 c 时其余白点不变，因此可以应用白路径定理。

由 c 沿白点可到 b，再到 d；还可到 g、f、h。因此真后代是 b,d,f,g,h。边 c→j 不能继续，因为 j 已非白色；i 虽与 c 附近相连，但边指向 c，不构成从 c 到 i 的白路径。不能把图画得近的 a、e 也计入。若题目使用包含根的 subtree，集合还应包含 c；这里后代按真后代计。

回到正文：白路径定理

A2 作业/往年题演练（非讲义内容）：DFS 时间戳与 DAG

题面（Midterm-2021T1-题目.pdf · Q2(a) · p.1；公式按原题重排）

p.1 “(a) For any edge uv in a dag G, which property holds for every DFS of G?”

(1) $pre(u)>pre(v)$ (2) $post(u)>post(v)$ (3) $post(u)<post(v)$ (4) $pre(u)<pre(v)$ (5) $pre(u)<post(v)$.

扫描u→v时，v若白，DFS将它及其后代处理完后才完成u，所以post(u)>post(v)；v若黑，则它已经完成，仍早于u；v若灰，是当前u的祖先，祖先到u的树路径加u→v将成环，与DAG条件矛盾。故只有(2)对每次DFS都成立。发现序列会随搜索起点改变，不能据一个例子选(1)或(4)。

题面（Midterm-2021T1-题目.pdf · Q5 · p.2；图已对照题解扫描页）

p.2 “5. [4 points] For digraph D, determine the pre- and post-numbers of vertex 8 for a DFS starting at vertex 1 (i.e., pre(1) = 1), assuming that the DFS visits the smallest unvisited vertex when there are multiple qualified frontier edges.”

图（题面，p.2）：九点有向图。 元素：出邻接表为1:{2,3,4}，2:{5,6}，3:{6,8,9}，4:{3,9}，5:{}，6:{}，7:{5,6}，8:{6,7,9}，9:{}。 看什么：箭头交叉不生成顶点；按最小未访问编号递归。

全事件依次为：发现1(1)，发现2(2)，发现5(3)，完成5(4)，发现6(5)，完成6(6)，完成2(7)，发现3(8)，发现8(9)，发现7(10)，完成7(11)，发现9(12)，完成9(13)，完成8(14)，完成3(15)，发现4(16)，完成4(17)，完成1(18)。因此8的pre=9、post=14。3的邻居6早已黑，不能给它第二个pre；这是容易把后面编号整体算偏的地方。

回到正文：本讲结尾

来源与证据

• 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

• 原件：L11-Graph-01-DFS-White-Path-Theorem-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。

• 版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。

• 发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。

• 既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无

• 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。