トポロジカルソートとは？
トポロジカルソート(Topological Sort)は、有向グラフで全ての辺u→vについてuがvより前に来るよう頂点を一列に並べることです。履修の前提順序、作業スケジュール、ビルド依存のように「Aを終えないとBができない」という関係を順序に解きほぐすときに使います。
前提: サイクルのない有向グラフ(DAG)である必要があります。サイクルがあると「AはBより先、BはAより先」が同時に要求され、順序を決められません。
核心は入次数(in-degree)
入次数は「その頂点に入ってくる辺の数」=「まだ終わっていない先行作業の数」です。
入次数が0の頂点は今すぐできる作業です(先行がない)。それを処理すると、その頂点が指していた次の作業の先行が1つ減ります。この考えがKahnアルゴリズムです。
動作原理(Kahnアルゴリズム)
ステップ1. 全頂点の入次数を計算します。
ステップ2. 入次数0の頂点を全てキューに入れます。
ステップ3. 1つ取り出して結果に追加し、その頂点が指す隣接頂点の入次数を1ずつ減らします。0になった頂点をキューに入れます。
ステップ4. キューが空になるまで繰り返します。結果に全頂点が入れば成功、結果の長さが頂点数より少なければサイクルがあるという意味です。
AlgoNoteの可視化は、入次数が0になり「準備完了」状態になる頂点が順に抜ける過程を示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(V + E) |
| 空間 | O(V) |
全頂点と辺を一度ずつ見るのでO(V + E)です。
例で追ってみる
辺 A→B、A→C、B→D、C→D:
- •入次数: A=0, B=1, C=1, D=2
- •A処理 → B, C が0 → キューへ
- •B処理 → D=1、C処理 → D=0 → キューへ
- •D処理 → 結果
A, B, C, D(または A, C, B, D)
よくあるミス
- •サイクル未検出: 処理した頂点数がVより少なければサイクルです。この検査を抜くと誤った部分結果を答えにしてしまいます。
- •一意性の勘違い: トポロジカル順序は通常複数あります(入次数0が複数のとき)。問題が特定順(辞書順など)を求めるなら優先度付きキューを使います。
- •無向グラフへの適用: 方向がないとトポロジカルソートは定義されません。
AlgoNoteで直接確認しましょう
入次数0の頂点がキューに入り、処理されるたびに下流頂点の入次数が減る過程をAlgoNoteでステップごとに確認できます。