割边(桥)

What · 是什么

割边(桥/bridge)是删除后使无向图连通分量数增加的边。判定与割点高度相似，同样用Tarjan的dfn/low数组：对于DFS树边u-v(v为u的子节点)，若low[v]>dfn[u]，则u-v是桥。因为v的子树除了经过u-v这条边，没有任何路径能到达u及其祖先。时间复杂度O(V+E)。在有重边的图中，直接跳过父节点会误判：两条重边之间本不构成桥，需改为记录'来时的边的编号'，只跳过同一条边而不跳过父节点。桥是边双连通分量的边界，求桥后去掉桥即可分解出边双连通分量。

Why · 为什么

How · 实现

伪代码

# 无重边版
tarjan(u, parent):
  dfn[u]=low[u]=++timer
  for v in adj[u]:
    if not visited[v]:
      tarjan(v,u)
      low[u]=min(low[u],low[v])
      if low[v]>dfn[u]: is_bridge[(u,v)]=True
    elif v!=parent:
      low[u]=min(low[u],dfn[v])

# 有重边版: 记录边编号, 只跳过来时边
tarjan(u, eid):  # eid为进入u时所经过边的编号
  dfn[u]=low[u]=++timer
  for (v,id) in adj[u]:
    if id==eid: continue
    if not visited[v]:
      tarjan(v,id)
      low[u]=min(low[u],low[v])
      if low[v]>dfn[u]: is_bridge[id]=True
    else:
      low[u]=min(low[u],dfn[v])

Python 实现

import sys

sys.setrecursionlimit(1 << 25)


def find_bridges(n, adj):
    """求无向图所有桥(含重边安全版本).
    adj[u] = [(v, edge_id), ...]
    return: 桥的边编号list
    """
    dfn = [0] * n
    low = [0] * n
    is_bridge = [False] * (len(sum(adj, [])) // 2 + 1)
    timer = [0]

    def dfs(u, parent_edge):
        dfn[u] = low[u] = timer[0] = timer[0] + 1
        for v, eid in adj[u]:
            if eid == parent_edge:
                continue
            if not dfn[v]:
                dfs(v, eid)
                low[u] = min(low[u], low[v])
                if low[v] > dfn[u]:
                    is_bridge[eid] = True
            else:
                low[u] = min(low[u], dfn[v])

    for s in range(n):
        if not dfn[s]:
            dfs(s, -1)
    return [eid for eid, b in enumerate(is_bridge) if b]


if __name__ == "__main__":
    # 测试1: 链 0-1-2-3, 所有边都是桥
    adj = [[] for _ in range(4)]
    eid = 0
    for u, v in [(0, 1), (1, 2), (2, 3)]:
        adj[u].append((v, eid))
        adj[v].append((u, eid))
        eid += 1
    assert find_bridges(4, adj) == [0, 1, 2], find_bridges(4, adj)

    # 测试2: 带环图, 仅环外挂边为桥
    # 0-1-2-3-0 环 + 2-4, 桥只有 2-4 (编号最后一条)
    adj2 = [[] for _ in range(5)]
    eid = 0
    for u, v in [(0, 1), (1, 2), (2, 3), (3, 0), (2, 4)]:
        adj2[u].append((v, eid))
        adj2[v].append((u, eid))
        eid += 1
    assert find_bridges(5, adj2) == [4], find_bridges(5, adj2)

    # 测试3: 重边: 0-1两条重边, 无桥
    adj3 = [[] for _ in range(2)]
    adj3[0].append((1, 0)); adj3[1].append((0, 0))
    adj3[0].append((1, 1)); adj3[1].append((0, 1))
    assert find_bridges(2, adj3) == [], find_bridges(2, adj3)

    # 测试4: 单边 0-1, 该边是桥
    adj4 = [[] for _ in range(2)]
    adj4[0].append((1, 0)); adj4[1].append((0, 0))
    assert find_bridges(2, adj4) == [0], find_bridges(2, adj4)

    print("bridge: ALL TESTS PASSED")

易错点

• 有重边时必须用边编号而非父节点标记，否则两条重边会被误判为桥
• 返祖边用dfn[v]更新low，树边用low[v]更新，二者不可混淆
• 割边判定条件为严格大于(>)而非>=：low[v]==dfn[u]意味着能绕回u，不是桥
• 桥判定不需要特判根节点(割点才需要)

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/cut/
• CP-Algorithms✓ https://cp-algorithms.com/graph/bridge-searching.html
• 书籍✓ CPH ch17 pp167-172