数据结构与算法 / 系统课时

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 树中的根。

Tarjan 时间戳 lowlink 与出栈关系图

栈只保存“已经访问但尚未归属某个强连通分量”的顶点。边指向一个已经出栈的顶点时,不能再用它更新当前 low,因为那个顶点已经属于此前完成的分量。

low 值如何更新

DFS 处理从 u 指向 v 的边时,分三种情况:

  1. v 未访问:先递归访问 v,返回后执行 low[u] = min(low[u], low[v])。
  2. v 已访问且仍在栈中:说明这条边仍可能连接当前未完成的强连通结构,执行 low[u] = min(low[u], dfn[v])。
  3. v 已访问但已出栈:忽略这条边,不更新 low[u]。

第二种情况使用的是 dfn[v],而不是 low[v]。因为此时处理的是一条直接指向栈内顶点的边,需要记录“当前节点能直接回到多早的已访问位置”,不能把对方通过其他路径能够到达的位置无条件传播过来。

完整实现与输出

下面的实现会返回所有强连通分量。为了让输出稳定,示例最后对每个分量和分量列表进行了排序;算法本身并不要求这种排序。

python
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)

预期输出

text
[[0, 1, 2], [3, 4]]

顶点 0、1、2 彼此可达,因此形成一个强连通分量;3、4 互相可达,形成另一个分量。边 1 -> 3 只说明前一个分量可以到达后一个分量,并不会让两个分量合并。

为什么整体是线性复杂度

Tarjan 中每个顶点只会进入 DFS 一次、入栈一次、出栈一次;每条有向边也只在遍历邻接表时检查一次。因此时间复杂度为 O(V+E)O(V+E),空间复杂度为 O(V+E)O(V+E),其中邻接表占 O(V+E)O(V+E),辅助数组与栈占 O(V)O(V)。

实现时最关键的边界是“是否仍在栈中”。如果把所有已访问顶点都拿来更新 low,就会错误地把已经完成的分量重新连接进当前分量。另一个常见错误是弹栈时只弹出根节点;正确做法是从栈顶持续弹出,直到弹出满足 low[u] == dfn[u] 的根 u,这些顶点共同组成一个完整强连通分量。

Tarjan 适合先压缩有向图中的环结构:把每个强连通分量缩成一个点后,得到的分量图一定是 DAG,后续可以继续做拓扑排序、依赖分析或可达性推理。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Tarjan 怎样找强连通分量

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通