浅析Tarjan：从强连通分量到割点桥的图论算法全解析-北京尧图网络

“浅析 Tarjan”——这标题一看就是算法老手写给新手的作战笔记。熟悉图论的人都知道Tarjan 这个名字几乎等价于“强连通分量”“割点”“桥”“最近公共祖先”一个基于深度优先搜索的框架把一堆看起来毫不相干的图论问题统一收编。你要是参加过算法竞赛或者面试时被问过“你怎么判断闭环依赖”大概率绕不开它。这篇文章我想以一个实践者的角度把 Tarjan 算法的底层逻辑、代码实现、坑点排查从头到尾拆一遍。不是说教而是把我自己从“背模板”到“真正理解”的过程分享出来。无论你是刚入门的算法新手还是想系统梳理图论知识的中级选手都可以在这篇里找到适合自己的切入点。读完后你会发现Tarjan 没那么玄就是一个巧妙的回溯记账本。1. 初识 Tarjan为什么一次 DFS 能解决这么多问题1.1 核心思想DFS 序与“回溯记账”逻辑Tarjan 算法的核心不复杂一句话概括利用深度优先搜索DFS时的访问顺序来判断哪些节点能“抱团”形成强连通分量或者哪些边是割断图的关键桥梁。第一次接触时很多人会问为什么非要写dfn和low两个数组为什么不能只用一个我的理解是dfn是“你第几个被访问的”用来标记身份low是“你通过非父节点回边能走到的最小身份编号”用来探测连通性。打个比方假设你在一座迷宫的各房间里依次贴上访问编号。你每进入一个新房间就贴上一个新编号同时手里记着一个“最早可达编号”。如果你能通过某条秘密通道回到编号更小的房间那么你手里的“最早可达编号”就会变小。当某次回溯时你发现某个子房间的“最早可达编号”仍然比当前房间的编号大那就说明子房间无法通过其他路径绕回你或你之前的位置——两者之间的通道就是关键通道。1.2 两个关键数组dfn 与 low 的实际含义dfn[u]节点 u 被 DFS 访问到的次序编号从 1 开始递增。low[u]节点 u 通过一次或多次 DFS 树边、回边能到达的所有节点中最小的dfn值。逻辑上low[u]的更新规则就几条初始low[u] dfn[u] 遍历邻接点 v - 如果 v 没访问过DFS(v)然后 low[u] min(low[u], low[v]) - 如果 v 已经访问过并且 v 还在栈中有向图强连通分量场景 low[u] min(low[u], dfn[v])为什么是无向图割点时low[u] min(low[u], dfn[v])也可以对已访问的父节点做因为无向图父子边本来就存在如果对父节点也更新low不会导致错误但会产生多余的相等比较而遇到“回边”指向祖先时用dfn[v]而不是low[v]更新是防止把未来才能确定归属的连通信息提前合并。我当初犯过的错误是在有向图强连通算法里对所有“已访问节点”都做low[u] min(low[u], dfn[v])忽略了“节点是否仍在栈中”。结果强连通分量全乱套——后面第 5 章我会专门讲这个坑。2. 强连通分量的核心算法2.1 算法步骤详解含栈的使用强连通分量Strongly Connected ComponentSCC是有向图中最大的强连通子图。Tarjan 求解 SCC 的步骤是初始化dfn 0, low 0开辟一个辅助栈。从任意未访问节点开始 DFS。进入节点 u 时分配dfn[u] timestamp初始化low[u] dfn[u]将 u 压入栈中并标记在栈中。遍历 u 的每条边 (u, v)若 v 未被访问过递归 DFS(v)返回后更新low[u] min(low[u], low[v])若 v 已被访问过且 v 仍在栈中则low[u] min(low[u], dfn[v])当 u 的所有边遍历完毕检查low[u] dfn[u]。如果成立则 u 是一个 SCC 的根节点。此时从栈顶不断弹出节点直到弹出 u这些节点共同构成一个强连通分量。注意节点出栈后需要标记为“不在栈中”否则后续节点判断时会把已经属于其他分量的节点误认为可回边的目标。2.2 一个手算模拟示例我们用一个简单的有向图来推演节点 1 → 22 → 33 → 1以及 3 → 44 → 4自环。从 1 开始步骤当前节点操作dfnlow栈内容11进入dfn[1]1low[1]1[1]22进入dfn[2]2low[2]2[1,2]33进入dfn[3]3low[3]3[1,2,3]43→1回边1在栈中-low[3]min(3,1)1[1,2,3]5返回节点2从3返回-low[2]min(2,low[3]1)1[1,2,3]6返回节点1从2返回-low[1]min(1,low[2]1)1[1,2,3]7节点1处理边1→无其他边-low[1]dfn[1]弹出3,2,1弹栈得到 SCC {1,2,3}继续处理其他节点。如果图中有孤立节点 4它自成一个 SCC。这个例子虽然简单但能看出 Tarjan 的核心只要通过回边能回到祖先low 就会变小直到根节点的 low 等于 dfn说明整个环被完整包裹了。2.3 复杂度分析为什么它是线性Tarjan 中每个节点只会 DFS 一次每条边最多被检查两遍一次从起点视角一次可能从终点视角但不会重复递归整体时间复杂度是 O(V E)空间复杂度 O(V)。这意味着我们能在线性时间内求出任意有向图的全部强连通分量这在处理百万级节点依赖图时非常实用。和 Kosaraju 相比Kosaraju 需要两次 DFS 加转置图代码直观但是多一轮遍历和额外存储图结构Tarjan 则一次 DFS 就能完成常数和内存更好。缺点是理解和调试门槛稍高每个变量的含义必须严格把握。3. 割点与桥Tarjan 在无向图上的华丽变身3.1 原理与判定条件在无向图中割点是指删除该点后连通分量数量增加桥割边是指删除该边后连通分量数量增加。Tarjan 在无向图上的应用本质还是dfn和low但判定逻辑有明显区别对于 DFS 树边 (u, v)其中 v 是 u 的子节点如果low[v] dfn[u]则 u 是割点当 u 不是根节点时。如果low[v] dfn[u]则边 (u, v) 是桥。根节点是割点的特殊条件根节点必须有至少两个子节点才算割点。这一区别值得反复记忆割点允许等于桥不允许等于。原因在于low[v] dfn[u]意味着 v 的子树可以回到 u但不能回到 u 的祖先。删除 u 后v 子树与 u 的祖先断开u 是分割点但边 (u, v) 并不是桥因为 v 子树仍然能和 u 连在一起。3.2 整体流程与注意事项无向图 Tarjan 的 DFS 流程从某个节点开始分配dfn和low。遍历邻接点时需要跳过“父边”避免反复访问。通常记录parent节点当遇到父节点时跳过但对于重边则需要特判见第 5 章。对未访问的子节点递归更新low[u] min(low[u], low[v])。对已访问的非父节点更新low[u] min(low[u], dfn[v])。回溯后根据上述条件判断割点和桥。我在练习割点题时发现一个反直觉点对于无向图的回边更新low时用dfn[v]而不是low[v]是为了避免“走回头路”把祖先的 low 信息传递回来造成误判。比如一个简单的正方形四个点按顺序成环。如果对已访问的非父节点比如 4 访问 2 时使用low[2]去更新low[4]可能让低层节点错误地继承高层连通性导致桥判断失效。3.3 双连通分量割点与桥的自然延伸无向图的边双连通分量要求没有桥每个分量内部任意两点之间至少存在两条无公共边的路径。点双连通分量则要求没有割点。Tarjan 同样可以扩展求解。如果你理解割点和桥的判定双连通分量只需要在 DFS 过程维护边栈或点栈在low[v] dfn[u]时弹出分量即可。很多情况下我们不是单纯求割点而是要在割点模型上做后续计数或动态规划比如“删除哪些点能最大化连通块变化”这种题目往往就配合 Tarjan 的割点逻辑再做搜索。4. 有趣的应用Tarjan 不止于强连通4.1 缩点构建 DAG解决传递性优化把有向图的所有强连通分量缩成一个超级节点原图就变成一个有向无环图DAG。这是 Tarjan 最经典的应用。为什么缩点有用因为强连通分量内部的任意两点可达很多问题如最长路径、方案计数、依赖传递在分量内部是等价的我们先缩点再在 DAG 上做 DP复杂度大大降低。我处理过一张“课程依赖关系图”包含数千个节点和上万个依赖边直接做拓扑能算但有环时拓扑排序会失效先用 Tarjan 缩点把环合并成一个节点后续就顺畅多了。4.2 离线 LCA维护祖先 low 的影子Tarjan 也可以用来解最近公共祖先LCA问题利用 DFS 过程中的并查集维护。在完全遍历完某棵子树后将子树的并查集合并到当前节点然后检查所有与该节点相关的查询如果对方节点已经被遍历过则其当前并查集根节点就是 LCA。这看起来和low没什么直接关系但本质还是“DFS 后序处理”思想的延伸。很多初学者会觉得 Tarjan 就是求 SCC看到 LCA 模板里也有 Tarjan 字样会懵。其实它们共享的是“一次性 DFS 完成离线查询”的策略只是数据结构不同。4.3 其他常见场景2-SAT 问题把命题逻辑转化为图判断是否存在赋值方案核心就是用 Tarjan 求 SCC。判定有向图中是否所有点都在某个环上本质上检查 SCC 数量。防火墙与依赖环检测在代码工程里检测模块循环依赖时Tarjan 是标准解法。网络稳定性分析求网络中的关键链路和关键节点即割点和桥。5. 常见问题与踩坑记录调试实录5.1 为什么 low 数组更新要区分“节点是否在栈中”我在代码里犯过一次经典错误if (v parent) continue; // 无向图 else if (!vis[v]) { dfs(v); low[u] min(low[u], low[v]); } else { low[u] min(low[u], dfn[v]); // 漏了“在栈中”判断 }在有向图上如果对已访问但已经出栈的节点也更新low那么当前节点可能会把旧分量的信息错误带回导致本应分离的两个 SCC 被并成一个。你可以想象一下你在一号楼发现走廊能通到二号楼但二号楼已经被独立管理了你硬是把自己楼的管理编号改成二号楼的结果两个楼就成一个大区域了划分全乱。正确的有向图代码必须写成else if (vis[v] in_stack[v]) { low[u] min(low[u], dfn[v]); }5.2 割点中根节点的双重判断无向图割点判断时根节点是特殊的存在只有它有两个及以上子节点才算割点。原因很简单根节点就算删掉每个子树的 DFS 树仍然各自成为连通块但如果是单子树删除根节点只是把这个子树变成更小的连通块并不会增加连通分量个数。我建议把根节点和普通节点的判断分开写不要试图用low[v] dfn[u]一锅端否则在只有一个孩子的根节点上会错误输出割点。5.3 重边处理问题无向图如果存在平行边重边普通的“跳过父节点”逻辑会失效。父子之间有两条边时第二条边其实不是树边而是一条回边所以如果遇到 parent 就直接跳过会漏掉这条回边导致桥判断错误。解决办法是记录边的编号而不是记录父节点跳过条件换成“跳过边的编号相同的那条”也就是skip_edge_id。这也是我在某道模板题上卡了两个小时的原因图简单重边一多桥就全错了。5.4 递归爆栈问题Tarjan 是深度优先的天然递归遇到链状图深度可能到数十万层。竞赛环境或者工程中深层递归容易爆栈。可以用两种方式解决在 C 中显式增加栈空间比如 Linux 下使用ulimit -s。将递归改成手写栈模拟或者用非递归迭代实现。手写栈模拟 Tarjan 比较繁琐但可控。如果真的追求工程鲁棒性我会优先考虑非递归版本如果是学习或快速原型递归还是最直观。5.5 速查表常见症状可能原因修正方式SCC 数量变少且包含无关节点更新 low 时未检查 in_stack补充节点是否在栈中割点多输出根节点根节点判断未特判单独统计根节点子节点数桥全部错乱忽略重边或只跳过 parent用边 ID 跳过有向图结果与线性结果都不对dfn 和 low 初始化顺序错误先分配 dfn再初始化 low大图崩溃递归栈溢出增栈或改非递归6. 一个完整编码模板与使用心得6.1 完整可用的 C 模板有向图强连通分量下面这个模板我经常复制改改用注释写得比较全#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint g[MAXN]; int dfn[MAXN], low[MAXN], scc_id[MAXN], scc_cnt; bool in_stack[MAXN]; stackint st; int timer; void tarjan(int u) { dfn[u] low[u] timer; st.push(u); in_stack[u] true; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (in_stack[v]) { low[u] min(low[u], dfn[v]); } } if (low[u] dfn[u]) { scc_cnt; while (true) { int v st.top(); st.pop(); in_stack[v] false; scc_id[v] scc_cnt; if (v u) break; } } } int main() { int n, m; cin n m; for (int i 0; i m; i) { int u, v; cin u v; g[u].push_back(v); } for (int i 1; i n; i) { if (!dfn[i]) { tarjan(i); } } cout SCC count: scc_cnt endl; return 0; }对于割点模板只要把图改成无向去掉in_stack判断加一个parent或edge_id参数再用上面的判定条件记录即可。我建议不要死记代码而是拿笔手动模拟一个小图观察每个节点的dfn/low变化理解后才记得牢固。6.2 我的工程应用建议很多人觉得 Tarjan 只存在于竞赛题里实际工程中少见。我前段时间做代码模块依赖分析时确实用上了。需求很简单找出模块之间的循环依赖并输出环所在的分量。这种问题如果靠直觉手写找环在有向图节点一多就会漏。最后我直接把 SCC 模板改一改把每个强连通分量节点数大于 1 或存在自环当成循环依赖输出效果非常直观。另外在服务链路或流程编排系统里判断 DAG 的合法性本质上就是检测是否存在环Tarjan 缩点也可以用于“如果存在环输出环内所有节点”的场景。大型系统里这种检测往往要做成图分析服务底层完全可以复用 Tarjan。6.3 学习路径上的最后一点建议学 Tarjan 最忌讳的是直接背模板然后 AC 几道题就以为懂了。我的建议是从有向图 SCC 入手配合手写追踪dfn/low/stack。再做无向图割点桥感受判定条件的细微差别。自己实现缩点后的 DAG并尝试完成拓扑或 DP 题目。最后再挑战 2-SAT 或离线 LCA将思路迁移到类似框架。我实际带过几个新选手他们看完我的笔记后每次都卡在同一个地方明明理解了low的含义却不会处理“边”和“点”的差异。所以我特别强调拿到题先问自己是求点什么是点还是边那个等于号要不要这比模板本身更重要。最后再分享一个小技巧如果你用的是邻接矩阵存图Tarjan 在处理重边和稀疏图时会很吃亏直接上邻接表配合边的编号管理能省掉未来无数 debug 时间。希望这篇梳理能让你对 Tarjan 有一个从“会背”到“会用”的跃迁后面再遇到图论题就不会心虚了。

浅析Tarjan：从强连通分量到割点桥的图论算法全解析

相关推荐

GitHub Trending日榜拆解：三个值得深挖的开发者工具

读懂DDR2数据手册：MT47H64M16HR时序参数解析与FPGA配置实战

单片机电容触摸按键实战：从RC充放电到量产参数调优

更多资讯

微信小程序投票系统怎么从零搭建？以活动评选为例的完整流程

T型三电平逆变器VSG自适应控制与并离网切换优化

COMSOL电弧熔池耦合仿真技术与焊接工艺优化

外贸找客户别再手扒谷歌地图了：我用一个 AI 专家一句话拿到海外商户名单

《小王子》第十六章的文学分析与哲学启示

用电器分析识别装置：电流波形特征提取与分类器实战

今日更新

防关联浏览器哪个好？三款产品实测差异解析

2026钢铁行业AI转型系统选型对比：多基地排产、大宗原燃料采购与质量追溯，六家厂商能力差异在哪里

影刀RPA深度实战：大模型Fine-tuning定制RPA专用Prompt与指令生成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？