なもり分解
なもりグラフから閉路を取り出し、もとのグラフから閉路に含まれる辺を削除する。 削除後のグラフは閉路に含まれる頂点を根とする森になっている。
有向グラフの場合は実装がより簡単になる。
code: Namori_decomposition.py
from collections import deque
def Namori_decomposition(N):
"""
N頂点N辺の単純連結無向グラフGから閉路を取り出す
Gに対して破壊的処理
"""
# bfsで後退辺を探す
while Q:
x = Q.popleft()
s = x
else:
Q.append(y)
# 後退辺の端点からdfs
while Q:
x = Q.pop()
s, t = x, y
else:
Q.append(y)
# dfs木を用いて閉路を復元
pos = s
while pos != t:
C.append(s)
# グラフから閉路に含まれる辺を取り除く
while s != t:
return C