数据结构与算法 / 系统课时
Tarjan 怎样找强连通分量
Tarjan 怎样找强连通分量
在有向图中,若一组顶点彼此都能沿有向边互相到达,它们构成一个强连通分量。Tarjan 算法只做一次 DFS,就能借助访问时间、low 值和栈判断哪些顶点应被归为同一分量,并在线性复杂度内完成分解。
学习目标
- 理解
dfn、low与栈在 Tarjan 算法中的职责 - 能判断一个 DFS 节点何时成为强连通分量的根
- 能实现并验证 Tarjan 强连通分量算法
dfn 与 low 分别记录什么
dfn[u] 表示顶点 u 第一次被 DFS 访问的时间戳,数值越小代表越早进入。low[u] 表示从 u 出发,经过当前 DFS 子树中的边以及指向“仍在栈中顶点”的回边后,能够到达的最小 dfn。
二者的差异很重要:dfn 一旦赋值就不再变化,而 low 会随着对子节点和回边的探索不断减小。如果 DFS 完成时满足 low[u] == dfn[u],说明 u 无法通过当前尚未出栈的路径回到更早的顶点,因此 u 正是一个强连通分量在 DFS 树中的根。

栈只保存“已经访问但尚未归属某个强连通分量”的顶点。边指向一个已经出栈的顶点时,不能再用它更新当前 low,因为那个顶点已经属于此前完成的分量。
low 值如何更新
DFS 处理从 u 指向 v 的边时,分三种情况:
v未访问:先递归访问v,返回后执行low[u] = min(low[u], low[v])。v已访问且仍在栈中:说明这条边仍可能连接当前未完成的强连通结构,执行low[u] = min(low[u], dfn[v])。v已访问但已出栈:忽略这条边,不更新low[u]。
第二种情况使用的是 dfn[v],而不是 low[v]。因为此时处理的是一条直接指向栈内顶点的边,需要记录“当前节点能直接回到多早的已访问位置”,不能把对方通过其他路径能够到达的位置无条件传播过来。
完整实现与输出
下面的实现会返回所有强连通分量。为了让输出稳定,示例最后对每个分量和分量列表进行了排序;算法本身并不要求这种排序。
def tarjan_scc(graph):
n = len(graph)
index = 0
dfn = [-1] * n
low = [0] * n
stack = []
in_stack = [False] * n
components = []
def dfs(u):
nonlocal index
dfn[u] = low[u] = index
index += 1
stack.append(u)
in_stack[u] = True
for v in graph[u]:
if dfn[v] == -1:
dfs(v)
low[u] = min(low[u], low[v])
elif in_stack[v]:
# 只用仍在当前未完成 SCC 范围内的回边更新 low
low[u] = min(low[u], dfn[v])
if low[u] == dfn[u]:
component = []
while True:
v = stack.pop()
in_stack[v] = False
component.append(v)
if v == u:
break
components.append(component)
for u in range(n):
if dfn[u] == -1:
dfs(u)
return components
if __name__ == "__main__":
graph = [
[1], # 0 -> 1
[2, 3], # 1 -> 2, 3
[0], # 2 -> 0
[4], # 3 -> 4
[3], # 4 -> 3
]
result = tarjan_scc(graph)
normalized = sorted(sorted(component) for component in result)
print(normalized)预期输出
[[0, 1, 2], [3, 4]]顶点 0、1、2 彼此可达,因此形成一个强连通分量;3、4 互相可达,形成另一个分量。边 1 -> 3 只说明前一个分量可以到达后一个分量,并不会让两个分量合并。
为什么整体是线性复杂度
Tarjan 中每个顶点只会进入 DFS 一次、入栈一次、出栈一次;每条有向边也只在遍历邻接表时检查一次。因此时间复杂度为 ,空间复杂度为 ,其中邻接表占 ,辅助数组与栈占 。
实现时最关键的边界是“是否仍在栈中”。如果把所有已访问顶点都拿来更新 low,就会错误地把已经完成的分量重新连接进当前分量。另一个常见错误是弹栈时只弹出根节点;正确做法是从栈顶持续弹出,直到弹出满足 low[u] == dfn[u] 的根 u,这些顶点共同组成一个完整强连通分量。
Tarjan 适合先压缩有向图中的环结构:把每个强连通分量缩成一个点后,得到的分量图一定是 DAG,后续可以继续做拓扑排序、依赖分析或可达性推理。