トポロジカルソート入門から実装まで：DAGの依存関係を解くKahn法とDFS法の完全ガイド
エバープレイ編集部トポロジカルソートとは
トポロジカルソート（topological sort）は、有限な有向グラフの頂点を「依存関係を満たす順序」で並べ替える手法です。具体的には、グラフの各有向辺 u → v に対して、並べた順序では u が v より前に来るような並びを作ることを指します。これは有向グラフが「循環（サイクル）を含まない」場合にのみ可能であり、そのようなグラフは有向非巡回グラフ（Directed Acyclic Graph, DAG）と呼ばれます。
基本概念：DAG と部分順序
トポロジカルソートが意味を持つのは、グラフが DAG のときです。DAG は「あるタスクが別のタスクに依存している」関係や、「講義の履修順」「ソースファイルの依存関係」「パッケージの依存関係」などを表現するのに適しています。グラフの有向辺は「先行関係（precedence）」を表し、トポロジカルソートはその部分順序（partial order）に対する線形拡張（linear extension）を生成します。
トポロジカルソートの存在条件
- トポロジカル順序が存在することと、グラフが有向閉路（Directed cycle）を含まないことは同値です。つまり、トポロジカルソートが可能である ⇔ グラフは DAG である。
- 逆に、グラフにサイクルがある場合は、ある頂点 u が v に依存し、同時に v が u に依存するような矛盾が生じ、トポロジカル順序は存在しません。
代表的なアルゴリズム
トポロジカルソートを求める代表的なアルゴリズムは大きく二つあります。どちらも時間計算量は O(V + E)（頂点数 V と辺数 E）です。
Kahn のアルゴリズム（幅優先的アプローチ）
Kahn のアルゴリズムは入次数（in-degree）に着目します。手順は次の通りです：
- 各頂点の入次数を計算する。
- 入次数が 0 の頂点をキュー（あるいは優先度付きキュー）に入れる。
- キューから頂点 u を取り出し、出力順に追加する。u から出る各辺 u → v を削除（実際は v の入次数を 1 減らす）し、v の入次数が 0 になればキューに追加する。
- これをキューが空になるまで繰り返す。出力された頂点の数が V に満たないならグラフにサイクルが存在する（トポロジカル順序は存在しない）。
キューを優先度キュー（最小ヒープ）にすると、辞書順や番号が小さい順に並べるなどの「決定的・最良（lexicographically smallest）」なトポロジカル順を得ることができます。
DFS（深さ優先探索）を用いる方法（逆終了時刻）
もう一つは深さ優先探索（DFS）の終了時刻（postorder）を利用する方法です。手順は：
- すべての頂点を未訪問にする。
- 未訪問の頂点から DFS を開始する。ある頂点の再帰訪問が終わったら（すべての子を訪問し終えたら）その頂点をスタックに積む（あるいは出力リストの先頭に挿入する）。
- 全探索が終わった後、スタックの取り出し順（または出力リストの逆順）がトポロジカル順序になる。
DFS 法では、探索中に「後退辺（back edge）」を見つけた場合、それはサイクルの存在を示します。DFS ベースと Kahn 法はどちらも正しさと計算量 O(V+E) を満たしますが、実装上の特徴（再帰の有無、メモリの使い方、順序の安定性）に違いがあります。
正当性の直感と短い証明
Kahn 法の正当性（すべての辺 u → v について u は先に出力される）は、入次数 0 の頂点しか出力されないことに基づきます。入次数 0 の頂点には前提となる頂点がないため、どの順で出しても条件を破らない。辺の削除操作は、まだ出力されていない辺だけを減らすので、最終的にすべての辺が条件を満たすように処理されます。DFS 法では、もし u → v があり u が先に完成（終了時刻が先）していると v をまだ探索していないか、v の探索の後に u を完成させるため、逆順に並べれば u が v の前に来ることが保証されます。
計算量と空間量
- 時間計算量：O(V + E)。頂点と辺をそれぞれ一度ずつ主に扱うため。
- 空間計算量：隣接リスト表現なら O(V + E)。入次数配列や訪問フラグ、スタック/キューが追加で必要。
実装上の注意点・派生的な工夫
- メモリ：巨大なグラフでは隣接行列は無理（O(V^2)）。ほとんどの実装では隣接リストを使う。
- 再帰深さ：DFS 法は再帰を深く使うため、頂点数が多いとスタックオーバーフローに注意。言語や環境によっては明示的スタックで非再帰実装にする。
- 決定的順序：同じ DAG に複数のトポロジカル順序が存在する。安定した順序や辞書順最小を求めたい場合は、Kahn 法で入次数 0 の集合を優先度キュー（min-heap）で管理する。
- レイヤー分け（最短セメスター数や並列実行）：Kahn の処理を層ごとに行えば、必要最小の「ステップ数」や「セメスター数」（各ステップ内で並列に実行可能な頂点群）を計算できる。これは DAG におけるレベル分解に相当する。
- 動的グラフ：辺の追加・削除が頻繁にある場合、逐次的にトポロジカル順を更新するアルゴリズム（incremental topological sort）が研究されている。一般には実装が複雑。
応用例
- ビルドシステム（Make、Bazel など）：ソースファイルやモジュールの依存関係からコンパイル順序を決める。
- パッケージ管理（依存解決）：パッケージのインストール順序や削除順序の決定。
- 講義の履修計画：履修前提条件を満たす順に講義を並べる。
- タスクスケジューリング：依存タスクがあるワークフローの順序化（並列実行可能なグループの抽出にも使える）。
- コンパイラの最適化・リンカ：モジュールの依存関係に基づく処理順序。
- データフロー解析、パイプライン処理：データ依存に基づく処理順序の決定。
- DAG 上での最長経路問題（クリティカルパス）：トポロジカル順序を使えば、DAG における最長経路を DP で O(V+E) に解ける。
よくある間違い・落とし穴
- 有向グラフにサイクルがある場合でもアルゴリズムをそのまま回してしまい、結果を鵜呑みにする。Kahn 法では出力数が V に満たなければサイクルを検出可能、DFS 法では後退辺で検出できる。
- トポロジカル順序が一意であると誤解する。一般に順序は多数存在し得る（ただし DAG の比較的特殊な構造では一意になる場合もある）。
- 巨大グラフで再帰深さ超過：DFS 実装の再帰に依存していると実行環境によってクラッシュする。非再帰化やスタックサイズの調整が必要。
- 重複辺や自己ループの扱い：自己ループ（u→u）は即ちサイクルを導くためトポロジカル順序は存在しない。
理論的な話題：順序の数や困難性
ある DAG に対して成り立つトポロジカル順序の総数（その DAG の線形拡張の数）を数えることは一般に計算困難です。実際、部分順序の線形拡張の個数を数える問題は #P-完全であり、一般には効率的に求められません（小規模の DAG なら DP や分割統治で計算可能ですが、一般には難しい）。
まとめ（実務的アドバイス）
- トポロジカルソートは依存関係を解決する基本ツール。アルゴリズムは Kahn 法と DFS 法が主流で、どちらも O(V+E)。
- 実装は隣接リストを用いるのが現実的。入次数を配列で管理する Kahn 法は直感的でサイクル検出もしやすい。
- 並列実行や最短ステップ数を考える場合はレイヤー分解を行う。辞書順や安定性が必要な場合は優先度付きのデータ構造を導入する。
- トポロジカル順序そのものは一意でないことが多く、順序の総数を求めることは一般に難しい。
参考文献
- Topological sorting — Wikipedia
- Kahn's algorithm — Wikipedia（説明と擬似コード）
- Topological Sort — CP-Algorithms
- Topological Sorting — GeeksforGeeks（例と実装）
- Linear extension — Wikipedia（部分順序の線形拡張に関する説明）
投稿者プロフィール
