强连通分量Kosaraju与Tarjan算法对比

可视化演示

强连通定义

先从城市规划师的第一课说起。你看地图时，会注意到有些路口彼此“锁死”在一起：从 A 出发，沿着单行道能到 B；从 B 出发，也能绕回 A。这样的路口多了，就形成一个内部四通八达、与外界通过单行道衔接的“环形街区”。在数学上，这种只存在于有向图中的现象，就叫强连通分量，英文缩写 SCC。注意，无向图里的“连通块”不叫强连通分量——因为那里的道路是双向的，讲故事的前提完全不同。

把概念说得更精确一些：在有向图中，若顶点 u 存在一条路径走到 v，且 v 也存在一条路径走回 u，我们就说 u 和 v 相互可达。把所有相互可达的顶点尽可能大地收拢在一起，得到的顶点集合就是一个强连通分量。“尽可能大”这三个字很重要，它意味着你不能在这个集合里再塞进任何一个顶点还能保持两两互相可达，所以每个分量都是“极大”的。

既然每个顶点都恰好属于一个分量，全图的顶点就被这些环形街区干净地划分成了若干组。一个由 6 个路口组成的有向图，可能被划分成 3 个街区、3 个独行客，也可以是一个大圈套若干散点。这个划分关系写成公式就是：

$$\displaystyle V=\bigcup_{i=1}^{k}C_i,\qquad C_i\cap C_j=\varnothing\ (i\neq j)$$

1. 全集覆盖：所有分量的并集等于整个顶点集合 V，说明每个顶点都要“落户”到某个街区分量中。

$$\displaystyle V=\bigcup_{i=1}^{k}C_i$$

2. 不相交：任意两个不同分量之间没有公共顶点，保证划分不重不漏。

$$\displaystyle C_i\cap C_j=\varnothing\ (i\neq j)$$

3. 分量个数 k：k 就是全图被划分出的街区数量，也是后续缩点后新图的节点数。

$$\displaystyle k=|V'|$$

回到城市地图：识别出这些环形街区，等于拿到了一张城市的“治安分区图”。下一步，我们就要用两种巡逻方案把这些街区逐一找出来。

Kosaraju算法

市长决定派一支考察队彻底摸清城市。老派侦探的做法很稳妥：第一天，考察队沿着每条单向街道一路探到底，每离开一个路口就记下“收队时间”；晚上回来，把地图上的每条街道方向全部反过来，画一张“反向地图”；第二天，按收队时间从晚到早的顺序，从对应路口出发走反向地图，每趟能到达的所有路口正好拼成一个环形街区。这个两趟巡逻方案，就是 Kosaraju 算法。

对应到技术上：第一遍在原图上做深度优先搜索（DFS，可以理解为沿街一路走到头再掉头），记录每个顶点完成探索的时间戳，即完成时间；第二遍在反图上按完成时间从大到小选取起点再做 DFS。每一趟第二遍 DFS 访问到的顶点集合，恰好是一个强连通分量。

为什么这个“刁钻”的顺序会奏效？关键引理是：如果存在从分量 C1 指向 C2 的有向边，那么 C1 中顶点的最大完成时间一定大于 C2 中顶点的最大完成时间。于是第一遍 DFS 结束后，完成时间最大的分量一定是“源头”分量——它在反图上没有其他分量能干扰它，第二遍 DFS 就能把它完整地走成一个街区，然后逐个击破。

$$\displaystyle C_1\to C_2 \implies f_{\max}(C_1)>f_{\max}(C_2)$$

1. 分量间有向边：$C_1\to C_2$ 表示存在一条有向边，从 C1 里的某个顶点指向 C2 里的某个顶点。

$$\displaystyle C_1\to C_2$$

2. 最大完成时间：$f_{\max}(C_1)$ 取 C1 内所有顶点在第一遍 DFS 中完成时间的最大值。

$$\displaystyle f_{\max}(C_1)=\max_{v\in C_1}f(v)$$

3. 顺序结论：起点的最大完成时间大于终点，所以按完成时间降序处理时，先处理的是“没有入边来自未处理分量”的分量。

$$\displaystyle f_{\max}(C_1)>f_{\max}(C_2)$$

回到城市故事：考察队用两趟“笨功夫”，却换来极其稳健的结果。Kosaraju 的正确性不依赖任何复杂的魔法，只要两次 DFS 都按规矩走完，每个环形街区都会乖乖现形。它思路清晰、不容易写错，代价则是要多准备一张反向地图。

Tarjan算法

年轻探员觉得两趟巡逻太费鞋底，他发明了“一趟走完”的窍门：随身带一个记事本，每到一个新路口就编一个递增的门牌号（发现时间 dfn），同时在旁边记一张“回溯纸条”（low 值）——纸条上写的是一路上能绕回到的最早门牌号。每当走到一条回头路，发现能绕回更早的路口，他就更新纸条。当某个路口发现自己的门牌号和纸条上的数字一致时，说明这个路口就是某个环形街区的“圆心”，把记事本上属于这个街区的一串路口全部圈出来即可。

技术上说，Tarjan 算法维护两个关键数组：dfn[u] 是顶点 u 被发现的时间戳；low[u] 是 u 的子树通过一条“返回边”（指向栈中已访问顶点的边）能追溯到的最早发现时间。DFS 过程中，对每个邻接点 v 分类处理：若 v 未被访问，递归进入，返回后用 low[v] 更新 low[u]；若 v 已在栈中，则用 dfn[v] 更新 low[u]。当 dfn[u] 等于 low[u] 时，从栈顶一路弹出到 u，这批顶点就是一个强连通分量。

low 值的计算公式可以写成：

$$\displaystyle \operatorname{low}(u)=\min\left\{\operatorname{dfn}(u),\ \min_{\substack{v\in\text{stack}\\(u,v)\in E}}\operatorname{dfn}(v),\ \min_{\substack{v=\operatorname{son}(u)}}\operatorname{low}(v)\right\}$$

1. 初始值：low 的起点就是自己的发现时间，表示“最保守情况下我只能追溯到自己”。

$$\displaystyle \operatorname{low}(u)=\operatorname{dfn}(u)$$

2. 返回边更新：邻接点 v 已在栈中时，说明 v 是 u 的“祖先方向”的回边，用更小的 dfn(v) 压低 low(u)。

$$\displaystyle \operatorname{low}(u)=\min(\operatorname{low}(u),\operatorname{dfn}(v))$$

3. 树边回溯：对未访问的儿子 v，递归返回后用它的 low(v) 继续压低 low(u)，把子树里能追溯到的门牌号传上来。

$$\displaystyle \operatorname{low}(u)=\min(\operatorname{low}(u),\operatorname{low}(v))$$

判定一个顶点是否为某个 SCC 的“根”，就看下面的等式是否成立：

$$\displaystyle \operatorname{dfn}(u)=\operatorname{low}(u)\ \Longleftrightarrow\ u\text{ 是一个SCC中最早被发现的顶点}$$

1. 相等含义：dfn(u) 等于 low(u)，说明整棵子树找不到指向更早祖先的返回边。

$$\displaystyle \operatorname{dfn}(u)=\operatorname{low}(u)$$

2. 根的身份：这样的 u 正是街区的“圆心”，即以 u 为根的 DFS 子树自成一个完整分量。

$$\displaystyle u=\text{root of SCC}$$

3. 弹栈成块：从栈顶弹出直到 u 为止的所有顶点，它们都属于这个 SCC。

$$\displaystyle \text{pop until }u\ \Rightarrow\ \text{one SCC}$$

回到巡逻故事：年轻探员用一张不断更新的小纸条，省掉了反向地图和第二趟巡逻。单遍 DFS 就能把环形街区逐个“圈”出来，这正是 Tarjan 算法被称为“单遍算法”的原因。

算法对比

两位“侦察员”最终都能给出相同的街区清单，但风格迥异。老派侦探（Kosaraju）提前准备反向地图，走两趟，准备工作花销大但每一步都直白；年轻探员（Tarjan）依赖一张回溯纸条做判据，一趟走完，脑力开销藏在 low 值的更新规则里。我们逐一对比四个维度。

时间复杂度：两者都是线性复杂度，但 Kosaraju 的实际开销约为两趟 DFS 加上反图构建；Tarjan 只有一趟 DFS 加上常数级的栈操作。写成公式便是：

$$\displaystyle T_{\mathrm{Kosaraju}}\approx 2\cdot\Theta(V+E),\qquad T_{\mathrm{Tarjan}}\approx\Theta(V+E)$$

1. Kosaraju 的代价：两遍完整 DFS，加上构建反图的 O(V+E) 时间。

$$\displaystyle T_{\mathrm{Kosaraju}}\approx 2\cdot\Theta(V+E)$$

2. Tarjan 的代价：一遍 DFS 内同时完成发现与回溯判断。

$$\displaystyle T_{\mathrm{Tarjan}}\approx\Theta(V+E)$$

3. 渐近相同：去掉常数后两者都是线性，这也是它们能处理百万级顶点图的基础。

$$\displaystyle O(V+E)$$

空间开销：Kosaraju 需要为每个顶点存储完成时间，还要额外存储一张反图（邻接表翻倍）；Tarjan 只需一个 DFS 栈和 dfn/low 两个数组，空间更紧凑。直觉与出错率：Kosaraju 的“两次遍历、反图顺序”非常直观，几乎不会写错；Tarjan 则需要透彻理解 low 的三种更新规则，稍不留神就会把 dfn[v] 和 low[v] 用混。

结论很清晰：面试和工程实践中，Tarjan 因常数小、空间省而更受青睐；但 Kosaraju 作为“最不容易写错的 SCC 算法”，在快速原型和教学场景中永远占有一席之地。两套方案就像“稳妥”与“聪明”两种风格，没有绝对优劣，只有场景匹配。

缩点DAG

找出所有环形街区之后，城市规划进入下一步：把每个街区抽象成一个“地铁站”，街区之间的单向街道变成地铁线路。这样一来，原本错综复杂的城市道路网，被压缩成一张简化的线路图。更妙的是，这张线路图不可能再有环——如果两条线路能构成环，那环上的街区早就该合并成一个更大的强连通分量了。

技术操作叫“缩点”：把每个 SCC 看作一个超节点，原图中连接不同分量的边保留为超节点之间的有向边；分量内部的边全部丢弃。缩点后得到的新图记作 G'，它一定是无环的，所以可以直接做拓扑排序，为后续的 DP、最长路径等算法铺路。

$$\displaystyle G'=(V',E'),\qquad V'=\{C_1,\dots,C_k\},\qquad (C_a,C_b)\in E'\iff \exists\,u\in C_a,\ v\in C_b,\ (u,v)\in E$$

1. 超节点集合：V' 中每个元素是原图的一个强连通分量，节点数量显著减少。

$$\displaystyle V'=\{C_1,\dots,C_k\}$$

2. 超边条件：只要原图存在一条从分量 Ca 内某顶点指向 Cb 内某顶点的边，就在两个超节点之间连一条有向边。

$$\displaystyle (C_a,C_b)\in E'\iff \exists\,u\in C_a,\ v\in C_b,\ (u,v)\in E$$

3. 无环保证：若 G' 有环，环上的超节点会因互相可达而被合并，矛盾，因此 G' 必为 DAG。

$$\displaystyle G'\text{ is a DAG}$$

回到城市：有了地铁线路图，后续的拓扑排序和动态规划就像在规整的线路上排班，清晰明了。缩点让我们能从“认识每个街区”升级到“规划城市骨架”。

应用分析

识别出环形街区并完成缩点后，这套方法立刻有了用武之地。现实世界的许多系统，都可以建模成一张大网，而强连通分量就是网中的“硬核结构”。

编译器控制流分析：编译器的控制流图（CFG）中，循环本质上就是一个强连通区域。AI 编译器（如 TVM、XLA）在调度深度学习算子时，会先做 SCC 检测，把计算图中的环状依赖识别出来，再决定循环展开、算子融合等优化策略。比如 LSTM 展开后形成的带环子图，SCC 分析能帮助编译器安全地重排执行顺序。

社交网络圈子挖掘：社交平台上的“互关”关系构成有向图，互相可达的好友集合就是一个小圈子。用 SCC 切分后，再对每个圈子做社区发现和推荐，能让“铁粉圈”被整体识别，消息触达和好友推荐都更精准。

Web 页面分析：网页之间的超链接构成一张巨型有向图。互相引用的网页簇（例如内容农场之间互相导流）会被 SCC 算法识别出来，搜索引擎可以据此分析链接环、评估页面权重，避免被刷量页面绑架排序结果。

无论哪个场景，都依赖同一个基本事实——所有分量的顶点数加起来恰好等于全图顶点数：

$$\displaystyle \sum_{i=1}^{k}|C_i|=|V|$$

1. 分量大小：|C_i| 是第 i 个强连通分量包含的顶点个数。

$$\displaystyle |C_i|$$

2. 总和为全图规模：所有分量顶点数加起来等于原图顶点总数，不重不漏。

$$\displaystyle \sum_{i=1}^{k}|C_i|=|V|$$

3. k 的定位：k 既是分量个数，也是缩点后 DAG 的节点数，是衡量原图“冗余度”的直观指标。

$$\displaystyle k=|V'|$$

回到城市的比喻：无论是编译器调度计算图中的循环，还是社交平台发现互相关注的圈子，我们做的都是同一件事——先用 Kosaraju 或 Tarjan 找出所有环形街区，再把这些街区压缩成地铁站，在一张干净的无环网络上做进一步的决策。理解 SCC，你就拥有了一件“剖析任意有向图骨架”的利器。

AI 应用场景

Python 演示

def kosaraju(n, graph):    visited = [False] * n    order = []     def dfs1(u):        visited[u] = True        for v in graph[u]:            if not visited[v]:                dfs1(v)        order.append(u)     for u in range(n):        if not visited[u]:            dfs1(u)     rev = [[] for _ in range(n)]    for u in range(n):        for v in graph[u]:            rev[v].append(u)     comp = [-1] * n     def dfs2(u, cid):        comp[u] = cid        for v in rev[u]:            if comp[v] == -1:                dfs2(v, cid)     cid = 0    for u in reversed(order):        if comp[u] == -1:            dfs2(u, cid)            cid += 1    return comp, cid  def tarjan(n, graph):    dfn = [0] * n    low = [0] * n    stack = []    on_stack = [False] * n    comp = [-1] * n    cid = 0    clock = 0     def dfs(u):        nonlocal clock, cid        clock += 1        dfn[u] = low[u] = clock        stack.append(u)        on_stack[u] = True        for v in graph[u]:            if dfn[v] == 0:                dfs(v)                low[u] = min(low[u], low[v])            elif on_stack[v]:                low[u] = min(low[u], dfn[v])        if dfn[u] == low[u]:            while True:                x = stack.pop()                on_stack[x] = False                comp[x] = cid                if x == u:                    break            cid += 1     for u in range(n):        if dfn[u] == 0:            dfs(u)    return comp, cid  if __name__ == "__main__":    n = 6    graph = [[1], [2], [0, 3], [4], [3, 5], []]    ck, k = kosaraju(n, graph)    ct, t = tarjan(n, graph)    print("Kosaraju:", ck, "count:", k)    print("Tarjan:", ct, "count:", t)

1. order.append(u)在 DFS 回溯时记录“收队时间”，Kosaraju 第一遍全靠它排序
2. rev[v].append(u)把每条边反向，构造反图这步是 Kosaraju 的灵魂
3. for u in reversed(order):按完成时间从大到小取起点，顺序反了结果就错了
4. if comp[v] == -1:第二遍 DFS 遇到未归属顶点就继续深入，一次收一个 SCC
5. dfn[u] = low[u] = clockTarjan 的时间戳初始化，发现时间与回溯纸条同时起步
6. low[u] = min(low[u], low[v])树边回溯：儿子能绕回更早，父亲也继承这个信息
7. elif on_stack[v]: low[u] = min(low[u], dfn[v])返回边必须用 dfn[v] 而不是 low[v]，这是最常见的写错点
8. if dfn[u] == low[u]:门牌号等于回溯纸条，确认自己是街区的根，开始弹栈

常见误区

面试题