Tarjan算法详解：一次DFS求解强连通分量、割点与桥

遇到带环的图论问题，很多人第一反应是“跑一遍拓扑排序试试”，但拓扑排序只适合有向无环图，一旦图里出现强连通分量，结果立刻乱套。这时候就要请出 Tarjan 算法。

Tarjan 是基于深度优先搜索（DFS）的图论算法，专门用来求有向图的强连通分量，顺手还能解决无向图的割点、桥、双连通分量等问题。核心思路非常朴素：在一次 DFS 遍历过程中，用“时间戳”和“栈”区分出哪些节点互相可达。你只要理解了两个关键数组的含义，剩下就是模版记忆的问题。这篇就来拆一拆 Tarjan 的底层逻辑、完整推导、代码实现，以及我实际调试中踩过的那些坑。

1. 在动手写代码之前：搞清楚 Tarjan 到底在做什么

1.1 一个绕不开的背景：强连通分量

强连通分量的定义一句话就能讲清：在有向图里，如果一组节点两两之间都存在可达路径，这组节点就构成一个强连通分量。注意是“两两互相可达”，不是“有一个环串起来就行”。

举个生活化的例子。一个班级里的小团体，A认识B、B认识C、C也认识A，那这个三人组内部是互相联通的，就是一个强连通分量。如果有个人只单向认识团体里的某个人，团体里的人却不认识他，那他就没资格进这个分量。太严格了？严格就对了，图论里“互相可达”就是这么苛刻。

为什么强连通分量这么重要？因为在有向图中，强连通分量内部的所有节点本质上可以看作一个“大节点”。把每个强连通分量缩成一个点后，原图会变成一个无环图（DAG）。无环图就能用拓扑排序、动态规划这些成熟工具来处理了。比如课程安排中的先修关系检测环、程序调用链中的循环依赖检测、社交网络中挖掘紧密社区，背后都是“找强连通分量然后缩点”这套流程。

1.2 Tarjan的定位与独特优势

求强连通分量不止一种方法，常见的还有 Kosaraju 算法和 Tarjan 算法。Kosaraju 的思路是先正向 DFS 记录出栈顺序，再在反图上按出栈顺序逆序 DFS，两轮遍历就能分出强连通分量，理解起来直观，但它需要构建反图，空间开销多一份。

Tarjan 的优势是只需要一次 DFS，不用建反图，时间复杂度和空间复杂度都是 O(V+E)。代价是理解门槛高一点——它引入了“时间戳”和“回溯值”两个概念，初次接触很容易懵。但也正因为如此，很多竞赛选手和面试官更偏爱 Tarjan，写起来快，边界条件也没那么多。

一句话总结：Tarjan 是在一次 DFS 里，通过维护每个节点的两个标记，把强连通分量“切”出来。下面这两把钥匙就是全文的核心。

2. 两把核心钥匙：dfn时间戳与low值

2.1 DFS时间戳：给每个节点一个“序号”

dfn（discover finish number，发现时间戳）记录的是每个节点在 DFS 过程中被第一次访问到的顺序。假设从节点 0 开始 DFS，依次访问 0、1、3、4，那么 dfn[0]=1、dfn[1]=2、dfn[3]=3、dfn[4]=4。

时间戳的意义在于给“访问先后”一个可比较的数字。如果节点 u 的时间戳比节点 v 小，说明 u 更早被访问到，在 DFS 树中 u 更靠近根。这个数字是全局递增的，每个节点只会被赋值一次，之后就再也不会改变。

生活类比：餐厅排队取号。你是第 37 号顾客，这个号码在你进店那一刻就固定下来了，后面再多人排队，你的号也不会变。dfn 就是这个取号，记录的是“你什么时候进店的”，而不是“你什么时候离店的”。

2.2 low值：我能借力回溯到的最早祖先

low（lowest reachable dfn，可回溯的最早时间戳）是 Tarjan 最核心、最让人头疼的概念。通俗理解：从节点 u 出发，沿着 DFS 树往下走，再借助若干条“回边”（后向边），最多能“够到”的具有最小 dfn 值的节点的时间戳。

low[u] 的取值来自三个渠道：

• 初始化：low[u] = dfn[u]，每个人先只够得到自己。
• 树边更新：如果 u 有一个子节点 v，在 DFS 递归返回后，执行 low[u] = min(low[u], low[v])，意思是“我儿子能回溯到的祖先，我也能通过儿子够到”。
• 回边更新：如果 u 有一条边指向某个已访问且还在栈里的节点 v，执行 low[u] = min(low[u], dfn[v])，注意这里是 dfn[v] 而不是 low[v]，原因后面细说。

三条规则缺一不可，尤其第三条很容易写错。为什么回边要看 dfn[v] 而不是 low[v]？因为 low[v] 可能已经被更新为某个更早的时间戳，但那个更早的节点未必和 u 在同一个强连通分量里。如果拿 low[v] 去更新 low[u]，可能会把不同分量的节点“错误地搅和在一起”。回边能提供的最强承诺就是“我能直接走到 v，所以 v 的时间戳是我能确保的最低值”，至于 v 还能往上走多少，那是 v 自己的事，与 u 无关。这个细节是最容易写错且最难查 bug 的地方。

2.3 判定语义：dfn[u] == low[u] 是分量的根

有了 dfn 和 low，强连通分量的判定就变得非常优雅：在 DFS 回溯到某个节点 u 时，如果发现 dfn[u] == low[u]，说明 u 是整个强连通分量里“最早被访问到”的那个人，也就是这个分量的根。此时栈中从栈顶到 u 之间的所有节点，恰好构成一个独立的强连通分量。

为什么相等就能判定？想一下 low 的含义：low[u] 是 u 能通过 DFS 树和回边够到的最早节点。如果 dfn[u] == low[u]，说明 u 最多只能够到自己，它没办法通过任何路径回到更早的祖先。那所有在栈中且位于 u 之上的节点，都是 u 的后代，它们通过子树内的回边连成一个整体，但与更早的祖先彻底“断联”。断联处就是分量边界。

如果对这个判定条件还有疑惑，那就动手模拟一个简单图：三个节点 0->1、1->2、2->0，建议手推一遍所有 dfn 和 low 的变化过程。推完之后你会拍大腿：原来如此。

3. 手写一遍强连通分量求解：从伪代码到Python

3.1 算法流程的五个步骤

完整求解一个图的强连通分量，按下面五步走：

1. 初始化全局时间戳计数器、空栈、空的结果列表。每个节点的 dfn 和 low 都先置为 0，表示未访问。
2. 对每个未访问的节点调用 DFS。进入 DFS 时，给节点赋 dfn 和 low 的初始值，然后压入栈中，并在一个集合（或数组）标记该节点在栈中。
3. 遍历当前节点 u 的所有邻接边，对每个邻接节点 v 分三种情况处理：
   • v 未访问：递归 DFS 访问 v，回溯返回后，用 low[v] 更新 low[u]。
   • v 已访问且仍在栈中：用 dfn[v] 更新 low[u]。
   • v 已访问但不在栈中：说明 v 已经归入某个强连通分量，与 u 无关，直接忽略。
4. 递归回溯到 u 时，检查 dfn[u] == low[u] 是否成立。如果成立，就从栈顶开始弹栈，直到弹出 u 为止，弹出的所有节点归为一个强连通分量，合并放入结果。
5. 循环处理下一个未访问节点，直到所有节点都有 dfn 值。

这五步是整个 Tarjan 算法的骨架。注意第四步“弹到 u 为止”必须是后进先出，因为栈中 u 之上的节点全是 u 在 DFS 树中的后代，它们与 u 共享同一个分量，这是由 DFS 树的性质保证的。

3.2 一份可直接使用的Python实现

理解了流程之后，代码就很自然了。下面这份实现我加了不少注释，建议直接对照上面的五步读：

class TarjanSCC: def __init__(self, n, edges): self.n = n self.graph = [[] for _ in range(n)] for u, v in edges: self.graph[u].append(v) self.dfn = [0] * n self.low = [0] * n self.stack = [] self.in_stack = [False] * n self.timestamp = 0 self.sccs = [] self.belong = [-1] * n def run(self): for i in range(self.n): if self.dfn[i] == 0: self._dfs(i) return self.sccs def _dfs(self, u): self.timestamp += 1 self.dfn[u] = self.low[u] = self.timestamp self.stack.append(u) self.in_stack[u] = True for v in self.graph[u]: if self.dfn[v] == 0: self._dfs(v) self.low[u] = min(self.low[u], self.low[v]) elif self.in_stack[v]: self.low[u] = min(self.low[u], self.dfn[v]) # 回溯判断：当前节点是强连通分量的根 if self.dfn[u] == self.low[u]: component = [] while True: x = self.stack.pop() self.in_stack[x] = False self.belong[x] = len(self.sccs) component.append(x) if x == u: break self.sccs.append(component)

这个类封装了完整功能。其中belong数组记录每个原始节点被缩点后属于哪个分量，方便后续做缩点构图。注意run()方法里对每个未访问节点都调用_dfs，这是处理有向图中存在多个不连通部分的关键，漏了这一步会丢掉一部分分量。

3.3 手动模拟一个例子：眼见为实

空谈概念容易晕，用一个 6 节点的图完整推一遍。图结构如下：

• 0 -> 1
• 1 -> 2
• 2 -> 0（0、1、2 构成一个环）
• 1 -> 3
• 3 -> 4
• 4 -> 3（3、4 构成一个环）
• 4 -> 5
• 5 -> 5(自环，5 自己构成分量)

这个图预期分成三个强连通分量：{0,1,2}、{3,4}、{5}。

从节点 0 开始 DFS：

看到第 13 步可能有人疑惑：4 的 low[4]=4，dfn[4]=5，为什么不马上弹？因为 3 还在栈中，而且 4 可以通过回边到达 3，说明 4 和 3 应该同属一个分量。只有等回溯到 3 时，dfn[3]=low[3]=4，弹掉栈顶的 3 和 4，分量才完整。

这个例子完全可以手动跑一遍，跑通之后你自然就明白四个判定细节：为什么要用 dfn 更新 low、为什么检查的是 dfn==low、为什么 3 和 4 的弹出顺序是“先弹4再弹3”、为什么孤立节点也能单独成块。这些弄懂了，Tarjan 的强连通分量部分就过关了。

4. 拓展：Tarjan不只是强连通分量——割点、桥与双连通分量

4.1 割点判定：一个子树与祖先的“断弦”

很多初学者不知道，Tarjan 思想换到无向图上，稍微改一下判定条件，就能求割点和桥。

割点定义：无向连通图中，如果删除某个顶点以及它关联的所有边，图不再连通，这个顶点称为割点。日常场景比如通信网络中的关键路由器、交通路网中的必经路口，都要靠割点来定位单点故障风险。

利用 Tarjan 框架，在无向图上跑 DFS（注意无向图的边会被遍历两次，需要记录父亲边的编号避免反复走同一条边）后，割点判定分两种情况：

• 根节点：如果根节点在 DFS 树中有 2 个或更多子树，根就是割点。因为删除根后，这些子树之间没有其他边连通（否则在 DFS 时这些子树会被合并成一棵）。
• 非根节点：对于非根节点 u，如果存在一个子节点 v，满足 low[v] >= dfn[u]，则 u 是割点。low[v] >= dfn[u] 的含义是：v 所在的子树无法通过任何回边走到 u 的祖先节点，砍掉 u 后，这棵子树就彻底和祖先断联。

很多教材把割点条件写成low[v] >= dfn[u]，和强连通分量的dfn[u] == low[u]放在一起记忆很容易混。其实两种是不同的问题，别硬背，理解“>=”表示“子孙连不到祖先”即可。

4.2 桥的判定：严格不等式 low[v] > dfn[u]

桥（割边）的定义和割点类似，区别是删掉的是边而不是点。在判定桥上，Tarjan 有一个特别漂亮的结论：在 DFS 树中，如果对于树边 u->v，满足了 low[v] > dfn[u]，那么 u->v 就是一座桥。

“>”不是“>=”，这是和割点最大的区别。走到大于号说明：v 子树里哪怕是回边，也只能回到 v 自己在树中的后代节点，连 u 都够不到，更别说 u 的祖先。那 u->v 就是唯一连接双方的“独木桥”，断掉必然分裂。

重边的情况需要特别处理：如果 u 和 v 之间有多条直接边，那 u->v 就不该判断为桥，因为还有另一条平行边兜底。所以无向图实现时，不仅要记录“父节点是谁”，还要记录“父边的编号”，回边判定时跳过父边编号而非直接跳过父节点。这个细节不处理，重边图中会产出假桥。

4.3 双连通分量：边双与点双

求完了割点和桥，双连通分量几乎是白送的。

边双连通分量就是删除图中所有桥之后，剩下的每个连通块。做法：先用 Tarjan 找桥，标记桥边，然后 DFS 跳过桥边，每扫到一个连通块就是一个边双。边双内部的任意两条边之间都存在两条不相交的路径，稳定性很高。

点双连通分量稍麻烦一点，需要用“辅助栈存边”而不是存节点。求点双时，在 DFS 遍历过程中，每走一条树边就把边压入辅助栈；一旦发现 dfn[u] <= low[v]（与割点判定同源），就从辅助栈里弹出直到弹出当前边，弹出的这一包边连同它们关联的端点，构成一个点双分量。这里要注意一个节点可以属于多个点双，而每个边恰好属于一个点双，这跟强连通分量“节点划分”的逻辑不一样。

能把 Tarjan 用到这个程度，说明你已经能在线性时间内处理一整类“关键点、关键边、可靠子图”问题，这在工程里的价值不亚于学会一个独立算法。

5. 实际使用中踩过的坑：调试记录与排查方法

5.1 递归栈溢出：图的规模一大就崩

Python 实现的 Tarjan 天然依赖递归，处理几万节点的图时经常遇到RecursionError: maximum recursion depth exceeded。核心原因是 Python 默认递归深度限制在 1000 左右，而一条链状的图 DFS 深度轻松超过这个数。

解决思路有两个方向。一是调大递归限制：

import sys sys.setrecursionlimit(10**6)

这个方法简单，但不是治本的：C 语言风格的递归在 Python 里性能一般，而且真正的调用栈深度还能被系统限制，setrecursionlimit 只是一个“软限制”。二是把递归改成显式栈的迭代写法。迭代版稍微复杂，但对脆弱的 Python 递归环境更友好，生产环境中大规模图的处理建议直接上迭代版。

我个人经验是：写题、做实验用递归版完全没问题，但一旦数据规模超过 5 万节点，优先换迭代版，免得线上跑崩。

5.2 自环与孤立点：最容易漏掉的分量

自环在 Tarjan 里不会产生问题：节点 5 有自环时，DFS 会看到自己在栈中，用 dfn[5] 更新 low[5]，low 值不变，最后 dfn==low 正常弹栈。

孤立点也一样，它被循环入口的_dfs(i)访问，dfn、low 都是自己的值，弹栈时单独成块。所以 Tarjan 天然能把自环节点和孤立点处理成独立分量，不需要特判。

需要担心的是反向问题：有人为了“优化”写代码时跳过某些节点，或漏了循环入口，导致部分节点根本没有 dfn 值，分量就会丢。建议在收尾阶段打印每个节点的 dfn 和 low，一眼就能看出哪些节点没被访问。

5.3 有向图中“在栈中”的判断不能省

在强连通分量版本的 DFS 里，遍历到已访问的邻接节点 v 时，必须检查 v 是否在栈中。如果省略这个判断，无论 v 是否已经归入别的分量，都用 dfn[v] 去更新 low[u]，会把已经形成的分量错误地和当前节点连通起来，导致分组错误。

先看错误代码长什么样：

elif visited[v]: # 错误示范：忘记检查 in_stack self.low[u] = min(self.low[u], self.dfn[v])

再看典型报错现象：孤立节点被并进之前某个分量，或者同一个分量被重复拆成多块。有一个很隐蔽的情况是，图里存在跨分量的“横叉边”，这条边会让 low 值被污染，但图在拓扑结构上仍然能跑完，肉眼很难查出来。

排查方法很简单：检查低值，对每个分量打印内部节点，再手动验证它们是否两两可达。一旦发现某个分量里混入了不该有的节点，优先查的就是这个elif分支。

5.4 无向图重边导致的“假桥”

无向图求桥时，如果用“跳过父节点”而不是“跳过父边编号”的方式实现，重边场景下会把桥算错。举一个最简单的例子：两个节点 a、b 之间有两条直接边。显然删除其中任意一条，图仍然连通，所以不该有任何桥。但如果代码里 DFS 从 a 走到 b 时，无脑跳过“父节点 a”的那条边，当 b 尝试走另一条边回到 a 时，走的是“回边”而非“树边”，更新 low[b] = min(low[b], dfn[a])，最终 low[b] == dfn[a]，不会被判成桥。这是正确的。

但如果问题反过来：只有一条边的时候，b 在遍历时会遇到 a，此时 a 就是父节点，若直接跳过父节点，b 将没有任何回边可走，low[b] 保持为 dfn[b]。此时若再求桥，dfn[b] > dfn[a] 恒成立，于是把这条唯一的边判成桥，这没错。真正的坑往往出现在多层 DFS 后，父节点和祖先节点的判断搅在一起。

更稳妥的处理是：DFS 时记录每个节点从哪个“边编号”走过来。遍历到邻接边时，只跳过与父边编号相同的那一条，其他边哪怕是回到父亲的也正常使用。用编号而不是节点来判重，重边干扰就能完全排除。

5.5 常见问题速查表

排查 Tarjan 问题最有效的工具永远是“画图 + 手动模拟”。如果你发现某个例子跑出来的结果和自己预想不一致，就把 dfn、low、栈的变化逐步打印出来，对照本表的模拟过程一行行找差异。

6. 我的学习路径与最终建议

6.1 先画图、再写板子、最后debug

我教过很多朋友学 Tarjan，总结出一个高效的学习路径：先拿笔画一个 6 节点的小图，手动模拟一遍，把 dfn、low 和栈的变化全部写在纸上；确认理解无误后，再对照自己写的代码跑一遍同一个图，对比结果；最后故意制造几个小陷阱（比如重边、孤立点、环套环）来测试代码的健壮性。

千万不要一上来就背模板。Tarjan 的模板只有十几行，背下来很简单，但背下来的东西遇到变体题（割点、桥、点双）就无从下手。只有理解了“dfn 是取号、low 是够到的最早祖先、栈中弹出的是成块的节点”这套语义，才能应对所有变体。

6.2 面试或竞赛时的快速要点

真到面试或比赛时，有几个要点能帮你快速检测自己的代码：检查主循环是否覆盖所有未访问节点；检查回边更新用的是 dfn[v] 而不是 low[v]；检查在栈判断是否写全；无向图求桥时检查是否用边编号替代节点编号。

如果你做到了以上四点，Tarjan 的代码基本不会有逻辑瑕疵。剩下的就是熟练度问题，多写几遍，做到“闭着眼能写对”的程度就可以了。

6.3 Tarjan 与 Kosaraju 的取舍

最后聊一聊算法选择。Tarjan 和 Kosaraju 都能在 O(V+E) 时间内求强连通分量，Kosaraju 需要两次 DFS 和一份反图，Tarjan 只需要一次 DFS，代码也更加紧凑。

在实际工程里，如果你不在乎多一份邻接表的空间，Kosaraju 的思路更直白，出问题也好排查；如果追求极致性能和代码量，Tarjan 更优。我个人偏爱 Tarjan，因为它一鱼多吃，能把割点、桥、双连通分量全部收入囊中，学一个赚一堆。但如果你是刚开始接触图论的读者，Kosaraju 作为入门理解强连通分量概念也不错，等概念清楚了再回来学 Tarjan，会顺畅很多。

踩过那么多坑之后，我最大的感触是：Tarjan 的难点从来不在代码本身，而在于三个习惯——给每个节点写清“什么时候访问的”、想清“它能借谁的力回溯”、算清“弹出栈时谁才是这一块的根”。只要这三个问题想明白了，Tarjan 真的只是一个会用栈的 DFS 而已。