橋検出(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