トポロジカルソート

トポロジカルソートは、有向非巡回グラフの全頂点を、各辺が前の頂点から後の頂点へ向かうように並べる。Kahn 法は入次数ゼロの始点を取り除く。DFS は復帰時に頂点を記録し、終了順を反転する。どちらも O(V + E) 時間で動き、有向閉路を拒否する。

科目の履修条件が例になる。全ての前提科目が完了して初めて次の科目を始められる。Kahn 法は今実行できる科目から進み、DFS は依存の連鎖を最後までたどり、戻りながら結果の後ろ側から配置する。

トポロジカルソートの仕組み

不変条件は、全ての辺 u -> v で u が v より前にあること。結果は一意とは限らない。残る前提がない二頂点は、外部の制約がなければどちらを先に置いてもよい。

Kahn 法は各頂点の残りの入次数を保持する。入次数ゼロの頂点をキューへ入れ、一つ取り出して答えに加える。その出辺の先で入次数を一ずつ減らし、ちょうどゼロになった頂点を入れる。全頂点を出力する前にキューが空になれば、残ったグラフには有向閉路があり、閉路に阻まれた下流の頂点も残りうる。

DFS は呼び出し開始時に活動中と記録し、全ての出辺の先が終了してから、その頂点を終了済みにしてリストへ追加する。このリストは後続の頂点が先になるので、反転するとトポロジカル順になる。活動中の祖先への辺は閉路を示し、再帰を続ける対象ではない。

失敗理由を示すなら Kahn 法が役立つ。残余グラフには閉路と、それに阻まれたタスクが含まれ、ビルドツールなどで診断に使える。反復なので長い依存鎖でも再帰スタックを使い果たさない。既存コードが再帰と活動中・終了済みの状態を持つなら、DFS を組み込みやすい。

トポロジカルソートのステップ

既定の Kahn 法の例は六頂点で、辺は A->C、B->C、B->D、C->E、D->E、D->F、E->F。

1. 入次数は A=0, B=0, C=2, D=1, E=2, F=2。
2. FIFO キューを [A, B] にする。文字順は再生を固定する規則で、グラフの追加制約ではない。
3. A を取り出して出力する。A->C を取り除くと C は 2 から 1 になる。まだ入れない。
4. B を出力する。B->C で C が 1 から 0 になり、キューへ入る。B->D で D も 1 から 0 になり、後に続く。キューは [C, D]、出力は [A, B]。
5. C を出力する。E は 2 から 1 になり、まだ待つ。
6. D を出力する。D->E で E がゼロになって入り、D->F で F は 2 から 1 になる。キューは [E]。
7. E を出力する。E->F で F がゼロになり、最後に F を出力する。
8. キューが空で六頂点全てを出力したので、[A, B, C, D, E, F] を返す。
9. 検証ではこの順に並べ、七辺が全て右向きかを調べる。DFS の [B, D, A, C, E, F] でも繰り返し、両方が通る。全辺が右を向けば、辺をたどって始点へ戻ることはできず、閉路がないことも示せる。

同じグラフで DFS が終了する順序は [F, E, C, A, D, B]。反転すると [B, D, A, C, E, F] になる。Kahn 法とは違っても、どちらも全ての依存を満たす。

Kahn モードでは in=k がゼロになってキューへ入る瞬間を見る。DFS モードでは、後続が全て終了して緑になってから頂点が終了行に入ることを確認する。

時間計算量と空間計算量

グラフ自体は O(V + E) を使う。Kahn 法は入次数、キュー、出力を追加で持つ。DFS は三状態の表、終了リストを持ち、長い鎖では呼び出しが O(V) フレームになる。比較ソートではないので、その O(n log n) 下界は関係しない。全隣接リストを読むだけでも O(V + E) かかる。

境界ケース

• 一頂点で辺がなければ、両手法ともその頂点を返す。
• 複数頂点で辺がなければ、全ての順列が合法。固定規則は再現性のためにある。
• 一つの鎖では順序が一意になる。先頭以外は直前の頂点を前提とする。
• 非連結の DAG でも全ての部分を処理する。DFS は全頂点の外側ループが必要で、一頂点からだけでは到達可能部分しか調べない。
• 自己ループや有向閉路があれば順序は存在しない。Kahn 法は未処理頂点を残し、DFS は活動中の頂点への辺を見つける。

よくある間違い

• 入次数一でキューへ入れる。一つでも未完了の前提があれば実行できず、ゼロへの変化を待つ。
• 最初に見た頂点を通常の BFS のように利用可能とする。Kahn 法では残りの入次数が決める。
• DFS の入口で答えに追加する。それは先行順で、他の前提に違反しうる。復帰時に追加して反転する。
• 一つの訪問ビットで閉路を検出する。活動中と終了済みを分ける必要があり、終了済みへの辺は閉路の証拠ではない。
• Kahn 法が止まった後に部分リストを返す。長さが V か確認する。合法な接頭部分でも全体のトポロジカル順にはならない。