CSCI3160 T08 SCC线性实现与汇分量

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T08 SCC线性实现与汇分量 · 原件 T08-强连通分量-未核-隐藏.pdf（本地课件） p.1–34 定位：把完成顺序数组、反向邻接表和逐个删除汇分量的解释连起来。 承接：L12 两遍DFS

p.1–3：复习两遍 DFS【新】

p.1 标题，p.2 目标输出{a,b,c}、{d,e,f,g,k,l}、{h,i}、{j}，p.3 重述原图完成标号、反转边、反图按递减标签启动。图（p.2）：本辅导在j处还画了自环。元素：自环反转仍是自己。看什么：它不改变SCC划分，DFS遇自己已灰也不会重复发现；本例比主课“简单图”的约定多了一条自环，应以此处图为准。

p.4–6：编号不是完成标签

p.4 将a,b,c,d,e,f,g,h,i,j,k,l改编号1,2,3,4,5,6,7,8,9,10,11,12。p.5 用A[i]存“第i个完成的顶点”，得到A=(8,2,3,1,12,11,6,5,4,7,9,10)。A[1]=8不是“8号标签等于8”。p.6 展示原邻接表；每点一条表头，后接全部出邻居，总空间O(V+E)。

p.6 的完整原图邻接表是：1:{3}，2:{1}，3:{2}，4:{2,5}，5:{1,6,7}，6:{4,11}，7:{4}，8:{9}，9:{7,8}，10:{10,5,7,8}，11:{12}，12:{6}。第一遍示例 DFS 森林有根9和根10；根9的树边为 9→8、9→7、7→4、4→5、5→1、1→3、3→2、5→6、6→11、11→12，根10单独成树。后序输出恰是给定 A。

p.7–9：反转边的操作方向

p.8 “add u to the neighbor list of v”

p.7 初始化V个空表头；p.8 扫原边1→3，在反图3的邻居表加1；p.9 扫2→1，在反图1的表加2。不能把每个原邻接表的元素顺序倒过来当作反图，那只改变扫描次序，并没改变箭头方向。

p.10–12：反图构造完整结果

p.10 扫3→2，将3加入反图2的表；p.11 完成后各点出邻居依次为：1:{2,5}，2:{3,4}，3:{1}，4:{6,7}，5:{4,10}，6:{5,12}，7:{5,9,10}，8:{9,10}，9:{8}，10:{10}，11:{6}，12:{11}。每条原边插入一次，O(V+E)。p.12 第二遍从A末尾开始，首点10。

p.13–15：前两个分量

p.13 从10只遇自己的自环，输出{10}并染黑；p.14 游标继续向前，下一白点A[11]=9；p.15 从9到8，输出{8,9}。图（p.13、15）：黑点逐渐增加，右侧画本轮DFS树。看什么：指向黑点10的边不会把已输出分量再吸入。

p.16–18：一次搜索跳过多个数组位置

p.16 下一个白点A[10]=7；p.17 沿反图访问7,5,4,6,12,11，输出六点SCC；p.18 继续倒扫，A[9]至A[5]都已黑，直到A[4]=1才另起搜索。数组游标始终向左，不需每次回到末尾重新找最大。

p.19–21：总时间为何保持线性

p.19 从1访问2、3，输出{1,2,3}；p.20 剩余数组项均黑，结束；p.21 转入结构解释。每个数组项被游标跳过一次，两遍DFS每边扫描一次，构造反图每边一次，总O(V+E)。即使有很多SCC，也不额外乘一个分量数。

补充：每个对象只走过常数次，不是每个分量重扫整图。 完成序数组有 V 个位置，游标从 V−1 单调减到 0；即使某一棵树一次染黑六个点，之后略过其五个旧位置的总工作也已包含在这 V 次内。反图邻接表始终保留，第二遍 DFS 只在首次发现一个点时扫描它的出边，所以所有树合计 E 次边检查。

可以把点的状态看成 白 → 当前分量搜索中 → 已输出；清空的是每次搜索的输出列表，而不是把此前点重新染白。若每找到一个分量就重置全部颜色，下一轮会重新进入已经输出的点，既可能重复输出，也破坏“外部邻居已黑”的证明。

实现三步可写成一个完整流程：第一遍发现点时标灰，扫描所有白色出邻居，退出时标黑并向 A 追加该点；扫描全部原边 u→v，向反图 v 的邻接表追加 u；把全部点重置为白一次，然后倒序扫描 A，每遇白点便在反图开启一次 DFS，把本次首次访问到的点记录为一个分量。没有新根时只略过该数组位置。返回全部分量以及每点的分量编号。

p.22–24：汇分量可一次完整取出

p.22 “if it has no outgoing edge”

sink SCC 指压缩图中出度0的分量，不是其内部每点出度0。图（p.22）：S4={a,b,c}无跨分量出边，内部仍有环。完整压缩图为 S1→S2、S1→S3、S2→S3、S3→S4，其中 S1={j}、S2={h,i}、S3={d,e,f,g,k,l}、S4={a,b,c}。自环留在 S1 内，不进入压缩图。p.23 若已知道一个汇SCC，从内部任何点DFS就恰好找到它；p.24 删除S4后S3成为新的汇。

p.25–27：在剩余图上重复

p.25 从S3中任一点找到{d,e,f,g,k,l}；p.26 删除它后S2成为汇；p.27 从S2得到{i,h}。要强调“剩余图”：S3原来有到S4的边，只有S4已删除或视为黑时，搜索才不会越界。

p.28–30：概念策略还缺找入口的方法

p.28 删除S2后只剩S1，p.29 得{j}。p.30 解释原图上概念顺序S4,S3,S2,S1虽正确，但在还没算SCC之前，不能直接假设知道这些分量。把“先找一个汇SCC”当作常数时间步骤是循环论证。

p.31–33：反图让完成次序派上用场

图（p.31）：压缩边全部反向，原图源S1变反图汇。元素：S4→S3→S2→S1，另有S3→S1。看什么：第一次DFS的最大完成标签给出原图源分量里的入口，所以在反图正好先处理汇。p.31 得S1，p.32 剩余汇为S2，p.33 为S3，和前面的根10、9、7一致。

p.34：最后的汇与算法对应

最后S4成为剩余反图的汇，从1开始得到a,b,c。这说明“完成顺序+反图”是在高效实现逐个剥离汇分量，而不是三个互不相关的步骤。程序只需颜色跳过旧点，无需反复物理删除图结构。

本讲核心考点

• （C 级 通识）完成序数组与顶点编号的区分。
• （C 级 通识）在线性时间构造反图与选择下一根。
• （C 级 通识）汇SCC的定义及反图第二遍为何隔离一个分量。

附录

本讲所需过程已在正文展开。

来源与证据

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

• 原件：T08-强连通分量-未核-隐藏.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：无

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