low-link · block

articulation point 与 bridge

一张连通的无向图里，删掉某个点会让它散成几块，删掉某条边也会。找出所有这样的点与边，朴素办法是逐个试删、每次重跑一遍连通性，代价 $O(V(V+E))$ 。而 SCC：Tarjan 与 Kosaraju 用过的那对整数换到无向图上一字不改地成立，一遍 DFS 就够。

本页与 SCC 一页共用的不只是思路，是同一份代码骨架：core/scc.ts 与 core/cut.ts 里的两个 dfs 逐行对照只差三处，一处是无向图要跳过来路，一处是判据的比较方向，还有一处是有向图特有的「已出栈」分支在无向图里根本不会发生。

1 · DFS 树与非树边

无向图的 DFS 把边分成两类，没有第三类。走到未访问的邻居，这条边进 DFS 树；走到已访问的邻居，那个邻居必是当前点在树上的祖先，这条边叫 back edge。有向图里还会出现指向旁支或已完成分量的边，无向图里不会：若 $v$ 已访问且不是 $u$ 的祖先，那 $v$ 被访问时就该顺着这条边先走到 $u$ 。

这条性质是后面全部判据的前提。它意味着任何一条「绕开 $u$ 」的通路，在 DFS 树上都表现为 $u$ 的某棵子树里伸出的一条 back edge，跳到 $u$ 的严格祖先。

2 · 判据里的那个等号

定义 1.1（articulation point 与 bridge） 连通无向图 $G$ 中，若删去点 $v$ 及其关联边后 $G$ 不再连通， $v$ 是一个 articulation point；若删去边 $e$ 后 $G$ 不再连通， $e$ 是一条 bridge。

沿用同样的 $\mathrm{dfn}$ 与 $\mathrm{low}$ ： $\mathrm{dfn}[u]$ 是访问时刻， $\mathrm{low}[u]$ 是 $u$ 的子树沿至多一条 back edge 能回到的最小 dfn。设 $v$ 是 $u$ 在 DFS 树上的儿子，两条判据只差一个等号：

\mathrm{low}[v] \ge \mathrm{dfn}[u] \iff u \text{ 是 articulation point}

\mathrm{low}[v] > \mathrm{dfn}[u] \iff \text{边 } u\text{-}v \text{ 是 bridge}

等号的去留对应两句不同的话。取等时， $v$ 的子树最远只能回到 $u$ 自己，回不到 $u$ 的祖先，删掉 $u$ 就断；但 $u$ 与 $v$ 之间可能还连着别的路（那条 back edge 就落在 $u$ 上），删掉这一条边不一定断。严格大于时， $v$ 的子树连 $u$ 都回不到， $u$ 与 $v$ 之间除了这条边再无通路。

root 不适用上面第一条：它没有祖先， $\mathrm{low}$ 与 $\mathrm{dfn}$ 的比较对它没有意义。root 是 articulation point 当且仅当它在 DFS 树上有两棵及以上子树，因为那些子树之间只能经 root 相连。第一张预置图的 root 度为 $2$ ，两条边却通向同一棵子树，它不是 articulation point。

图 2-1 · low-link 判据的单步执行。节点下方是 dfn/low，判定在从儿子返回的那一帧作出；可换图，也可打开更新式的错误开关对照 §3。

警示 · 「跳过来路」这一步按点比对，因此本页的实现不接受重边。 $u$ 与 $v$ 之间若有两条平行边，第二条也会被当作来路跳过，而它本该充当一条 back edge，把这条边从 bridge 名单里除名。预置图里没有重边；要支持重边，跳过的应是那条具体的边而不是那个点。

3 · 更新式里的 dfn 与 low

处理一条 back edge $u \to v$ 时，正确的写法是 $\mathrm{low}[u] \gets \min(\mathrm{low}[u], \mathrm{dfn}[v])$ 。把 $\mathrm{dfn}[v]$ 换成 $\mathrm{low}[v]$ 看上去更「彻底」，也确实是流传很广的一种写法，但它在无向图上是错的： $\mathrm{low}[v]$ 可能已经被 $v$ 自己更早的一条 back edge 压到了 $u$ 的祖先之上， $u$ 于是误以为子树能绕过自己。

实测把这件事量化了。第二张预置图（在第一张上多加一条 $C$ - $F$ ）的正确答案是 $C$ 与 $E$ 两个 articulation point，改用 $\mathrm{low}[v]$ 之后一个都不剩。而同样的改动放到第一张预置图上，丢掉的只有 $E$ ， $C$ 与 $D$ 照旧报出，连唯一那条 bridge 都仍然正确。换句话说，这个缺陷在半数图上根本不显形，测试若只覆盖第一张图就会一路绿灯。第二张图是为此专门造的：反例的必要条件是「祖先的 low 已被更早的 back edge 压低」， $C$ 先经 $C$ - $A$ 把自己的 low 压到 $1$ ， $F$ 再跳回 $C$ ，两件事凑齐才出错。

对 SCC 而言这处改动测不出差别，SCC：Tarjan 与 Kosaraju §3 记着 200 张随机图的比对结果。同一个内核，两种判据对它的容错度并不相同。

4 · biconnected component 与边栈

判据给出的是散点：哪些点是 articulation point、哪些边是 bridge。把它们组织起来的结构是 biconnected component，文献与实现里常简称 block：极大的、内部没有 articulation point 的子图。

block 划分的是边而不是点。每条边恰属于一个 block，而 articulation point 同时属于它两侧的所有 block，正因如此它才是接缝。实现上加一个边栈：树边与 back edge 入栈，判据 $\mathrm{low}[v] \ge \mathrm{dfn}[u]$ 成立时从栈顶弹到 $u$ - $v$ 为止，弹出的一段就是一个 block。

图 4-1 · 边栈切 block 的单步执行。边按所属 block 着色，绿色是还留在栈上的边；判据成立的那一帧一次弹出一整块。

只含一条边的 block 就是一条 bridge，这一点在测试里作为等价关系逐图核对过。第一张预置图切出四块，其中 $C$ - $D$ 单独成块；第二张图补上 $C$ - $F$ 后，中间三块并成一块，bridge 随之消失。

注 · block 出栈的顺序是「最深的先切」。判据只在递归返回时才可能成立，离 root 最远的那块因而最先离开边栈。这与 SCC 的出栈顺序同源：两者都是在返回的路上认出「这一段到顶了」。

5 · 节点失效后的连通块

articulation point 的定义本身就是一份可执行的验证程序：逐个删点、重算连通块、看数目有没有变多。本系列的测试就拿它当 oracle 校验 low-link 的结论，代价 $O(V(V+E))$ ，在 8 个点的图上无所谓。

图 5-1 · 删点后的连通块。点任一节点即可删掉它或恢复，表里列出每个点被删后剩余的块数，与 low-link 的判定并排。

工程上的对应物很直白：把图当成一张网络，articulation point 就是「挂掉就会把网络切成两半」的那些节点，bridge 是同样地位的链路。冗余设计要消灭的正是这两类结构，而连通性：分隔集与 Menger 定理从另一侧回答同一个问题：要切开指定的两个点最少得删几个点，以及这个数为何等于两点间不相交路的条数。那一页给的是定理，本页给的是求法。

6 · 参考文献

Hopcroft, J., & Tarjan, R. (1973). Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM, 16(6), 372–378.
Tarjan, R. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160.
Schmidt, J. M. (2013). A simple test on 2-vertex- and 2-edge-connectivity. Information Processing Letters, 113(7), 241–244.