数据结构与算法 / 系统课时
桥和割点怎么一次找出
桥和割点怎么一次找出
桥和割点回答的是“删掉什么会让无向图断开”。只做一次 DFS,就能同时记录访问时间和子树能回到的最早祖先,从而判断哪些边是桥、哪些顶点是割点,并直接用于网络脆弱点分析。
学习目标
- 理解
dfn与low分别记录什么信息。 - 掌握桥与割点的判定条件,以及根节点的特殊规则。
- 用一次 DFS 在非连通无向图中同时找出桥和割点。
时间戳和低链接值解决什么
对顶点 u,dfn[u] 表示它第一次被 DFS 访问的时间。low[u] 表示从 u 的 DFS 子树出发,沿若干树边再至多经过一条返祖边,能够到达的最小 dfn。
因此,low 不是“最早访问时间”的简单复制,而是在回溯时把子树能够绕回祖先的能力向上传递。子树若完全绕不过父节点,就会暴露出桥或割点。

桥和割点的判定
设 v 是 DFS 树中 u 的子节点。若 low[v] > dfn[u],说明 v 的整棵子树无法绕过边 u-v 回到 u 或更早祖先,因此 u-v 是桥。
割点条件稍有不同。若 u 不是 DFS 根节点,并且存在子节点 v 满足 low[v] >= dfn[u],那么删除 u 后,v 的子树无法通过返祖边连接到 u 的祖先,u 是割点。根节点没有祖先,只有当它在 DFS 树中至少有两个独立子树时才是割点。
一次 DFS 同时求出两类结果
下面的示例给每条无向边分配唯一编号,因此对普通图和含重边的图都能正确处理父边。图中 0-1-2-0 构成环,而 1-3、3-4、3-5 是连接不同部分的关键边。
def find_bridges_and_articulations(n, edges):
graph = [[] for _ in range(n)]
# 用边编号区分真正的父边与平行边。
for eid, (u, v) in enumerate(edges):
graph[u].append((v, eid))
graph[v].append((u, eid))
dfn = [-1] * n
low = [-1] * n
bridges = []
articulations = set()
timer = 0
def dfs(u, parent_eid=-1):
nonlocal timer
dfn[u] = low[u] = timer
timer += 1
child_count = 0
for v, eid in graph[u]:
if eid == parent_eid:
continue
if dfn[v] == -1:
child_count += 1
dfs(v, eid)
# 回溯时把子树能到达的最早祖先信息向上传递。
low[u] = min(low[u], low[v])
if low[v] > dfn[u]:
bridges.append(tuple(sorted((u, v))))
# 非根节点满足该条件时,删除 u 会截断这棵子树。
if parent_eid != -1 and low[v] >= dfn[u]:
articulations.add(u)
else:
# 已访问邻点提供一条返祖路径,尝试降低 low[u]。
low[u] = min(low[u], dfn[v])
if parent_eid == -1 and child_count >= 2:
articulations.add(u)
for start in range(n):
if dfn[start] == -1:
dfs(start)
return sorted(set(bridges)), sorted(articulations)
if __name__ == "__main__":
edges = [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (3, 5)]
bridges, cuts = find_bridges_and_articulations(6, edges)
print("bridges:", bridges)
print("articulations:", cuts)预期输出
bridges: [(1, 3), (3, 4), (3, 5)]
articulations: [1, 3]这段代码的时间复杂度是 O(V + E),因为每个顶点只进入 DFS 一次,每条无向边最多从两个方向检查一次;额外空间主要来自邻接表、DFS 栈和几个长度为 V 的数组。
容易写错的边界
非连通图必须从每个未访问顶点重新启动 DFS,否则只能得到起始连通分量中的结果。根节点的割点判定不能套用非根公式,否则只有一个 DFS 子树的根也可能被误判。
桥使用严格条件 low[v] > dfn[u],割点使用非严格条件 low[v] >= dfn[u]。前者问“这条边是否还能被绕过”,后者问“这棵子树删除当前顶点后是否还能连到更早祖先”,两者边界不同。