type
Post
status
Published
date
May 3, 2026
slug
tarjan
summary
tags
category
icon
password
深入解析 Tarjan 算法：无向图中的割点与割边判定
在计算机科学与图论领域，图的连通性是一个极其重要的研究方向。在分析网络拓扑的脆弱性、寻找关键交通枢纽或通信网络中的单点故障时，我们经常会遇到两个核心概念：割点（Articulation Point / Cut Vertex）和割边（Bridge / Cut Edge）。
美国计算机科学家 Robert Tarjan 发明了一种基于深度优先搜索（DFS）的极其优雅且高效的算法，能够在 的时间复杂度内（其中 是顶点数， 是边数）同时找出无向图中的所有割点和割边。
本文将基于你提供的这段精炼的 C++ 代码，深入拆解 Tarjan 算法的底层逻辑，并完整梳理割点与割边的判定机制。
一、 核心概念：什么是割点与割边？
在进入代码逻辑之前，我们需要明确这两个概念在无向连通图中的定义：
- 割边（桥）：如果删除无向图中的某条边后，图的连通分量数量增加（原本连通的图变成了两个互不相连的“孤岛”），那么这条边就被称为割边。
- 割点：如果删除无向图中的某个顶点以及所有依附于该顶点的边后，图的连通分量数量增加，那么这个顶点就被称为割点。
简而言之，割点是关键的“枢纽”，割边是唯一的“通道”。
二、 算法基石：DFS 生成树与两个神奇的数组
Tarjan 算法的精妙之处在于它利用了对图进行深度优先遍历时产生的 DFS 生成树。在 DFS 过程中，算法维护了两个至关重要的数组：
dfn[u]（时间戳 / DFS 序）：
记录节点 在 DFS 遍历过程中第一次被访问到的次序。这个值一旦在节点被访问时确定，就不会再改变。它反映了节点在生成树中的上下级层级关系。
low[u]（追溯值）：
这是 Tarjan 算法的灵魂。它表示节点 及其 DFS 生成树上的所有子孙节点，在不经过 $u$ 到其父节点的树边的情况下，能够通过一条“返祖边（Back-edge）”到达的最小的
dfn 值。 换句话说，
low[u] 记录了以 为根的子树中的节点，向图的“上层”能爬回到的最高位置（即时间戳最小的节点）。三、 逐行解析：割边判定的代码实现
为什么 是割边的判定条件？
让我们仔细思考这个不等式：
dfn[u]是节点 的访问时间。
low[v]是节点 （ 的子节点）及其子树所能到达的最早的访问时间。
如果
low[v] > dfn[u]，这意味着什么？这意味着，从节点 及其所在的整棵子树出发，无论怎么绕，都找不到任何一条路径可以绕过 这条边回到 本身，更别提回到 之前的节点了。
既然没有任何其他的“备用路线”连接子树 和 （及其上层图），那么一旦我们将 这条边切断，节点 所在的子树就会彻底与图的其余部分断开连接。因此， 就是一条割边（桥）。
四、 如何修改代码来寻找割点？
你提供的代码完美解决了割边问题，但文章的主题包含“割点”。实际上，基于几乎相同的逻辑和数组，只需稍加修改判定条件，我们就能找到割点。
判定一个节点 是否为割点，分为两种情况：
1. 非根节点
如果节点 不是 DFS 生成树的根节点，只要它的某个子节点 满足条件：
那么 就是一个割点。
逻辑解析：与割边的严格大于不同，这里是大于等于。如果 ，说明 及其子树最多只能绕回节点 本身，无法到达 更早的祖先。如果把顶点 删掉，那么 的子树同样无法与上层连通，因此 是割点。
2. 树根节点
如果节点 是 DFS 遍历的起点（即树根），上述公式就不适用了。树根没有祖先，所以其子节点的 值一定大于等于它的 值。
对于根节点，判定它是否为割点的条件非常直观：只要它在 DFS 生成树中拥有两棵或两棵以上的独立子树，它就是割点。 因为删掉根节点后，它的这些子树之间就会相互断开。
割点代码实现示例：
为了寻找割点，我们通常会引入一个变量记录子树数量，并将判定逻辑调整如下：
注意: 如果图不连通就要遍历所有节点，从每一个节点开始即
五、 总结与注意事项
- 时间复杂度：无论是求割点还是割边，每个顶点和每条边都只被访问常数次，因此整体时间复杂度为 ，非常高效。
- 重边问题：在处理可能包含重边（两点之间有多条边）的图时，寻找割边的代码需要特别小心。如果 和
之间有两条边，它们都不是割边。上面的代码通过
v != fa来避免通过刚刚过来的边原路返回，但这无法处理重边。若有重边，通常需要在 DFS 时记录边的编号，而非父节点的编号。
- 图不连通的情况：如果原始图本身就是由多个连通分量组成的，我们需要在主函数中遍历所有的节点，如果发现有未访问的节点（
dfn[i] == 0），就以它为起点调用一次dfs。
Tarjan 算法通过巧妙的时间戳与追溯值设计，将复杂的图拓扑关系降维到了生成树上的数值比较中。掌握它，不仅能解决割点割边问题，更是理解强连通分量（SCC）、双连通分量（BCC）等更高级图论算法的基础。
- 作者:wzy
- 链接:https://wzyblogs.us.ci//article/tarjan
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。