強連結成分分解
Abstract
強連結成分分解は, 深さ優先探索を用いて$ O(|V|+|E|)timeで行える. Explanation
Definition (強連結)
有向グラフ$ G = (V, E)が強連結(strongly connected) であるとは, $ Gの任意の2頂点$ u, vに対して,
$ u, v-有向パスと$ v, u-有向パスがともに存在することをいう.
Definition (強連結成分)
有向グラフ$ G = (V, E)の頂点集合$ Vを, 次が満たされるような極大な$ k個の集合に$ V = \bigsqcup_{i=1}^{k} V_iと分割する:
任意の$ i=1, \dots, kと, 任意の2頂点$ u, v \in V_iに対して, $ u, v-有向パスと$ v, u-有向パスがともに存在する.
この分割は一意的に定まる.
各$ V_iが誘導する部分グラフ$ G_i = (V_i, E_i)を$ Gの 強連結成分 (strongly connected component) という.
有向グラフを強連結成分に分解するアルゴリズムとしては, Kosaraju-Sharirのアルゴリズムが知られている.
Algorithm (Kosaraju-Sharir)
Input:
有向グラフ$ G = (V, E).
Output:
$ Gの強連結成分の頂点集合$ V_1, \dots, V_k.
1. 有向グラフ$ Gの頂点に深さ優先探索を行い, 全頂点にDFSによる後行順序をつける. 2. 有向グラフ$ Gのすべての辺の向きを逆にしたグラフ$ \overleftarrow{G}を作る.
3. グラフ$ \overleftarrow{G}の全頂点を「未探索」と状態を設定し, $ i \gets 1と初期化する
4. 「未探索」の頂点がある間, 次を行う:
4-1 「未探索」の頂点の中で手順1での順序が最も大きい頂点$ vを選ぶ.
4-2 頂点$ vを始点とし, グラフ$ \overleftarrow{G}のDFSを行う. DFSで訪れた頂点は「未探索」から「探索済み」の状態に変更する.
4-3 「探索済み」となった頂点の集合を$ V_iとする.
5. $ V_1, \dots, V_kを出力する.
TODOアルゴリズムの正当性を示す.
Implementation
グラフ構築
Input
グラフの頂点数 N
グラフの各有向辺の始点 init, 終点 end
Output
グラフの隣接リスト E
Time complexity
$ O(|E|)time.
強連結成分の計算
Input
なし
Output
強連結成分の数 k
どの強連結成分に属するかを表すリスト scc
Time complexity
$ O(|V|+|E|)time.
code:python
class StronglyConnectedComponents:
def __init__(self, N):
self.N = N
self.E = [[] for _ in range(N)]
self.reverse_E = [[] for _ in range(N)]
self.postorder = []
def add_edge(self, init, end):
self.reverse_Eend.append(init) def _dfs(self, E, s):
postorder = [] # a dfs postordering of each vertex
while stack:
v, p, st = stack.pop()
if st == 0 and not self.visitedv: # visited v for the first time n_children = 0
if self.visitedu: continue if n_children == 0:
n_children += 1
else:
n_children += 1
if n_children == 0: # v is a leaf
postorder.append(v)
elif st == 0 and self.visitedv: # the edge (v, p) is a back edge continue
elif st == 1: # now searching
continue
else: # search finished
postorder.append(v)
return postorder
def components(self):
self.postorder = []
for v in range(N):
order = self._dfs(self.E, v)
self.postorder += order
k = 0
while self.postorder:
v = self.postorder.pop()
order = self._dfs(self.reverse_E, v)
for u in order: self.sccu = k k += 1
return k, self.scc
Verification
References
繁野麻衣子, 『ネットワーク最適化とアルゴリズム』, 朝倉書店, 2010.