桥查找器

伪代码

与割点完全相同的机制，只是把其中一个比较由大于等于改成了严格大于。

dfs(u, 父结点):
    disc[u] = low[u] = ++时间

    对 u 的每个邻居 v:
        若 v == 父结点: 跳过     // 跳过来时的那条边
        若 v 已访问:
            low[u] = min(low[u], disc[v])    // 回边
        否则:
            dfs(v, u)
            low[u] = min(low[u], low[v])
            若 low[v] > disc[u]:
                报告边 (u, v) 是桥

这个严格不等号就是它与割点的全部差别。low[v] > disc[u] 表示 v 之下的子树中没有任何东西能抵达 u 或 u 之上，因此边 (u, v) 是唯一的通路，删掉它就会让图断开。割点用的是 low[v] >= disc[u]，其中取等意味着子树能抵达 u 本身但再上不去；这在你删掉结点 u 时会孤立该子树，但只删掉那条边时并不会。

分步示例演算

在一个三角形加两条边尾巴的图上从 A 出发执行 DFS，这与割点示例使用的是同一个图，从而可以在完全相同的数据上对照两种判据。

示例图: 无向边 A-B、B-C、C-A 构成三角形，另有 C-D 与 D-E。

1. 分配发现时间. 沿 A、B、C、D、E 依次下探，得到的发现时间分别为 1、2、3、4 和 5。
2. E 是死胡同. E 只有父结点 D 这一个邻居，因此 low[E] 保持为 5。
3. D-E 是桥. 回到 D 时，low[D] = min(4, low[E] = 5) = 4。检查这条边：low[E] = 5 > disc[D] = 4，因此 D-E 是桥。删掉它会孤立 E，这显然是对的。
4. C-D 同样是桥. 在 C 处，回边 C-A 给出 low[C] = min(3, disc[A] = 1) = 1，再并入孩子后为 min(1, low[D] = 4) = 1。检查通往 D 的边：low[D] = 4 > disc[C] = 3，因此 C-D 也是桥。
5. 三角形上的边都不是. 在 B 处，low[B] = min(2, low[C] = 1) = 1。检查边 B-C：low[C] = 1 > disc[B] = 2 不成立，因此 B-C 不是桥。C 无需借助 B-C 就能抵达 A，这条边存在替代通路。同样的推理也排除了 A-B 与 C-A。

桥是 C-D 与 D-E。请注意它与同一个图上割点结果的对照：那里的答案是结点 C 和 D。三角形上的每条边都位于一个环上，因而都有绕行路线；而尾巴上的每条边都是通往其后一切的唯一连接。一般规律由此直接得出：一条边是桥，当且仅当它不位于任何环上。

复杂度及其来源

时间: O(V + E) · 空间: O(V)

一次深度优先搜索，每条边只附加常数级的额外工作，因此代价就是遍历的代价。每个结点访问一次，每条边从两个端点各检查一次。状态是每个结点两个整数加上递归栈，全为 O(V)。朴素做法是逐条删边再检查连通性，代价为 O(E 乘以 (V + E))；因此在一个有 10000 条边的图上，low-link 方法大约要快四个数量级。

何时使用桥查找，何时不宜

同一次 DFS 能回答好几个相关问题。请根据脆弱的是一条边、一个结点还是一整片区域来选择。

常见陷阱

• 误用 >= 而不是 >. 割点的判据是 low[v] >= disc[u]，桥的判据是严格的 low[v] > disc[u]。用 >= 会把每一条通往「无法越过其父结点」的结点的树边都报告出来，导致严重的过度上报。仅仅一个字符就把两个算法分开了。
• 按结点而非按边跳过父结点. 当 u 与 v 之间存在平行边时，第二条边是一条真正的替代通路，两条边都不是桥。按结点身份跳过会掩盖这一点，从而报告出一条并不存在的桥。请记录你具体是从哪条边过来的。
• 回边上使用 low[v] 而不是 disc[v]. 遇到已访问的邻居时，应当并入它的发现时间而不是 low-link。用 low[v] 可能把来自无关子树的值引进来，从而悄无声息地压制掉真正的桥。
• 把它用于有向图. 桥是为无向图定义的。有向图上的对应问题是「删去哪些边会使强连通分量数量增加」，那是另一个问题，需要另一套工具。
• 忘记非连通分量. 一次 DFS 只覆盖一个分量。请遍历所有结点并从每个未访问的结点重新发起搜索，否则其他分量中的桥将不会被报告出来。

常见问题

什么是图中的桥？

桥又称割边，是指删去之后会使连通分量数量增加的边。等价地说，它是一条不位于任何环上的边：如果有一个环经过它，那么该环的其余部分就提供了替代通路，删掉这条边也不会让任何东西断开。

如何找出图中的桥？

执行一次 DFS，为每个结点记录发现时间与 low-link，即从它的子树出发、至多经由一条回边所能抵达的最早发现时间。从 u 通往孩子 v 的树边是桥，当且仅当 low[v] > disc[u]，也就是 v 之下没有任何东西能抵达 u 或 u 之上。整个算法为 O(V + E)。

桥和割点有什么区别？

桥是删去后会让图断开的边；割点是产生同样效果的结点。两者出自同一次 DFS，差别只在一个比较：桥用严格大于，割点用大于等于。一个图可以只有其中一种而没有另一种。

桥可能位于某个环上吗？

不可能，而这也是理解它最清晰的角度。如果一条边位于某个环上，该环的其余部分就是其两端之间的替代通路，删掉它图仍然连通。桥恰恰就是那些不位于任何环上的边。

桥有什么用途？

用于找出电信与光纤骨干网中的关键链路、关闭后会把一个区域切开的必经道路与铁路区间、电网中脆弱的连接，以及软件依赖的风险分析。在 LeetCode 上，同一个问题以「网络中的关键连接」的形式出现。