Kahn法（トポロジカルソート）徹底解説：原理・実装・応用と注意点

2025年12月11日 最終更新日時 : 2025年12月11日 エバープレイ編集部

概要：Kahn法とは何か

Kahn法（Kahn's algorithm）は、有向非巡回グラフ（DAG：Directed Acyclic Graph）に対してトポロジカルソート（頂点の部分順序を線形順序に拡張する操作）を行うための代表的なアルゴリズムの一つです。Arthur B. Kahnが1962年に提案した手法で、頂点の入次数（in-degree）が0の頂点を逐次取り出して出力し、その頂点に接続する辺を取り除く（実装上は近傍の入次数を減らす）という反復処理によって順序を決定します。実行時間は O(V + E)（Vは頂点数、Eは辺数）で、サイクルの検出も自然に行える点が特徴です。

アルゴリズムの直感と前提

トポロジカルソートの目的は「依存関係」を満たす線形順序を得ることです。DAGにおいては必ず少なくとも1つ以上の入次数0の頂点が存在します（そうでなければ全ての頂点に前提があり、無限に前に遡ることで循環が生じるため）。Kahn法はこの事実を利用し、入次数0の頂点を順に取り出して依存先の入次数を減らすことで、次の選択肢を作り出していきます。

基本的な手順（擬似手順）

  • 入力：有向グラフ G=(V,E)（隣接リストで表すことを想定）
  • 1. 各頂点 v の入次数 in_degree[v] を計算する。
  • 2. in_degree[v] == 0 の頂点を初期キュー（または集合）に入れる。
  • 3. 結果リスト L を空にする。
  • 4. キューが空でない間反復する：キューから頂点 u を取り出し、L に追加する。u から出ている各辺 (u, v) について in_degree[v] を1減らし、in_degree[v] が0になったらキューに追加する。
  • 5. すべての頂点を処理した後、L の長さが |V| でなければグラフにサイクルが存在する（トポロジカル順序は存在しない）。

計算量とメモリ

時間計算量は、各頂点を一度処理し、各辺を一度だけ見に行くため O(V + E) です。メモリは隣接リスト表現を用いた場合に O(V + E) が必要になります。in_degree を保持する配列（O(V)）と、ゼロ入次数の頂点を管理するキュー（最大で O(V)）が追加で必要です。

正当性の要点（なぜ正しいか）

正当性は次の観点から説明できます。

  • 存在性：DAGには必ず入次数0の頂点が少なくとも1つ存在する。仮に全頂点の入次数が1以上であれば、ある頂点から前駆頂点へと遡ることで有限回のうちに同じ頂点に戻るためサイクルが生じる（矛盾）。
  • 保存性：入次数0の頂点を出力してその辺を実質的に取り除く操作は、依存関係（先行関係）を壊さずに残りのグラフに対してトポロジカルソートを再帰的に適用できる。
  • サイクル検出：処理後に出力された頂点数が全頂点数に満たない場合、入次数0の頂点が尽きたことを意味し、残りの部分に全頂点の入次数が1以上である閉路（サイクル）が存在するためトポロジカル順序は存在しない。

DFSベースのトポロジカルソートとの比較

もう一つの代表的な方法は深さ優先探索（DFS）を用いる方法で、各頂点の探索完了順序（postorder）を逆順に並べることでトポロジカル順序を得ます。両者の主な違いは次の通りです。

  • 直感性: Kahnは入次数に基づく逐次削除でわかりやすく、DFSは再帰的な帰りがけ順を利用する。
  • サイクル検出: Kahnは最終的な出力量で明示的に検出でき、DFSは「前向き辺（back edge）」の検出でサイクルを検出する。
  • 力学: Kahnは入次数0の頂点群から任意に選ぶため非決定的（データ構造次第で順序が変わる）。DFSは再帰の訪問順に依存する。
  • 実装面: Kahnはキューやヒープを使うためイテレーティブで大規模データや外部メモリ向きに適応しやすい。DFSは深い再帰が問題になる場合がある（スタック破壊や再帰深さ制限）。

実装上の注意点と最適化

実運用でKahn法を用いる際のポイント：

  • データ構造：隣接リストと整数配列の in_degree が基本。高頻度ではヒープ（優先度付きキュー）を使えば辞書順（あるいは重み付きの最小順）で安定した順序を出力可能。
  • 安定性：入次数0の頂点を普通の FIFO キューで扱うと、挿入順序に応じて出力順が決まる。特定の順序（例：アルファベット順）を常に得たいなら min-heap を使う。
  • 並列化：入次数0の頂点群は独立に処理できるため、複数スレッド／分散環境で並列化しやすい。各スレッドが独立に出力し、最後にマージする設計や、分散カウントで同期する設計が考えられる。
  • 外部メモリ対応：巨大グラフでは隣接リスト全体をメモリに置けないことがある。ストリーミングで辺を順次読み込み入次数を計算し、複数パスで処理を行うなどの工夫が必要。
  • 動的グラフ：グラフが頻繁に変化する環境では、毎回全体を再計算するのはコストが高い。部分的に順序を更新する「動的トポロジカルソート」アルゴリズム（incremental topological ordering）を利用することがある。

実用的な応用例

Kahn法は多くのシステムで依存関係解決に用いられます。代表例：

  • ビルドシステム（Make、Bazel、Ninjaなど）：ソースやターゲットの依存関係に基づきビルド順序を決定する。
  • パッケージ管理：ライブラリの依存関係からインストール順序を生成。
  • ワークフロー／ジョブスケジューラ（Airflow、Luigiなど）：ジョブ間の依存関係を表現するDAGに対するスケジュール生成。
  • コンパイラ：最適化パスや変換の順序付け（依存する解析や最適化を先に実行する必要がある場合）。
  • データパイプライン：処理ステップ間の依存関係に沿った処理順序の決定。

よくある落とし穴

導入時に遭遇しやすい問題：

  • 非DAGを渡す：入力にサイクルが含まれていると完全な順序は存在しないため、アルゴリズムはサイクルを報告する必要がある。単に途中で処理が止まるだけだと原因究明が困難。
  • 順序の非決定性：同時に複数の入次数0頂点がある場合、選択の差で出力順が変わる。再現性を求める場合はソート済み集合や優先度付きキューを使う。
  • メモリ制約：大規模グラフでは隣接リストや in_degree 配列がメモリを圧迫するため、この点を踏まえた設計が必要。

拡張と応用的トピック

Kahn法をベースにしたさまざまな拡張や関連手法があります。

  • 優先度付きトポロジカルソート：入次数0の集合を優先度付きキューで管理することで、最小ラベル順などの特定の順序を保証する。
  • 並列トポロジカルソート：複数の入次数0ノードを同時に処理することで高速化。依存先の in_degree 更新は原子操作やロックで同期する必要がある。
  • 部分順序の列挙：Kahn法をバックトラッキングで拡張すると、全てのトポロジカル順序（線形拡張）を列挙できる。ただし順序数は爆発的に増える可能性がある。
  • 動的アルゴリズム：エッジの追加・削除に対してトポロジカル順序を部分的に更新するアルゴリズム（例：Pearce-Kellyなどの研究）も存在する。

実装例（概念のみ）

実装は以下の要素を順に用意すればよい：

  • 隣接リスト adjacency[v]（各頂点から出る辺のリスト）
  • 入次数配列 in_degree[v]（初期化はすべての辺を1回走査して計算）
  • キュー（FIFO）または優先度付きキュー（安定順が必要な場合）
  • 出力リスト result[] に頂点を順に追加

処理後、result の長さが |V| であれば成功、足りない場合はサイクルあり。

まとめ

Kahn法はトポロジカルソートをシンプルかつ効率的に実現する基本アルゴリズムで、依存関係解決における現実的な問題に広く使われています。入次数の管理とゼロ入次数頂点の選択という直感的な操作により、O(V + E) の時間で処理できる点、サイクル検出が自然に行える点、並列化や優先度制御などの応用が容易な点が強みです。一方で、順序の非決定性や大規模データでのメモリ制約、動的グラフへの対応といった実用上の配慮も必要です。これらを踏まえ適切なデータ構造や実行環境を選ぶことで、Kahn法はビルドシステムやワークフロー管理、パッケージ解決など多様な場面で有効に機能します。

参考文献

カテゴリー
IT
前の記事
ティム・バートンの世界：ゴシックとファンタジーが生む映像表現の解剖
2025年12月11日
次の記事
Tucker分解とは｜理論・アルゴリズム・実装・応用までの完全ガイド
2025年12月11日