トポロジカルソート

DAGの頂点列のうち、全ての有向辺に関して始点が終点よりも先行して現れる系列を求めるアルゴリズム

深さ優先探索(後行順)をして得られる系列の逆順がちょうどこれにあたる。

DFS(後行順)のラベル付の性質による

子孫が祖先よりも先に探索される。

TODO 図を加える。

まあまあ厳密に書くと

$ G := (V, E): DAG

$ Gに対して、以下を満たすよう、$ Vの全要素を含むリスト$ Lを得る。

$ \mathrm{index}(v)を$ L中の$ vの頂点とする。

$ \forall (v, w) \in E; \mathrm{index}(v) < \mathrm{index}(w)

(0) 事前準備

0-0. トポロジカルソートの結果の配列として、$ L = ［］とする。

(1) DFSとトポロジカルな系列 (in $ L, out $ \hat{L})

1-1. DFSの開始点として、任意の点$ v \in V - Lを選ぶ

$ V - Lは未探索点に当たる。初期状態では$ Vそのもの。

1-2. $ vを中心に後行順の深さ優先探索を行い、頂点のアクセス系列を表す$ L_vを得る。

$ L_v: $ vから到達可能な頂点全体からなるリスト

1-3. $ L_vの逆順の系列$ \hat{L_v}を求める。

この$ \hat{L_v}は部分的にトポロジカルソートの事後条件を満たす。

$ \hat{L_v}も$ vから到達可能な頂点全体からなるリスト。 ... (1)

(2) 求まったトポロジカルな順列を整理する。

2-1 $ L := \hat{L} + L

$ \hat{L}を$ Lに先頭から連結する。

先頭から繋げる理由

前提: $ Gが連結。

(1)の$ vから到達不能な頂点全体には、$ vを終点とする辺の始点が存在するため。

系列内にて、その始点が終点よりも先に来なければならない。

2-2 $ V - L = \emptyならば終了。そうでなければ(1)に戻る。

空集合であれば、全ての頂点を探索したことになる。

付記

入ってくる辺を持たない$ v \in Vを発見できれば、連結なグラフについては手順1を一発で済ませられる。

紙の上で動かす際にはそれが都合いい。

DFSが先行順, 中順だとうまくいかない。

出力順において、必ずしも祖先 < 子孫とはならないため。