连通分量与Tarjan算法

可视化演示

什么是强连通分量

聚会进行到一半，你站在角落观察：有三五个人自成一个小圈，你从圈里任何一个人出发，让他沿着“自己认识谁”这条有向的朋友链去传话，居然能绕回圈里任意一个人。这种“无论从谁起跑，都能互相找到彼此”的人群，就是我们要找的主角——强连通分量（SCC）。

在计算机科学的图论中，这种关系被严格定义：有向图中两个顶点u、v，如果u能沿有向边到达v，v也能沿有向边到达u，就说它们强连通。所谓强连通分量，就是满足“任意两点都强连通”的极大顶点集合。注意“极大”二字：一旦某个圈子满足条件，就不能再塞进任何别的顶点，否则圈子就“不铁”了。

$$\forall u, v \in C, \quad u \rightsquigarrow v \wedge v \rightsquigarrow u$$

1. 任意两点：对强连通分量C中的任意两个顶点u和v，都要求满足下述性质，一个都不能例外。

$$\forall u, v \in C$$

2. 双向可达：u能沿着有向边组成的路径到达v，同时v也能沿着路径到达u，两个方向缺一不可。

$$u \rightsquigarrow v \wedge v \rightsquigarrow u$$

回到聚会的例子，强连通分量可以看成“最铁的小圈子”，但圈子之间可能还有单向的认识关系：A圈的人认识B圈的人，B圈却没人认识A圈的人。理解了这个基础，下一步我们看怎么用算法把圈子自动化地圈出来。

图的基础概念与可达性

在识别圈子之前，你得先有一份“聚会通讯录”——这对应图论里的有向图。通讯录里每个人是一个顶点，一条“A认识B”的记录就是一条从A指向B的有向边。所有边连起来，就构成了整个聚会的社交网络。要判断两个人是否在同一个铁圈子里，核心看“可达性”：沿着有向边一步步走，能不能从u走到v。

可达性有两个方向：如果只能单向到达，比如u能到v但v到不了u，它们就只是“单相思”，够不上强连通；只有u能到v、v也能到u，才是真正的“双向奔赴”。在无向图里，“连通”简单得多，因为边没有方向；但有向图里方向就是人品，方向不对，路就断了。

$$u \rightsquigarrow v \wedge v \rightsquigarrow u \Rightarrow u, v \in C$$

1. 前提条件：u能到达v，且v能到达u，这是判断两个顶点属于同一SCC的充要条件。

$$u \rightsquigarrow v \wedge v \rightsquigarrow u$$

2. 结论归属：当这个双向可达条件成立时，u和v必然属于同一个强连通分量C。

$$u, v \in C$$

通讯录上的名字和箭头，就是算法处理的对象。有了这股“关系网”，接下来介绍的主人公Tarjan，将教我们用一张号码牌和一句悄悄话，把铁圈子一个个揪出来。

Tarjan核心：dfn与low

Tarjan算法的灵感，来自聚会主持人发号码牌。主持人从1号开始，按“第一次走进会场”的顺序给每个宾客发号码牌，这个号码就是dfn（发现时间）。每个宾客还握着一个秘密数字low，代表“我通过自己和朋友的悄悄话，能回溯到的最早号码”。刚进门时，low和自己的dfn一样。

宾客们按“深度优先”的方式互相串门：你刚认识朋友A，就立刻去A的朋友圈里逛；逛完回来，再根据朋友们的low压低自己的low——如果朋友能回到3号，我也能借他的路子回到3号，我的low就变成3。如果某条边指向一个还在会场里（栈中）的老熟人，说明找到一条回边，可以直接把low压到那个熟人的dfn。

$$\operatorname{low}[u] = \min\left(\operatorname{dfn}[u],\ \min_{v \in \text{child}(u)} \operatorname{low}[v],\ \min_{k \in \text{back}(u)} \operatorname{dfn}[k]\right)$$

1. 自身编号：low的初始值就是节点自己的入场编号dfn[u]，表示“目前我只回到自己这里”。

$$\operatorname{low}[u] = \operatorname{dfn}[u]$$

2. 树边传递：对每个DFS树孩子v，用low[v]来尝试压低low[u]，因为孩子能回到的地方，通过树边我也能到。

$$\min_{v \in \text{child}(u)} \operatorname{low}[v]$$

3. 回边回溯：对指向栈中节点k的回边，用dfn[k]压低low[u]，因为k还在等待确认，说明我们同属一个圈子。

$$\min_{k \in \text{back}(u)} \operatorname{dfn}[k]$$

号码牌越小的宾客，越是圈子里的“元老”。当所有人的low都传完，那些low值等于自己号码牌的人，就是圈子的主心骨——下一节我们看怎么用它决定“开圈”的时机。

辅助栈与根节点判定

主持人手上有张“待定名单”——栈。凡是已经入场、但还没被确认属于哪个铁圈子的人，都按入场顺序压在栈里。栈里的顺序，恰好就是深度优先串门的路径。

判断“开圈”的时机很简单：当一个宾客u的low终于传回来，等于他自己的dfn时，说明他是这个圈子里最早入场的“元老”，圈子里再没人能通过回边回到更早的号码。这时，从栈顶一路弹出，直到弹出u本身，弹出的这一摞人，就是同一个强连通分量。

$$\operatorname{dfn}[u] = \operatorname{low}[u]$$

1. 编号相等：当节点u的dfn和low相等，说明它无法通过任何回边回到更早的节点。

$$\operatorname{dfn}[u] = \operatorname{low}[u]$$

2. 根节点判定：此时u是自己所在SCC的根；从栈顶弹出元素直到u为止，这些元素共同构成一个SCC。

$$\text{从栈顶弹出直到 } u \text{ 的节点为同一SCC}$$

用栈来“圈人”的好处是天然正确：深度优先的路径上，能在回边帮助下绕回u的点，一定都压在u上面的栈里。弹栈一次，圈里人一个不多、一个不少。

Tarjan算法全流程

现在把整个流程串起来，就像组织一场“深度优先的串门大会”。主持人从1号开始，依次检查每个还没入场的宾客；对每个宾客，执行同一套三步动作：入场牌、串门问low、开圈弹栈。

具体流程是：初始化所有dfn和low为0，准备空栈；从每个未访问顶点出发做DFS；进入节点时设dfn=low=timer（timer每次加一）；遍历所有邻边：若邻点未访问，递归DFS并用low[邻]压低low；若邻点在栈中，用dfn[邻]压低low；回溯后若dfn[u]==low[u]，弹栈输出一个SCC。整张图扫完，所有SCC就都拿到了。

$$T(V, E) = O(V + E)$$

1. 顶点开销：每个顶点恰好被访问一次，入栈、出栈各一次，贡献O(V)。

$$O(V)$$

2. 边开销：每条边在遍历邻接表时被检查一次，贡献O(E)。

$$O(E)$$

一次串门大会，就把所有铁圈子一次圈完。Tarjan聪明之处在于，把“判断圈子”完全融入了DFS的回溯过程，不需要额外的全局信息。这就是它成为面试常客的原因。

Kosaraju的双DFS

如果Tarjan是“入场发牌、串门传话”的主持人，Kosaraju就像另一个更慢条斯理的主办方：他先记录每位宾客的离场时间，再举办一场“反向点名”的终场派对。

第一遍DFS：在原图上做深度优先遍历，每离开一个节点就记下它的完成时间（离场号）。注意，这个离场号有个重要性质：一个SCC的根，通常拥有整个分量里最大的离场号。第二遍DFS：把原图所有边反向，得到反图G^T；拿着离场号从大到小的顺序，在反图上挨个做DFS——每次DFS能访问到的所有节点，恰好就是一个完整的SCC。

$$G^T = (V, E^T),\quad E^T = \{(v, u) \mid (u, v) \in E\}$$

1. 反向图顶点：反图G^T与原图拥有完全相同的顶点集合V，人还是那些人。

$$G^T = (V, E^T)$$

2. 反向边：原图每条有向边(u,v)，在反图中变成(v,u)，关系方向完全颠倒。

$$E^T = \{(v, u) \mid (u, v) \in E\}$$

为什么有效？因为在原图里，SCC内部的路径在反图里依然连通，而分量之间的边方向反转后，“先离开的分量”再也走不回“后离开的分量”，于是每次DFS恰好圈住一个SCC。思路清晰，代价是跑两遍DFS、还要建反图。

两种算法复杂度对比

两个主持人一个“单刀直入”，一个“两遍成事”，账本记得一样漂亮：时间上，Tarjan只做一次DFS，Kosaraju做两次但都是线性；空间上，Tarjan需要一个辅助栈和两个数组，Kosaraju需要额外存反图。两者的渐进复杂度完全相同。

但“纸面一样”不等于“手感一样”。Tarjan常数小、内存省，一次遍历就地出结果，适合追求极致性能的工程场景；Kosaraju思路简单、正确性容易证明，而且两遍遍历天然适合“先并行算离场号、再并行分圈”的分布式实现。

$$O(V + E) \quad \text{与} \quad O(V + E)$$

1. 时间量级：Tarjan和Kosaraju的时间复杂度均为O(V+E)，都能在线性时间内求出全部SCC。

$$O(V + E)$$

2. 空间量级：两者空间也均为O(V+E)，Tarjan省在不用存反图，Kosaraju省在思路更直接。

$$O(V + E)$$

选谁取决于场景：比赛和面试爱考Tarjan，因为它一镜到底；工业界做超大规模图处理时，Kosaraju的可并行性反而更吃香。理解了差异，就能在“快与稳”之间做聪明的取舍。

SCC的实际应用

聚会散场后，主持人的记录本还有大用处。SCC最大的价值在于“缩点”：把每个强连通分量压缩成一个超级节点，分量之间的边保留，得到的新图一定是有向无环图（DAG）。环变成了点，秩序就出来了。

三大应用场景随之而来：社交网络上，SCC就是天然的社区核心，互关互转的用户聚成圈子，社区发现可以先从SCC种子扩展；程序分析中，函数调用图的SCC就是递归调用环，编译器会优先处理环内代码；构建系统里，包依赖出现环会导致死锁，用SCC探测环并缩点后，可以按拓扑序安装依赖。

$$G_{\text{SCC}} = (C, E_C),\quad (C_i, C_j) \in E_C \iff \exists\, u \in C_i, v \in C_j,\ (u, v) \in E$$

1. 缩点建图：把每个SCC当作一个超级节点，所有超级节点组成新图节点集合C。

$$G_{\text{SCC}} = (C, E_C)$$

2. 分量间边：当原图中存在从Ci某点到Cj某点的边时，缩点图中建立Ci到Cj的有向边。

$$(C_i, C_j) \in E_C \iff \exists\, u \in C_i, v \in C_j,\ (u, v) \in E$$

从“谁和谁亲密”到“谁能先安装”，SCC把一团乱麻的互相依赖整理成条理清晰的DAG。这正是图论算法落地为工程工具的典型路径：先找环，再排序，最后自动化。

AI 应用场景

Python 演示

def tarjan_scc(graph):    n = len(graph)    dfn = [0] * n          # 入场顺序号    low = [0] * n          # 最早回溯号    in_stack = [False] * n    stack = []    comps = []    timer = 0     def dfs(u):        nonlocal timer        timer += 1        dfn[u] = low[u] = timer        stack.append(u)        in_stack[u] = True        for v in graph[u]:            if dfn[v] == 0:        # 树边: 邻点没入过场                dfs(v)                low[u] = min(low[u], low[v])            elif in_stack[v]:      # 回边: 邻点还在栈中                low[u] = min(low[u], dfn[v])        if low[u] == dfn[u]:       # 自己是圈子的根            comp = []            while True:                x = stack.pop()                in_stack[x] = False                comp.append(x)                if x == u:                    break            comps.append(comp)     for i in range(n):        if dfn[i] == 0:            dfs(i)    return comps  if __name__ == "__main__":    # 图: 0->1->2->0 构成SCC{0,1,2}, 3->4->3 构成SCC{3,4}    graph = [[1, 3], [2], [0], [4], [3]]    print("SCCs:", tarjan_scc(graph))

1. dfn[u] = low[u] = timer入场瞬间dfn和low先设置成同一个号码，low之后会被压低。
2. if dfn[v] == 0:邻点从未入过场，说明这是一条树边，先递归再回传low。
3. elif in_stack[v]: low[u] = min(low[u], dfn[v])邻点还在栈里，说明找到回边，用dfn压低low。
4. if low[u] == dfn[u]:低值等于入场号，u是圈子的根，触发弹栈。
5. x = stack.pop()从栈顶依次弹出宾客，直到弹回根节点，这一摞人就是一个SCC。

常见误区

面试题