トポロジカルソート
概要
有向非巡回グラフ(DAG)に順位付けをすること。
例
Makefileで指定されたファイルのコンパイル順序の決定
実装例
実装例1 Kahn (1962)
入力辺を持たない頂点を探して1個選び、その頂点と、その頂点から出る辺を取り除くのを繰り返していく方法
計算量:ノードと辺の数に対して O(|V|+|E|)
実装例2 深さ優先探索 Tarjan (1976)
すべての頂点からDFSして、帰りがけ順に結果列に入れていく。最後にreverse
循環があっても気づけないので注意]
トポロジカル順序が一意になる場合
実装例1において、どのタイミングにおいても次に選ぶ頂点(入次数が 0 の頂点)の個数が1個なら一意になる