图论割点与桥Cut Vertices BridgesTarjan 算法无向图割边深度判定在无向连通图Undirected Graph算法与大型分布式网络高可用拓扑分析中“割点Cut Vertex / Articulation Point”与“桥Bridge / Cut Edge / 割边”是衡量系统单点故障风险Single Point of FailureSPOF与关键拓扑脆弱性的核心指标。数学定义割点割顶在无向连通图中如果删去某个顶点 $u$ 及其所有相连的边后整个图分裂为两个或更多不连通的子图则称顶点 $u$ 为图的一个割点桥割边在无向连通图中如果删去某条边 $(u, v)$ 后整个图分裂为两个不连通的子图则称边 $(u, v)$ 为图的一座桥。典型工程应用分布式骨干网络关键交换机单点故障排查若关键路由器是割点其宕机会导致整个局域网割裂为孤岛关键链路脆弱性评估LeetCode 1192 查找集群内的关键连接。今天我们把 Tarjan 算法在无向图上求解割点与桥的数学判定准则、根节点特判以及工业级代码模板彻底讲透。一、核心基石DFS 搜索树与两类边树边 vs 反向边对一个无向连通图进行深度优先遍历DFS遍历过程中的遍历路径构成一棵DFS 生成树DFS Spanning Tree树边Tree EdgeDFS 遍历过程中初次访问到新未访问节点时经过的有向边反向边 / 回边Back Edge连接当前节点与其祖先节点的非树边这是无向图中环路存在的唯一形式无向图不存在横叉边。与强连通分量类似我们为每个节点维护两个核心数组dfn[u]节点 $u$ 被首次访问到的绝对时间戳low[u]从 $u$ 出发经过其子树以及至多一条反向边所能到达的时间戳最小的祖先节点的dfn值。graph TD A[DFS 访问无向图节点 u] -- B[分配 dfn[u] 与 low[u] timer] B -- C[遍历 u 的所有邻居节点 v] C -- D{邻居 v 是否为 u 的父节点 parent?} D --|是 (无向边回流)| E[直接跳过 (严禁走原路反向更新!)] D --|否| F{邻居 v 是否已被访问 (dfn[v] 0)?} F --|已访问| G[说明存在反向边回环! 更新 low[u] min(low[u], dfn[v])] F --|未访问| H[树边递归 DFS(v, u), 回溯后更新 low[u] min(low[u], low[v])] H -- I{桥判定: low[v] dfn[u] ?} I --|是| Bridge[边 (u, v) 是一座关键桥!] H -- J{割点判定: low[v] dfn[u] ?} J --|是且非根节点| CutNode[节点 u 是一个关键割点!]二、桥Cut Edge的数学判定准则在 DFS 树中对于一条树边 $(u, v)$$u$ 是父节点$v$ 是子节点桥的判定黄金法则$$\mathbf{low[v] dfn[u]}$$物理直观证明low[v] dfn[u]意味着以 $v$ 为根的整个子树中没有任何一条反向边能够连接到节点 $u$ 或 $u$ 之上的任何祖先节点这说明子树 $v$ 想要连接到图的其他部分边 $(u, v)$ 是唯一的物理通道一旦删去边 $(u, v)$子树 $v$ 将与 $u$ 及其祖先彻底物理失联因此边 $(u, v)$ 必然是一座桥三、割点Cut Vertex的数学判定准则与根节点特判对于节点 $u$非根节点的割点判定若存在至少一个子节点 $v$满足$$\mathbf{low[v] \ge dfn[u]}$$则节点 $u$ 是一个割点物理直观证明low[v] dfn[u]意味着子节点 $v$ 最多只能连回到 $u$ 自身无法翻越到 $u$ 的祖先节点一旦将节点 $u$ 物理拔除子节点 $v$ 与 $u$ 的父代祖先将被彻底切断图发生割裂终极特判DFS 搜索树的根节点Root判定对于整个 DFS 的起始根节点 $u_{\text{root}}$由于没有更早的祖先上述不等式天然成立。根节点的独立判定法则根节点是割点当且仅当根节点在 DFS 树中拥有 $\ge 2$ 个互不相交的子树分支childCount 2工业级实战LeetCode 1192 查找集群内的所有关键连接桥import java.util.*; public class CriticalConnectionsSolution { private int timer 0; private int[] dfn; private int[] low; private ListListInteger graph; private ListListInteger bridges; public ListListInteger criticalConnections(int n, ListListInteger connections) { dfn new int[n]; low new int[n]; graph new ArrayList(); bridges new ArrayList(); timer 0; for (int i 0; i n; i) graph.add(new ArrayList()); for (ListInteger edge : connections) { int u edge.get(0); int v edge.get(1); graph.get(u).add(v); graph.get(v).add(u); } // 假定图连通从节点 0 开始 DFS (父节点记为 -1) dfsBridge(0, -1); return bridges; } private void dfsBridge(int u, int parent) { dfn[u] low[u] timer; for (int v : graph.get(u)) { if (v parent) { continue; // 核心无向图严禁原路回流遍历父节点 } if (dfn[v] 0) { // 树边递归 dfsBridge(v, u); low[u] Math.min(low[u], low[v]); // 核心判定子节点 v 无法回溯到 u 及以上边 (u, v) 即为桥 if (low[v] dfn[u]) { bridges.add(Arrays.asList(u, v)); } } else { // 遇到已访问的反向边 low[u] Math.min(low[u], dfn[v]); } } } }割点与桥的判定总结速查拓扑结构核心判定数学不等式根节点Root特殊处理时间复杂度桥割边树边 $(u, v)$ 满足low[v] dfn[u]无需特判所有边通用$\mathcal{O}(V E)$割点割顶存在子节点 $v$ 满足low[v] dfn[u]需特判根节点必须在 DFS 树中有 $\ge 2$ 个子节点$\mathcal{O}(V E)$实习生的图论总结无向图中的割点与桥揭示了网络拓扑结构中最致命的单点薄弱环节。Tarjan 算法通过精巧的时间戳dfn与追溯值low的大小比较在严密的 $\mathcal{O}(V E)$ 线性时间内实现了全图关键连接的秒级扫描。掌握了割点与桥的判定本质无论是网络可用性设计还是高难度算法攻坚你都将拥有直击拓扑命门的锋利眼光。