DAGのトポロジカルソート
Abstract
有向非巡回グラフ$ G = (V, E)は, $ O(|V| + |E|)timeでトポロジカルソートが可能.
Explanation
Definition (DAG)
有向グラフ$ G = (V, E)が非閉路的 (acyclic) であるとは, $ Gが有向閉路をもたないことをいう.
非閉路的な有向グラフを有向非巡回グラフ (DAG) と呼ぶ (DAGはDirected Acyclic Graphのアクロニムである).
Definition (トポロジカル順序)
有向グラフ$ G = (V, E)のトポロジカル順序 (topological order) とは,
$ Vの各頂点への番号付け$ \mathrm{top} \colon V \to \{ 0, \dots, |V|-1 \}であり,
各辺$ e \in Eに対して$ \mathrm{top}(\partial^{+} (e)) < \mathrm{top}(\partial^{-} (e))が成り立つもののこと.
以下の定理が成立する.
Theorem (DAGの特徴づけ)
有向グラフ$ Gが非閉路的$ \Longleftrightarrow有向グラフ$ Gはトポロジカル順序によるソート (トポロジカルソート) ができる.
Proof
($ \Leftarrow) 背理法.
有向閉路があるとトポロジカルソートの性質が満たされず矛盾.
($ \Rightarrow) グラフの頂点数$ nに関する帰納法.
$ n=1のときは成立. $ n = k-1のときの成立を仮定し, $ n = kのときも成立することを示す.
グラフ$ Gは非閉路的なので, 入次数0の頂点$ vが存在する (ないとすると矛盾する).
この頂点$ vを$ Gから取り除いたグラフ$ G - vは仮定よりトポロジカルソートを持ち, これを利用して$ Gのトポロジカルソートも得ることができる. $ \blacksquare
TODO きちんと示す.
DAGの頂点のトポロジカルソートを行うアルゴリズムとして, 以下のKahnのアルゴリズムが知られている.
Algorithm (Kahn)
Input:
有向グラフ$ G = (V, E).
Output:
- $ GがDAGならば, トポロジカル順序$ \mathrm{top} \colon V \to \{ 0, \dots, |V|-1 \}.
- $ GがDAGでないならば, 'DAGでない' と判定.
1. $ k \gets 0と初期化し, グラフ$ Gに関して$ \mathop{\mathrm{indeg}}_G (v) = 0となる頂点$ vが存在する間, 次を繰り返す.
1-1 任意に$ \mathop{\mathrm{indeg}}_G (v) = 0となる頂点$ vを選び, $ \mathop{\mathrm{top}} (v) := kと定める. $ k \gets k+1とインクリメントする.
1-2 グラフ$ Gから頂点$ vを取り除き, $ G \gets G - vと更新する.
2. すべての頂点$ vに対して$ \mathop{\mathrm{top}}が定義されていれば, $ \mathop{\mathrm{top}}を出力する. そうでなければ, 'DAGでない' と判定する.
Kahnのアルゴリズムの正当性は, Theoremの証明そのものである.
Implementation
Kahnのアルゴリズムを実装した. 具体的には, 以下のようにすればよい.
1. 空のリスト$ Lを用意する.
2. 空の キュー$ Qに入次数0の頂点をすべて入れる (入れる順序は任意). 3. キュー$ Qに頂点が残っている限り, 以下を行う.
3-1. キュー$ Qの先頭から頂点$ vを取り出し, $ vをリスト$ Lの末尾に追加.
3-2. 頂点$ vに隣接する各頂点$ u \in N(v)の入次数を1だけ減らす. その結果 $ u \in N(v)の入次数が0になった場合, $ uをキュー$ Qの最後尾に追加.
4. ソート済みリスト$ Lにグラフのすべての頂点が含まれていれば, $ Lを出力する. そうでなければ, 入力されたグラフはDAGでないと判定する.
Input
グラフ (頂点は0-indexed, 連結とは限らない) の隣接リスト E
Output
グラフがDAGなら, そのトポロジカルソート top_sorted を返す.
そうでないなら, None を返す.
Time complexity
$ O(|V| + |E|)time.
code:python
from collections import deque
def topological_sort(E):
'''
Kahn's Algorithm (O(|V| + |E|) time)
Input:
E: the adjacency list of the digraph
Output:
If the input digraph is acyclic, then return a topological sorting of the digraph.
Else, return None.
'''
N = len(E)
for ends in E:
for v in ends: indegv += 1 q = deque([v for v in range(N) if indegv == 0]) top_sorted = []
while q:
v = q.popleft()
top_sorted.append(v)
if indegu == 0: q.append(u) if len(top_sorted) == N: # The input digraph is acyclic.
return top_sorted
else: # There is a directed cycle in the digraph.
return None
Verification
References
浅野孝夫, 『離散数学 —グラフ・束・デザイン・離散確率—』, サイエンス社, 2010.
J. Kleinberg and É. Tardos, 『アルゴリズムデザイン』, 共立出版, 2008.
T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 『アルゴリズムイントロダクション 第3版』, 近代科学社, 2009.