强连通分量算法 | Codeboy's Blog

形式陈述

设有限有向图 $D=(V,A)$ 。定义

u\sim v \quad\Longleftrightarrow\quad u\leadsto v\ \text{且}\ v\leadsto u.

可达性的自反性与传递性，加上定义中的对称写法，使 $\sim$ 成为等价关系；它的极大等价类称为强连通分量（SCC）。分解由图唯一确定，与算法的搜索次序无关。

把每个 SCC 收缩为一个顶点，并在不同分量间存在原弧时连一条弧，得到凝聚图 $D^{\mathrm{SCC}}$ 。它必为 DAG：若若干分量在凝聚图中形成有向圈，沿圈任意两分量都能互相到达，本应属于同一个极大分量。

Kosaraju–Sharir 算法先在 $D$ 上做DFS，再按完成时间递减的顺序在转置图 $D^{\mathsf T}$ 上启动 DFS；第二遍的每棵搜索树恰是一项 SCC。证明可投影到凝聚 DAG：第一遍完成时间最大的未处理分量，在转置凝聚图中不会走到另一个未处理分量，所以第二遍不会越界；分量内部又互相可达，故一次搜索恰好取完该分量。

Tarjan 算法只做一遍 DFS。给顶点 $v$ 记录发现编号 $index[v]$ 、是否仍在活动栈上，以及lowlink：从 $v$ 的 DFS 子树出发，沿树边并最后使用一条指向栈内顶点的弧所能触及的最小发现编号。对树边 $v\to w$ ，递归返回后用 $lowlink[w]$ 更新；对指向栈内已发现点 $w$ 的弧，只用 $index[w]$ 更新。若

lowlink[v]=index[v],

则 $v$ 是一个尚未输出 SCC 的根，从栈顶弹出到 $v$ 为止正好得到整个分量。指向已出栈顶点的弧不能参与更新，因为目标已经属于封闭的旧分量。

在同时存出邻接表与转置邻接表的表示中，Kosaraju–Sharir 时间为 $\Theta(|V|+|A|)$ ，额外图存储为 $O(|V|+|A|)$ ；也可按输入接口即时枚举入弧。Tarjan 在出邻接表上同样是 $\Theta(|V|+|A|)$ 时间，数组、活动栈和递归栈为 $O(|V|)$ 。这些界假定静态图与单位成本的顶点、弧访问。

直觉

SCC 把图中的循环区域压成不可再分的“往返岛屿”。岛内任意点都能去而复返；岛与岛之间一旦离开，凝聚图的无环性保证不可能沿分量边绕回。这样，原图的循环结构留在分量内部，分量之间则恢复可拓扑处理的偏序。

两类线性算法利用的是同一方向不对称。Kosaraju–Sharir 先用完成时间找到凝聚图边界，再在反图中从不会外泄的分量开始剥离。Tarjan 把尚未归属分量的顶点留在栈上，lowlink 询问当前 DFS 子树能否回到更早的活动顶点；一旦回不到根之前，就可以封口并弹出一整段。

例子与边界

考虑弧

1\leftrightarrow2,\qquad 2\to3,\qquad 3\to4,\quad4\to5,\quad5\to3,\qquad5\to6.

分量依次为 $C_1=\{1,2\}$ 、 $C_2=\{3,4,5\}$ 、 $C_3=\{6\}$ ，凝聚图只有 $C_1\to C_2\to C_3$ 。从 $1$ 能到 $6$ ，却不能返回，故“单向可达”不能用来分组。若把每条无向边替换成一对反向弧，无向连通分量才会与 SCC 一致。

在 Tarjan 实现中，设 $C_3$ 已经弹栈，随后扫描 $5\to6$ ；即使 $index[6]$ 很小，也不能降低 $lowlink[5]$ ，因为从 $6$ 没有返回当前活动分量的保证。另一个常见错误是对任意栈内邻点使用 $lowlink[w]$ ；非树弧应取 $index[w]$ ，否则可能跨越尚未证实的 DFS 结构合并分量。

平行弧不改变 SCC 划分，只增加扫描记录；自环让单顶点分量显式含圈，但没有自环的孤立顶点也仍是一个 SCC。SCC 分解唯一，分量的编号、输出顺序和 DFS 树均可随邻接顺序改变。

推论与应用

凝聚图允许先在分量内部处理循环，再按拓扑序传播分量间信息。2-SAT 用变量文字图中的 SCC 判断某个文字与其否定是否同属一分量；依赖分析可把互相递归的模块合成一个编译单元；DAG 动态规划则从凝聚后的无环骨架开始。

自动机论模型检查会在系统与 Büchi 自动机的积图中寻找从初态可达、含接受状态且确有可重复圈的 SCC。单顶点 SCC 若没有自环，不能仅凭“它是 SCC”就断言存在正长度循环；接受条件仍需单独核对。

支配树询问单入口 flow graph 的所有入口路径是否必经某点，输出祖先树；SCC 询问两点是否存在双向路径，输出等价类。二者都使用 DFS 编号，但量词、状态和更新公式不同。对动态图，插入一条返弧就可能合并整条凝聚路径上的分量，静态线性分解不会局部自动修复。

参考资料

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§20.5。
Robert E. Tarjan, “Depth-First Search and Linear Graph Algorithms,” SIAM Journal on Computing 1(2), 1972, pp. 146–160。
Micha Sharir, “A Strong-Connectivity Algorithm and Its Applications in Data Flow Analysis,” Computers & Mathematics with Applications 7(1), 1981, pp. 67–72。

形式陈述 ​

反向链接

形式陈述