数据结构与算法 / 系统课时

桥和割点怎么一次找出

桥和割点怎么一次找出

桥和割点回答的是“删掉什么会让无向图断开”。只做一次 DFS,就能同时记录访问时间和子树能回到的最早祖先,从而判断哪些边是桥、哪些顶点是割点,并直接用于网络脆弱点分析。

学习目标

  • 理解 dfn 与 low 分别记录什么信息。
  • 掌握桥与割点的判定条件,以及根节点的特殊规则。
  • 用一次 DFS 在非连通无向图中同时找出桥和割点。

时间戳和低链接值解决什么

对顶点 u,dfn[u] 表示它第一次被 DFS 访问的时间。low[u] 表示从 u 的 DFS 子树出发,沿若干树边再至多经过一条返祖边,能够到达的最小 dfn。

因此,low 不是“最早访问时间”的简单复制,而是在回溯时把子树能够绕回祖先的能力向上传递。子树若完全绕不过父节点,就会暴露出桥或割点。

DFS 时间戳与低链接值关系

桥和割点的判定

设 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 是连接不同部分的关键边。

python
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)

预期输出

text
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]。前者问“这条边是否还能被绕过”,后者问“这棵子树删除当前顶点后是否还能连到更早祖先”,两者边界不同。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

桥和割点怎么一次找出

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通