一个无向图可能有许多环,却仍然依赖某一条边连接两个很大的区域。如果逐条删除边并重新遍历,便会重复大量相同的工作。深度优先搜索(DFS)只需运行一次,就能判断每个子树是否有另一条路返回其连通分量的其余部分。
为此需要引入低链值。理解其含义,而不只是记住公式,才能明白判桥时为什么使用严格不等式。边的身份同样重要:端点相同的两条边仍是两条不同的路径;如果把它们都当作“通向父节点的连接”而跳过,就可能错误地判出一条桥。
相对于原有连通分量数定义边失效
定义 10.1.1
(无向多重图中的桥)
设 是有限无向图。允许平行边和自环,并为每条边赋予不同的 ID。删除一条边只删除该 ID 所对应的边。若删除一条边使连通分量的数量增加,就称这条边为桥。
图原本可以不连通。因此,仅凭删除后图不连通还不足以判定桥;连通分量数必须增加。自环绝不是桥,因为删除自环不会改变不同顶点之间的连通性。
证明透视
桥恰好是不存在其他端点路径的边
设边 的端点为 。如果删除 之后仍有从 到 的路径,那么任何原来经过 的路线都可用这条替代路径代替该步,所以原来的连通分量不会分裂。因此 不是桥。
反过来,如果删除后其端点不再连通,那么它们原来的连通分量已经分裂,连通分量数便增加。对于自环,可取从端点到自身的长度为零的路径作为替代路径。
删除一条边至多把原分量分成两部分:任意顶点到 的原有简单路径,要么避开该边,要么在跨越它之前到达 。因此,删除后该顶点仍与 或 连通。桥恰好使连通分量数增加一。
当端点不同时,可将替代路径选为简单路径;它与 一起构成一个环。反之,包含 的任意环去掉 后,剩余部分就是一条替代路径。我们将自环视为长度为一的环,将两条平行边视为长度为二的环。按照这些约定,一条边是桥,当且仅当它不在任何环上。
DFS 树限制了返回边可能到达的位置
运行深度优先搜索,并在每遇到一个尚未访问的顶点时开始一棵新的根树。顶点第一次被发现时,用全局递增时钟赋予它发现时间 。发现新顶点所用的边构成 DFS 森林。顶点的子树由该顶点及其在森林中的所有后代组成。
在无向图的 DFS 中,每条非树边连接一个顶点和它的祖先或后代;自环是退化情形。两个互不为祖先后代的已完成 DFS 子树之间不存在边:较早被遍历的子树检查到这样的边时,就会在结束之前发现另一端点。
因此,离开某个子树的另一条边必定通向祖先。正是这一结构性质,使最小发现时间能够证明是否存在返回路径。
定义 10.1.2
(低链值的含义与递推)
定义 为以下方式能到达的最小发现时间:从 出发,沿零条或多条 DFS 树边向下走,再至多经过一条非树边到达祖先;也允许完全不移动。
因此,初始化 。对于 DFS 子节点 ,在其遍历完成后,用 更新当前值。对于经由不同于父树边本身的边到达的已发现邻点 ,用 更新当前值。
证明透视
每次更新都对应一条允许的路径
初始值对应留在 。若路径先沿树边向下进入子节点 ,其余部分就是 所概括的路径之一;因此子节点完成后的值恰好提供这些可能性。
从 到祖先 的非树边直接到达发现时间 。从祖先一端检查边时,也可能遇到已访问的后代;后代的发现时间大于 ,不会降低当前值。对它同样取最小值是无害的。
每条允许的向下路径要么留在当前顶点,要么先进入某个子树。这些情况覆盖了定义中的所有可能,故按 DFS 返回顺序归纳即可证明递推正确。父树边必须排除:立刻沿正在考察的同一条边返回,并不是替代路径。
低链值是发现时间,不是连通分量大小、回边数量或最短路径长度。只有所有后代都处理完毕,子节点的低链值才完整。
常见错误
(在子节点返回之前就测试)
子节点的 low 值要等到它的所有后代都处理完才是最终值。在从 出发探索的三角形 中,顶点 2 的初始值是 。若用这个初始值对 作测试,会把边 当成桥;但 2 到 0 的非树边把 降到 ,所以它不是桥。
判桥条件是严格不等式
定理 10.1.3
(DFS 树边的桥判据)
设 为从 到其 DFS 子节点 的树边。则 是桥,当且仅当 。每条非树边(包括自环)都在某个环上,所以不是桥。
证明透视
从 u 到 v 的树边是桥,当且仅当 low[v] > tin[u]
设 是 的 DFS 子节点,考虑把 的整个子树与其连通分量的其余部分分开的割。它们之间的父树边跨越这个割。其他跨割边必是从 的某个后代通向 或 的祖先的非树边。
这样的边存在,当且仅当 。它提供一条绕过父树边的路径:先在子树内走到这条边,再跨到祖先所在一侧,最后利用该侧的树路径。因此,由替代路径刻画可知,父树边不是桥。
如果 ,就没有其他边跨越这个割。删除父树边会使整个子树与外部断开,所以它是桥。非树边则与一条树路径共同构成环,本身不可能是桥。
等号十分重要: 意味着还有另一条路径回到 本身,这已足以绕过树边。若误用 代替 ,就会把这样的环上边错误标记为桥。
跳过父边,而不是跳过所有通向父顶点的边
反例模式
平行边揭示两种处理的区别
取顶点 0 和 1,用 ID 分别为 0 和 1 的两条边连接。DFS 通过边 0 发现顶点 1。在顶点 1 处,跳过边 0:这是其父树边在当前端点对应的邻接项。边 1 仍通向顶点 0,因而将 降至 。
两条边都不是桥:删除任意一条,另一条仍连接两个顶点。如果程序跳过所有邻点等于父顶点的邻接项,就会把两条边都跳过,使子节点低链值过高,错误地将树边判为桥。
不同的边 ID 保存了已经经过的父边与平行替代路径之间的实际区别。
完整例子:包含孤立顶点
例题 10.1.4
(一个环、一条桥、一对平行边与另一条桥)
使用顶点 0 至 6,并按下列顺序输入边:
| 边 ID | 端点 | 在所得图中的作用 |
|---|---|---|
| 第一个三角形 | ||
| 第一个三角形 | ||
| 第一个三角形 | ||
| 通向平行边对的连接 | ||
| 两条平行边之一 | ||
| 另一条平行边 | ||
| 通向顶点 5 的连接 |
顶点 6 是孤立顶点。按递增顺序处理根,并按输入顺序检查邻接项,得到:
| 顶点 | 发现时间 | 完成后的低链值 |
|---|---|---|
三角形中从 2 到 0 的边将顶点 2 的值降至零,再传给顶点 1。第二条平行边将顶点 4 的值降至发现时间 3。因此树边 4 对应等号,不是桥。顶点 5 无法绕路返回,所以边 6 是桥。同样,,因此边 3 是桥。
桥的 ID 为 [3, 6]。孤立顶点需要自己的 DFS 根,但没有需要检验的父边。
例题 10.1.5
(自环与一条路径)
取 及编号 的边:、、。在顶点 0,自环的边端编号为 ,不是父边,而且端点已被发现,所以它把 贡献给 ,而 本来就是 。树是链 ,,且 、。边 2 有 ,边 1 有 ,所以两者都是桥。自环从不作为树边被测试,也不是桥。桥的 ID 为 [1, 2]。
重放同一张图,观察每次返回,并将实体删边结果与两种刻意错误的规则比较。
迭代实现必须保留返回事件
代码使用合法整数顶点编号 ,并以输入位置作为边 ID。每个栈帧记录一个顶点及下一个邻接项的位置。进入子节点前先推进该位置。子节点的栈帧结束时,更新父节点并进行判桥,这相当于递归 DFS 调用的返回。
def bridge_edges(n, edges):
if n < 0:
raise ValueError("vertex count must be nonnegative")
edges = list(edges)
adjacency = [[] for _ in range(n)]
for edge_id, (u, v) in enumerate(edges):
if not (0 <= u < n and 0 <= v < n):
raise IndexError("edge endpoint outside the vertex set")
adjacency[u].append((v, edge_id))
adjacency[v].append((u, edge_id))
tin = [-1] * n
low = [-1] * n
parent = [-1] * n
parent_edge = [-1] * n
is_bridge = [False] * len(edges)
timer = 0
for root in range(n):
if tin[root] != -1:
continue
tin[root] = low[root] = timer
timer += 1
stack = [(root, 0)]
while stack:
vertex, next_index = stack[-1]
if next_index == len(adjacency[vertex]):
stack.pop()
edge_id = parent_edge[vertex]
if edge_id != -1:
predecessor = parent[vertex]
low[predecessor] = min(low[predecessor], low[vertex])
if low[vertex] > tin[predecessor]:
is_bridge[edge_id] = True
continue
stack[-1] = (vertex, next_index + 1)
neighbor, edge_id = adjacency[vertex][next_index]
if edge_id == parent_edge[vertex]:
continue
if tin[neighbor] != -1:
low[vertex] = min(low[vertex], tin[neighbor])
else:
parent[neighbor] = vertex
parent_edge[neighbor] = edge_id
tin[neighbor] = low[neighbor] = timer
timer += 1
stack.append((neighbor, 0))
bridge_ids = [edge_id for edge_id, flag in enumerate(is_bridge) if flag]
return bridge_ids, tin, low
每个顶点只被发现一次。每条无向边都提供两个邻接项,自环也一样;每个邻接项只检查一次。每次栈操作、低链值更新和边标记都只需常数时间。最后的线性扫描按输入顺序返回桥的 ID,无须排序。总时间和空间复杂度均为 。显式栈帧还避免了长路径上的递归调用深度限制。
返回的低链值取决于具体 DFS 顺序,而桥的集合是图本身的性质。改变邻接表顺序可能改变发现时间和低链值,却不会改变哪些边是桥。
删除桥,观察稳固区域之间的森林
定理 10.1.6
(桥森林)
设 有 个连通分量和 条桥。删去所有桥后恰好剩下 个分量,而且其中没有分量含桥。把每个余下的分量缩成一个顶点,再放回各条桥,得到一个森林。
证明
(缩合无桥区域)
设原图有 个连通分量和 条桥。删除所有桥,再求剩余图的连通分量。先删除其他桥后,每一条原有的桥仍然是桥:删边不可能为它创造新的替代路径。因此每次删除都使连通分量数增加一,最终得到 个分量。
每条原本不是桥的边都在某个环上,而环上的任何边都不是原图的桥。这些环在删桥后仍然完整,因此剩余各分量内部没有桥。
将每个剩余分量收缩成一个顶点,并恢复原有的桥,连接相应的收缩顶点。所得图是一片森林。若收缩后的顶点之间有环,展开各收缩分量内部的路径后,就能得到绕过环上每一条桥的替代路径,与它们是桥矛盾。
在上例中,原来的 、 给出四个区域:、、 和 。桥森林是一条三个顶点的路径,外加一个孤立顶点。
反例模式
割点是另一种失效对象
取两个共用顶点 2 的三角形,顶点集合分别为 和 。每条边都在三角形上,因此没有桥。但删除顶点 2 及其所有关联边后, 与 分离,所以 2 是割点。
判桥考虑删除一条边;判断割点则考虑删除一个顶点及其关联边。严格的判桥不等式本身并不能直接给出删点算法。
常见错误
(边与顶点的测试用了同一个门槛)
对从 到 的树边,桥需要严格的 ,因为回到 本身的路已经绕过该边。对割点 ,子节点 把子树分开的条件是 ,因为删去 同时毁掉只回到 的路。对边 加两条 ,等式 说明 不是桥,但顶点 1 是割点。
练习与详解
快速检查
(1. 比较连通分量数,而非只判断是否不连通)
一个图原本有两个连通分量。删除一条边后仍有两个分量。这条边是桥吗?如果删除后有三个分量呢?
解答 · 解答 1
仍为两个分量时,它不是桥;增加到三个时,它是桥。定义比较的是删除前后的数量;原本不连通的图也可以同时包含桥和非桥。
快速检查
(2. 正确理解等号)
DFS 树边从 通向子节点 ,且 、。它是桥吗?等号说明了什么?
解答 · 解答 2
它不是桥。某条从子树出发的路径通过非树边到达 ,避开了父树边。回到 本身已经足够,不必到达 的严格祖先。这就是判定使用 而不是 的原因。
快速检查
(3. 保留平行的替代路径)
两个顶点之间有两条平行边。DFS 把第一条用作树边。在子节点处应跳过哪个邻接项?第二条边应如何影响低链值?
解答 · 解答 3
只跳过具有第一条边 ID 的邻接项。第二条边仍提供通向父节点的非树路径,将子节点低链值降至父节点的发现时间。两条边都不是桥,因为删除其中一条后另一条仍在。
快速检查
(4. 完成例子中的判桥)
在七顶点例子中,用完成后的值检验 ID 为 3、4 和 6 的树边。为什么必须等子节点完成后才能检验?
解答 · 解答 4
边 3 满足 ,所以是桥。边 4 满足 ,所以不是桥。边 6 满足 ,所以是桥。后代可能发现返回边并降低子节点的值;若在返回前检验,使用的值可能尚未完成,从而误报桥。
快速检查
(5. 区分边失效和顶点失效)
为什么两个共用一个顶点的三角形没有桥,却有割点?自环会是桥吗?
解答 · 解答 5
每条边都有绕三角形另一侧的替代路径。然而,删除共用顶点会移除两个三角形之间唯一的共同连接,使其余顶点分离。自环不连接不同顶点,删除它不会增加连通分量数,因此它绝不是桥。
快速检查
(6. 计算删除所有桥后的区域数)
一个图原本有三个连通分量和四条桥。删除所有桥后还剩多少个连通分量?解释为什么先删除的一条桥不可能给后面的一条桥创造新的替代路径。
解答 · 解答 6
共有 个连通分量。删边只会移除路径,不会创造路径,所以尚未删除的原有桥仍没有连接其端点的替代路径。每次删除使分量数增加一。将七个区域收缩并保留四条桥,得到一片有三个连通分量的森林。