橋検出(Bridge-finding)

概要

グラフ \(G = (V, E)\) において橋(除去するとグラフが連結でなくなる辺)を検出する。

計算量

\(O(|V| + |E|)\)

実装

橋検出して縮約したグラフを返す実装。 多重辺にも対応できるようにしている。

# Bridge-Finding
# 橋、二重辺連結成分分解
# g: 隣接リスト, v: 頂点数, s: 探索開始地点
#
# DFS木を求めながら橋を見つけ、グラフを縮約していく
def bridge_finding(G, N, start=0):
    fin = [False] * N
    v_cnts = [0] * N
    used = [False] * N
    bG = [[] for i in range(N)] # 縮約後のグラフ
    bV = [[] for i in range(N)] # 各ノードに縮約される元頂点
    def dfs(v, prev, edges, conts):
        cur_c = prev_c = 0
        used[v] = True
        conts.append(v)
        for w in G[v]:
            if used[w]:
                if w==prev:
                    # (v, prev)の多重辺対応
                    if prev_c == 1:
                        v_cnts[prev] -= 1
                        cur_c += 1
                    prev_c += 1
                elif not fin[w]:
                    v_cnts[w] -= 1
                    cur_c += 1
            else:
                w_edges = []; w_conts = []
                ret = dfs(w, v, w_edges, w_conts)
                if ret > 0:
                    edges += w_edges
                    conts += w_conts
                else:
                    # (v, w)は橋
                    bG[w] = w_edges
                    for u in w_edges:
                        bG[u].append(w)
                    bV[w] = w_conts
                    edges.append(w)
                cur_c += ret
        fin[v] = True
        cur_c += v_cnts[v]
        return cur_c
    dfs(start, -1, bG[start], bV[start])
    for u in bG[start]:
        bG[u].append(start)
    return bG#, bV

単純にグラフ内で橋となる辺(頂点のペア)を返す実装。

# 単純に橋となる辺を返す
def bridge(G, N):
    result = set()
    label = [None]*N
    gen = 0
    cost = [0]*N
    def dfs(u, p):
        nonlocal gen
        res = 0
        for v in G[u]:
            if v == p:
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                r = dfs(v, u)
                if r == 0:
                    result.add((u, v) if u < v else (v, u))
                res += r
        res -= cost[u]
        return res
    for v in range(N):
        if not label[v]:
            label[v] = gen; gen += 1
            r = dfs(v, -1)
            assert r == 0, r
    return result

参考

戻る