CSCI3160 L12 强连通分量与两遍DFS

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L12 强连通分量与两遍DFS · 原件 L12-Graph-02-Strongly-Connected-Compon-未核-隐藏.pdf（本地课件） p.1–18 定位：通过两遍 DFS 划分有向图，并解释为什么必须反转边、按完成次序启动。 承接：#L11-02 白路径定理（本地资料）

p.1–3：强连通还要求极大【新】

p.1 为标题。

p.2 S is maximal in the sense that we cannot put any more vertex into S without breaking the above property.

强连通分量 SCC 是极大的顶点集合：任意两点互相可达，而且不能再加入其他顶点保持这个性质。“极大”不是全图中点数最多，而是不能扩张。p.3 的 {a,b,c} 是 SCC；{a,b,c,d} 不是，因为引入 d 后不再互相可达；{d,e,f,k,l} 虽内部强连通却可再加入 g，故也不是完整 SCC。

p.4–5：分量确实形成划分

p.4 的引理对两个不同 SCC 断言交集为空。这里“不同”是结论成立的必要限定；同一分量当然与自身相交。

若两个强连通集合共享 x，则前者任意 u 可经 x 到后者任意 v，反向亦然；并集仍强连通，因此两个不同的极大集合不可能重叠。p.5 的目标划分是 {a,b,c}、{d,e,f,g,k,l}、{h,i}、{j}。一个孤点集合也可构成 SCC，这不要求它具有自环。

图（p.3、5）：12 个顶点的有向图。元素：a→c→b→a 是一个环；d,e,f,g,k,l 通过多条内部路径互达；h 与 i 双向相连；j 可走向其他区域但不能从这些区域返回。看什么：仅有“向外可达”不会把分量合并。

原图完整出邻接表（p.3）：a:{c}，b:{a}，c:{b}，d:{b,e}，e:{a,f,g}，f:{d,k}，g:{d}，h:{i}，i:{g,h}，j:{e,g,h}，k:{l}，l:{f}。其中 g→d 是图上方的弧线；它让 e→g→d→e 闭合，因此 g 必须与 d、e 一起归入分量。

p.6–8：第一次记录完成，随后反转全部边

p.6 规定：第 i 个变黑的顶点获得标签 i。

标签按第一次 DFS 的完成顺序从 1 增加，不是发现顺序。p.7 给出的完成顺序为 h,b,c,a,l,k,f,e,d,g,i,j，所以 h 的标签是1，a 是4，g 是10，i 是11，j 是12。第一次从 i 启动，最后另起根 j。

图（p.7–8）：原图及反转图。元素：第一次树包含 i→g→d→e，再分别向 a 和 f 深入；p.8 每条箭头反向，标签不变。看什么：反转的是整个原图，不能只反转 DFS 树边。实现时一次扫描原图边 (u,v)，向反向邻接表 v 中加入 u。

p.9–11：第二遍每棵树输出一个分量

p.9 Start at the vertex with the largest label.

第二遍先把颜色重置为白，在反转图上从标签最大的白点启动，栈空后仍这样选根。p.10 的根依次是 j、i、g、a，输出的四棵树分别就是上面的四个 SCC。树内部的访问次序可以有差异，分量划分不会改变。

p.10 的原例在第二遍实际使用以下完整候选顺序：j,i,g,d,e,f,k,l,a,c,b,h。先从 j 得 {j}；再从 i 得 {i,h}；从 g 得 {g,e,d,f,l,k}；顺序中后面的 d,e,f,k,l 已黑，全部跳过；从 a 得 {a,b,c}；最后 c,b,h 已黑，结束。不是每一个标签都启动一棵新树，而是只在白点处启动。

p.11 总时间 $O(V+E)$：两次 DFS 加构造反向邻接表都是线性。无需比较排序标签；第一次每完成一个点就压入列表，第二次倒序遍历该列表，遇黑跳过即可。若每次线性扫描寻找最大白点，反而可能引入平方时间。

补充：最小反例说明两项操作都不能少。 自取图仅有 a→b。第一次从 a 开始，先完成 b 后完成 a，标签分别 1、2。正确的第二遍反图只有 b→a，先从 a 开始只能收集 a，再从 b 收集 b，得到两个单点 SCC。

若不反图而仍从 a 开始，就会沿 a→b 把两个点放进同一树，错误合并。若已经反图却按标签从小到大，先从 b 开始也会走到 a，同样错误。不是“反图”和“排序”分别神奇地有效，而是反向边与递减完成次序共同保证不进入尚未处理的其他分量。

p.12–14：把整个分量压成一个点

p.12 定义分量图：每个压缩顶点代表原图一个不同的 SCC；两个不同分量之间，只要原图有任意一条对应方向的跨边，就在分量图中连边。

分量图的每个点是一个 SCC，跨分量的原图边变成分量间的边。它一定无有向环；否则环上的分量互相可达，应合并为一个 SCC。

图（p.13–14）：四个压缩点 S1={j}、S2={h,i}、S3={d,e,f,g,k,l}、S4={a,b,c}。元素：边为 S1→S2、S1→S3、S2→S3、S3→S4；分量标签取内部顶点完成标签的最大值。看什么：四个分量标签分别12、11、10、4，跨分量的箭头总从大标签指向小标签。

这里取最大值很关键：不必断言一个 SCC 的所有完成事件在时间上连续，也不必断言该分量每个点的标签都大于后继分量的每个点。

p.15–16：下降标签是证明的关键

p.15 $\mathrm{label}(S_i)>\mathrm{label}(S_j)$

若原图有跨分量边 Si→Sj，考察两者中最先发现的点。若它在 Si，则可到 Si 和 Sj 的所有尚白顶点，它完成时 Sj 已完成，所以 Si 的最大标签更大。若最先发现的点在 Sj，则 Sj 不可能到 Si，否则两者互达属于同一 SCC；因此 Sj 会先处理完，再轮到 Si，结论仍成立。

p.16 的原命题用入边表述：分量按最大标签递减编号后，反图中若 v→u 进入 $S_i$，而 v 不在其中，则 v 在某个 $S_j$，且 j>i。证明是将它还原成原图边 u→v，由 p.15 得 $\mathrm{label}(S_i)>\mathrm{label}(S_j)$，所以 j>i。等价地，将出发与到达分量交换来看，反图出边只能去编号较小的分量。下面采用这个等价出边说法。

p.16 将分量按最大标签递减排列。反转后，某个分量的出边只通向序列中更早、已经处理的分量。这正是第二遍不会“走出自己分量”的原因。只记“做两遍 DFS”而漏掉顺序或反转步骤，不能得到这个保证。

p.17–18：从第一棵树推广到全部

第一次选最大标签的 SCC：在反转图内部仍然互相可达，其外部出邻居均不存在于尚白分量，因此 DFS 恰好覆盖它。p.18 归纳：假设之前的 SCC 已全黑，下一最大标签白点所在分量内部全白、互达；能向外走到的较早分量已黑，故本棵树仍恰好是一个 SCC。

这也给出实现检验：每个点输出一次；树内任意两点互达；压缩图无环。三者帮助理解，不应拿实际运行的检查代替上述正确性证明。

分量间双向可达的判断题见附录 A1。

对应往年题见附录 A2。

本讲核心考点

• （C 级 通识）强连通集合与极大强连通分量的区别。
• （C 级 通识）第一次按完成顺序标号；第二次反图按标签递减选根。
• （C 级 通识）证明跨分量边使最大完成标签下降。
• （A 级：Final-2025T1 Q1(h)）不同 SCC 不能双向存在可达路径。

附录

A1 作业/往年题演练（非讲义内容）：Final-2025T1 第 1(h) 题

题面（Final-2025T1-题目.pdf · Q1(h) · p.2；扫描件，视觉读取）

p.2 “(h) (2 points) If S1 and S2 are two distinct strongly connected components in a directed graph, we cannot have a path from a vertex in S1 to a vertex in S2 and a path from a vertex in S2 to a vertex in S1 simultaneously.”

题源：Final-2025T1-题目.pdf（本地课件） p.2 Q1(h)。判断：两个不同 SCC 之间，不能既有从第一个到第二个的有向路径，又有从第二个到第一个的有向路径。

正确。假设双向路径均存在，利用两个分量内部的互相可达，就能把任意 u、v（分别属于两个分量）双向连接起来。并集仍强连通，与两个分量分别极大矛盾。注意允许单方向跨分量路径；禁止的是双向同时存在。

回到正文：分量划分

A2 作业/往年题演练（非讲义内容）：完成标签与分量方向

题面（Final-2021T1-题解.pdf · Part I Q3 · PDF p.2 左栏，印刷 p.3；扫描件，视觉读取；公式按原题重排）

p.2 “3. Determine true statements for an arbitrary DFS on a digraph G:”

(a) $post(u)>post(v)$ if there is a (u,v)-path in G.

(b) $post(u)>post(v)$ if G contains a (u,v)-path but no (v,u)-path.

(c) The vertex of maximum post number belongs to a source strongly connected component.

(d) The vertex of minimum pre number belongs to a sink strongly connected component.

(a)错：两点双向边图，DFS先发现v再发现u，u→v路径存在，但u先完成，所以post(u)<post(v)。(b)对：u、v不在同一SCC，存在从u到v的单向可达。若u先发现，会在u完成前把v完成；若v先发现，因为v不能到u，它会先完成，再在以后发现u。两种情况都得所述次序。

(c)对：若最大完成编号所在SCC有别的SCC指向它，前者的分量最大完成编号必更大，矛盾。因此它在源SCC中。(d)错：最先发现的点由DFS启动选择，可任意选；图a→b先从a启动，a的pre最小，却处于源分量而不是汇分量。结论为(b)、(c)，不是笼统说“所有有向路径都让post递减”。

回到正文：本讲结尾

来源与证据

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

• 原件：L12-Graph-02-Strongly-Connected-Compon-未核-隐藏.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：无

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