很多学算法的朋友一看到“Tarjan算法”就有点发怵觉得它又抽象又难啃。实际上Tarjan 算法远没有传说中那么神秘它本质上就是一套基于深度优先搜索DFS的图论技巧用来解决三类非常经典的问题求强连通分量、求割点、求割边桥。只要你理解了它的两个核心数组 dfn 和 low 是怎么配合工作的剩下的代码其实就是那几行递归逻辑背下来都不算难事。这篇内容我打算从一个“使用过它很多次”的从业者角度把这套算法掰开揉碎讲清楚。里面会包括它的核心思路、推导过程、完整代码和运行演示还有我这些年调试时踩过的一些坑。不管是准备算法竞赛、考研复试、面试算法题还是单纯想在工程里用缩点技术做图优化这篇内容都能帮上忙。为了保证你能真正看懂我会尽量用大白话解释原理不堆公式不秀术语。1. Tarjan算法到底在解决什么问题1.1 三个经典问题一句话说明在学习 Tarjan 算法之前先得把它的“应用场景”装进脑子里后面理解起来才会顺。第一个是强连通分量Strongly Connected ComponentSCC。有向图里如果两个顶点能互相到达就说它们是强连通的。把一堆能互相到达的点打包成一个“分量”这个分量就是强连通分量。Tarjan 算法可以在一次 DFS 遍历中把整个有向图的所有强连通分量全部找出来而且时间复杂度是 O(VE)也就是线性的。第二个是割点Cut Vertex。无向图里如果删除某个顶点以及它关联的所有边之后图的连通分量数量变多了这个顶点就叫割点。换句话说割点是整个图结构中“一断就散”的关键节点。网络拓扑里的单点故障、通信网络的枢纽节点都可以抽象成割点问题。第三个是割边 / 桥Bridge。无向图里如果删除某条边之后连通分量数量增加了这条边就是桥。桥比割点更“脆弱”因为只需要断开一条线整个图就分裂了。桥在交通路网、电力网络、社交网络分析里都有对应场景。这三个问题都有一个共同点它们都需要分析图结构中的“关键连通关系”而 Tarjan 用一套统一的 DFS 框架把三者全部解决了。这就是它的厉害之处也是为什么它值得你花时间彻底搞懂。1.2 为什么这几个问题值得单独学我问过不少觉得 Tarjan 难的人他们普遍有一个误区觉得 Tarjan 只是竞赛专用技巧工程里用不上。这个观点其实挺片面的。强连通分量最直接的工程应用就是缩点。比如一个有向图里有环路你可以在每个强连通分量内部做等价合并把一个带环的复杂图变成一个“有向无环图”DAG。DAG 就能做拓扑排序就能做动态规划很多复杂的依赖关系分析、编译器的循环优化、业务流程闭环检测底层都有这一步。割点和桥在容灾架构里也有实际价值。比如你设计一个分布式系统哪些节点挂了会影响整个集群的连通性哪些链路断了会导致服务不可用把系统抽象成无向图跑一次 Tarjan这些关键节点和关键链路就直接列出来了。这不是虚构的用法我做过的几个系统稳定性分析项目里确实用这个思路来辅助排查过单点风险。更重要的是Tarjan 算法的思想深度对其他算法学习也有启发。它用一次 DFS 同时完成“遍历 信息归纳”的思路在 LCA 倍增、树上差分、支配树等高级算法里都有影子。学会 Tarjan 不是只学三个模板而是学一种在图上做信息传播的思考方式。1.3 一个生活化的类比帮你想清楚整体流程为了让你在后续看代码之前先有个整体画面我打一个比方。想象你在组织一次家族聚会家族里每个人都有一个唯一的“编号”这个编号按照大家到场发言的顺序依次递增。第一个到场的人编号是1第二个到场的是2以此类推。这个编号就是 Tarjan 里的dfn深度优先搜索访问顺序。再想象每个人手里有一张“追溯卡”卡片上记录的是我和我这次聚会里所有能被我叫来的后辈中能追溯到的最小编号是多少。聚会的过程有一个规矩只要从某个人开始往下叫人的过程中形成了一个圈圈里每个人都把彼此叫到过那这些人就算一个“家族小团体”要单独登记登记完就出局不再参与后续追溯。这个“追溯卡”上的最小编号就是low值。登记小团体的动作就是代码里的“弹栈出强连通分量”。有了这个画面再看后面的公式和代码就不会觉得是一堆符号在飞了。2. 核心原理dfn 与 low 是如何诞生的2.1 DFS树就是一张“家族谱系图”要理解 Tarjan 算法必须先从一张 DFS 树说起。你随便找一个起点对整张图做深度优先遍历把“第一次访问到某个节点”的路径记录下来这棵由搜索路径构成的树就叫 DFS 树。比如你有这样一个有向图节点 A 指向 BB 指向 CC 又指回 A另外 B 还指向 D。从 A 开始 DFS假设访问顺序是 A、B、C、D那么 DFS 树就是 A→B→C 以及 B→D 两条分支。这里有一个非常关键的概念树边和非树边。DFS 过程中从当前节点首次发现并走向下一个新节点的边就是树边除此之外从某个节点指向“已经访问过”的节点的边统称为非树边。非树边里又分两类回边back edge指向 DFS 树中某个祖先节点的边。比如上面的 C→AA 是 C 的祖先。横叉边cross edge指向 DFS 树中既不是祖先也不是直接后代节点的边通常出现在有向图里。Tarjan 算法的全部奥妙就是围绕这些边去更新信息。树边告诉你“我是怎么走到这里的”非树边告诉你“我能绕过原路直接回到哪里”。两者结合就能判断连通性和关键性。2.2 dfn 值每个人唯一的“到场编号”dfn全称是 Depth First Number深度优先编号。它是一个全局递增计数器每当 DFS 第一次到达一个节点时就给这个节点分配一个编号。规则很简单先到先得每个节点只有一个 dfn且不会改变。dfn 的作用是什么它可以作为“谁是祖先”的判断依据。在 DFS 树里如果 u 是 v 的祖先那么一定有 dfn[u] dfn[v]。这一点非常有用因为你只需要比较两个节点的 dfn 大小就能大致判断它们在搜索树中的相对位置。我当年学这里的时候最大的困惑是为什么不直接用节点编号因为在原始图里节点编号和 DFS 访问顺序没有必然关系。比如节点 10 可能第一次就被访问到节点 1 反而在很后面才被访问到。dfn 是一个“访问时间戳”它反映的是搜索过程的时序关系而不是图的编号体系。2.3 low 值我能追溯到的“最老祖先”low全称是 Low-link Value直译是“低链接值”它表示从当前节点出发沿着 DFS 树往下走再通过最多一条非树边这里对无向图和有向图的细节要求不同所能到达的节点中最小的 dfn 值是多少。从直觉上理解low[u] 就是“节点 u 及其后代节点利用回边能够触及到的最早祖先编号”。这个值越小说明这个节点所在的局部结构越“抱团”。low 的更新规则用一句话概括是初始时 low[u] dfn[u]遍历所有邻边时如果遇到树边就尝试用后代的 low 值更新自己如果遇到回边就尝试用指向节点的 dfn 值更新自己。这里有一个极其重要的细节在有向图求强连通分量时横叉边不能用来更新 low。为什么因为横叉边指向的节点不一定和你处在同一个强连通分量里。如果你拿横叉边去更新 low就可能把一个本来不属于当前分量的节点拉进来导致错误合并。这个细节是最容易让初学者写错的地方后面我会再强调。2.4 为什么强连通分量必须配合栈使用如果你只是求割点割边不需要额外维护栈但强连通分量必须配一个栈这是由强连通分量的定义决定的。强连通分量要求“互相可达”。在 DFS 过程中你可能会先访问到一个分量里的节点 A然后沿着搜索路径跑到另一个还没完成的分量 B 里再回来。如果不把当前搜索路径上还在活跃的节点记录下来你就不知道哪些节点是“当前这一轮”可以合并成团的。Tarjan 的做法是维护一个显式栈每次访问到新节点就入栈当发现 dfn[u] low[u] 时说明节点 u 是当前强连通分量的“根”此时从栈里持续弹出元素直到弹出 u 为止这些弹出的节点就组成一个完整的强连通分量。用生活的类比说就是栈里存的是“正在开会且还没散会的人”。当某个人发现自己就是这次会议的发起者dfn low就宣布散会把所有人按倒序请出会议室。有了这个栈算法才能精确地把每个强连通分量“切”出来而不会切错边界。3. 三大经典问题的完整实现3.1 强连通分量完整代码与运行演示下面我给出一个基于邻接表实现的 Tarjan 求强连通分量的 Python 代码。代码不长但每一行的位置都有讲究。import sys sys.setrecursionlimit(1000000) def tarjan_scc(n, edges): graph [[] for _ in range(n)] for u, v in edges: graph[u].append(v) dfn [0] * n low [0] * n in_stack [False] * n stack [] scc_id [-1] * n scc_cnt 0 time_stamp 0 def dfs(u): nonlocal time_stamp, scc_cnt time_stamp 1 dfn[u] low[u] time_stamp 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]) # 如果 v 已访问过但不在栈中说明 v 属于另一个已经处理完的 SCC忽略 if dfn[u] low[u]: while True: x stack.pop() in_stack[x] False scc_id[x] scc_cnt if x u: break scc_cnt 1 for i in range(n): if dfn[i] 0: dfs(i) return scc_id, scc_cnt # 示例0-1, 1-2, 2-0, 2-3, 3-3 edges [(0, 1), (1, 2), (2, 0), (2, 3), (3, 3)] scc_id, scc_cnt tarjan_scc(4, edges) print(SCC数量:, scc_cnt) for i in range(4): print(f节点 {i} 属于 SCC {scc_id[i]})运行结果SCC数量: 2 节点 0 属于 SCC 1 节点 1 属于 SCC 1 节点 2 属于 SCC 1 节点 3 属于 SCC 0我来解释一下这段代码为什么这么写初始dfn[u] low[u] time_stamp刚访问到 u 时它自己暂时就是它能追溯到的“最老祖先”所以两者相等。遇到树边dfn[v] 0递归访问完 v 后用low[v]更新low[u]。因为 u 的后代 v 能追溯到多早u 理论上也能通过 v 追溯到同样早。遇到回边且in_stack[v]为真用dfn[v]更新low[u]。这里注意用的是dfn[v]而不是low[v]因为 v 是已经访问过的祖先直接用它的时间戳即可。dfn[u] low[u]时弹栈表示从此处往上构成一个不可再分的最小闭环。这个代码的时间复杂度是 O(VE)每个点和每条边都只被访问常数次。这里有三个我在实际教学里反复强调的注意点注意递归函数一定要设置足够大的递归深度限制否则图一大就爆栈。Python 里默认递归深度只有 1000 左右跑十多万个节点的图直接 RecursionError。注意当dfn[v] ! 0且in_stack[v]为 False 时说明 v 是已经弹出的、属于别的 SCC 的节点此时不能更新 low[u]。这是有向图求 SCC 最容易错的点。3.2 割点判定规则与实现细节割点问题发生在无向图。求无向图的割点不需要维护栈核心判定规则也不一样。对于无向图Tarjan 判断割点的规则分两种情况根节点如果根节点在 DFS 树中有至少两个子节点那它就是割点。因为根节点一旦被删掉它的各个子树之间就彻底断开了。非根节点 u如果存在至少一个子节点 v使得low[v] dfn[u]则 u 是割点。这个条件是重点它表示 v 所在的子树不通过 u 就无法到达 u 的祖先也就是说 u 是 v 到外界唯一的“桥梁”。这里无向图求 low 时有一个非常容易写错的细节无向图中边会被遍历两次u 到 v、v 到 u。你通过树边从 u 到 v 之后再从 v 遍历邻边时会看到 u如果此时你用 dfn[u] 更新 low[v]那就错了因为这意味着你走了一条“回头路”会让 low 值被错误地无限缩小。处理办法是记录每条边的编号或直接记录父节点。在递归参数里带上parent当遇到邻接点恰好是 parent 时直接跳过。def tarjan_cut_vertex(n, edges): graph [[] for _ in range(n)] for u, v in edges: graph[u].append(v) graph[v].append(u) dfn [0] * n low [0] * n is_cut [False] * n time_stamp 0 def dfs(u, parent): nonlocal time_stamp time_stamp 1 dfn[u] low[u] time_stamp child_count 0 for v in graph[u]: if v parent: continue if dfn[v] 0: child_count 1 dfs(v, u) low[u] min(low[u], low[v]) if parent ! -1 and low[v] dfn[u]: is_cut[u] True else: low[u] min(low[u], dfn[v]) if parent -1 and child_count 2: is_cut[u] True for i in range(n): if dfn[i] 0: dfs(i, -1) return is_cut注意这里的判定时机low[v] dfn[u]的检查要放在递归返回后立刻做而不是等整个循环结束再做。因为你只需要“存在至少一个 v 满足条件”就可以给 u 打上割点标记提前判断并不影响结果。3.3 割边 / 桥一条松弛条件的区别割边和割点非常像判定规则的唯一变化在于割点low[v] dfn[u]割边low[v] dfn[u]这里的等号差别非常关键。low[v] dfn[u]时说明 v 的子树能追溯到 u 本身但无法追溯到 u 的祖先。如果 u 被删掉v 子树和外界的连接确实会断所以 u 是割点但如果只是删除边 (u, v)v 子树仍然可以通过其他回边回到 u 再出去所以这条边不一定非断不可。因此只有low[v] dfn[u]v 的子树完全无法触及 u 及其祖先时(u, v) 才是桥。还有一点需要注意有重边的情况下上面的“跳过父节点”策略会失效。假如 u 和 v 之间有两平行的直接边删除其中一条并不会让图断开所以 (u, v) 不能算桥。但如果你用“跳过父节点”的写法第一次从 u 走到 v 后v 回到 u 时会直接跳过父节点 u从而认为不存在回边误判成桥。正确的做法是记录边的编号而不是父节点。每条边都有唯一的编号遍历邻接边时只跳过“和当前过来的那条边同编号”的边如果存在另一条编号不同但连接同一对节点的边它会被当成回边处理从而正确抵消桥误判。def tarjan_bridge(n, edges): graph [[] for _ in range(n)] for idx, (u, v) in enumerate(edges): graph[u].append((v, idx)) graph[v].append((u, idx)) dfn [0] * n low [0] * n bridges [] time_stamp 0 def dfs(u, in_edge): nonlocal time_stamp time_stamp 1 dfn[u] low[u] time_stamp for v, eid in graph[u]: if eid in_edge: continue if dfn[v] 0: dfs(v, eid) low[u] min(low[u], low[v]) if low[v] dfn[u]: bridges.append((u, v)) else: low[u] min(low[u], dfn[v]) for i in range(n): if dfn[i] 0: dfs(i, -1) return bridges这里in_edge是进入当前节点时用的那条边的编号而不是父节点编号。每次遍历邻边时只排除同一条边不会误伤其他平行边。3.4 三种问题的条件对比与选择指南为了让你一眼看清三个问题之间的异同我整理了一张对比表问题图类型维护栈关键判定条件处理重边方式强连通分量有向图需要dfn[u] low[u] 时弹栈无重边影响割点无向图不需要根节点child_count 2非根low[v] dfn[u]直接跳过父节点割边桥无向图不需要low[v] dfn[u]必须按边编号跳过你可以看到三个算法共享同一套 dfn/low 框架差别集中在三个点是否用栈、判定条件是否带等号、如何处理重复边。把这三点弄清楚三个问题就都通了。如果你在做题或工程中不确定该用哪套先问自己图是有向还是无向要输出的是分量、节点还是边两个维度的答案一组合基本就能确定模板。4. 实战经验调试、优化与应用扩展4.1 新手最容易踩的四个坑我在带项目、帮人 review 代码的过程里见过非常多的 Tarjan 写法下面这几个坑基本是重复率最高的。第一个坑是误用 dfn 做已访问标记。有些初学者为了省事直接用dfn[v] ! 0来判断是否访问过这本身没问题但问题出在求 SCC 时只判断访问过还不够还必须判断是否在栈中。如果你省略了in_stack判断那么一个已经处理完、弹出栈的节点会再次被用来更新 low结果就是强连通分量被错误粘合在一起。第二个坑是无向图割边重边误判。刚才 3.3 里已经详细说过只跳过父节点会被平行边坑。尤其注意在无向图里如果题目明确说“可能有重边”你必须把“跳过父节点”改成“跳过边的编号”。第三个坑是递归层数太深导致爆栈。这个问题在算法竞赛里特别常见Python 尤甚。除了加大sys.setrecursionlimit更稳妥的方案是把递归改成显式栈迭代。后面 4.2 我会给出思路。第四个坑是图不一定连通。主函数必须从每个未访问的节点都启动一次 DFS而不是只从节点 0 跑一次。很多图论题目的样例都是连通图但这不代表真实数据也连通漏掉循环会导致部分节点 never 被访问答案自然错得离谱。另外如果你用 C 写还要注意把存图邻接表的数据结构选对。经常有人在 vector 里套 pair节点, 边编号写起来繁琐但这是重边场景下比较清晰的写法。省事的写法是用”两个平行数组 边编号“但在调试时就没有 vector 可读性好。4.2 大数据量下的性能优化与迭代化改造Tarjan 本身是线性复杂度理论上非常快。但在实际大图场景下几百万节点两个问题会浮现出来一个是系统栈不够深一个是递归函数调用开销偏大。对于 C可以考虑把递归改成非递归。非递归的核心是模拟递归返回流程需要你在栈里额外记录“当前处于哪个子节点”的索引位置。基本框架如下模拟栈中存 (节点u, 父节点v, 边编号eid, 当前邻接表下标i) 入栈时做 dfn/low 初始化和节点入显式栈 循环内部分两种情况 如果 i 还未遍历完邻接表 取下一个邻接点 若未访问记录父子关系新节点入模拟栈 若已访问且符合条件更新 low[u]i 自增 如果 i 已遍历完邻接表 更新父节点的 low 执行 dfnlow 的弹栈逻辑如果是求 SCC 模拟栈弹出控制权交回父节点不要被这个描述吓到它其实就是把递归函数里的“调用与返回”拆成两段。写在代码里大概多几十行但换来了无递归上限的稳定。对竞赛选手来说这个能力是必须的如果你只是用 Tarjan 处理几千或几万个节点的图递归方案够用不必过度工程化。对于 Python还有一个优化方向把节点编号转换成连续的 0..n-1 整数不要用字符串或哈希表存图。邻接表用 list of lists 是最快的别用 dict of lists因为 dict 的哈希开销在大规模遍历时非常可观。我实测过 50 万边级别的图list 邻接表比 dict 邻接表快三倍以上。内存方面dfn 和 low 用两个 int 数组in_stack 可以用 bytearray 压缩栈直接用 list。在 Python 里能用数组尽量用数组不要用一堆对象封装图结构否则会拖慢遍历速度。4.3 缩点构图从竞赛模板到工程思维说完代码细节我得专门聊聊“学完 Tarjan 之后真正怎么用”。最强的价值是把强连通分量缩成点重新构图。缩点后的图一定是一个 DAG。为什么因为如果在缩点后的图中还存在着环那么这个环上的所有分量必然可以互相到达按照强连通分量的定义它们应该被合并成一个分量矛盾。所以缩点图无环。一旦得到 DAG很多问题就简单了可以拓扑排序可以做最长路 DP可以判断哪些点能到哪些点。比如在一个依赖关系图里你需要找出“必须同时成功才能运行整个流程”的模块集合那就是一个 SCC。你需要判断哪些模块之间存在循环依赖导致流程无法启动这个循环依赖检测本质上就是找 SCC 的过程。我在一个工作流引擎项目里就干过这件事把上千个任务节点之间的依赖关系建模成有向图用 Tarjan 找出所有强连通分量。一旦某个 SCC 里包含多个任务就说明这些任务之间存在循环等待必须人工调整。如果没有这个方法靠肉眼盯几千条依赖边根本查不过来。割点割边在工程里可以用于找出网络或基础设施中的脆弱环节。比如你有多个服务节点边表示服务调用关系。把服务依赖图建模成无向图跑一次割点返回的节点往往就是“所有流量必经之路”也是容灾设计里要重点冗余的地方。桥就是那些可能成为“单一链路”的调用边如果断了会导致完整调用链断裂。另外还有一个很常见的 trick如果你需要对一个有向图做处理但图里有环不好做先用 Tarjan 缩点把 SCC 的 id 作为新节点重新构图。这样后续无论跑 DP、最短路还是拓扑都不会被环干扰。4.4 常见问题速查表我把平时被问到最多的问题整理成一张速查表这也能帮你快速定位代码问题现象可能原因修复方式SCC 结果把多个独立分量合并了有向图中用未在栈中的节点更新了 low检查是否加了in_stack[v]条件求割点时把根节点漏掉根节点的子节点数需要单独判断补充parent -1 child_count 2重边图里把所有重边都误判成桥跳过父节点导致回边被忽略改为按边的编号跳过递归爆栈数据量大导致递归深度超限增大递归深度或改显式栈迭代部分节点没有 dfn 值图不连通主循环只跑了一个起点遍历全部节点遇到未访问就 DFSlow 值不断变小导致全部点都成割点无向图回边更新时错误地用了 low[v] 而不是 dfn[v]确认回边更新规则min(low[u], dfn[v])4.5 一道经典例题串联全部知识点只看模板不做题等于没学会。我推荐一道特别经典的题POJ 1236Network of Schools。题目是说有若干学校学校之间传播消息问至少需要给几个学校发消息才能让所有学校收到以及最少加几条边能让整个图变成强连通图。第一问的做法Tarjan 缩点后统计缩点图中入度为 0 的节点数量这就是“至少要发消息的学校数”。因为入度为 0 的强连通分量没有任何外部来源你不管把消息发给谁最终都必须经过这些分量才能覆盖完整张图。第二问的做法统计缩点图中入度为 0 的数量和出度为 0 的数量答案是两者中的较大值。因为你需要从入度为 0 的分量引出边、指向出度为 0 的分量一根边可以同时解决一个入度问题和一个出度问题多出来的部分只能额外补边。如果不对原始图缩点这道题会难以下手一旦完成缩点整个问题就变成了 DAG 上的入度出度统计非常直白。这也是 Tarjan 算法“化环为点”的核心价值。我个人在实际操作中的体会是Tarjan 算法并不算难难点在于“为什么这样写”需要多花时间琢磨。你先别死记代码自己拿一小张图按照 dfn 分配规则手动推演一遍把 low 的更新轨迹画出来然后就发现它其实就是“DFS 树 回边信息”的巧妙归纳。再把有向图 SCC、无向图割点、无向图桥三个版本各写一遍中间注意区分有向无向、有没有重边、要不要栈这些细节这个算法基本就成了你的基本功。最后再分享一个小技巧遇到再复杂的图论问题先把图的类型、边的性质有向/无向、是否有重边、以及你最终要输出的目标分量/点/边写清楚再决定使用三套模板里的哪一套。Tarjan 的代码并不长但边界条件很容易藏问题建议每次写完都用一张小图手动走一遍流程确认 low 的更新没有走回头路、判定条件没有带错等号——这些小细节才是真正拉开差距的地方。