トポロジカルソートを使用する

トポロジカルソート (topological sort) は、有向非巡回グラフ（DAG）の頂点を「すべての有向辺 \(u \to v\) について \(u\) が \(v\) より前に来る」ように並べる手続きである。数値の大小で配列を並べ替える通常のソートとは対象が違い、辺が表す前後関係（依存・前提・制約）を壊さない線形順序を求める。

ビルドシステムやパッケージマネージャの依存解決、講義の履修順序、タスクのスケジューリングなど、「A のあとに B」という制約が集まった場面で使う。閉路があるとそのような順序は存在しないため、入力は DAG であることが前提になる（実装では処理しきれない頂点が残れば閉路ありと判定できる）。

本稿では Kahn のアルゴリズム（入次数 0 の頂点を順に確定していく幅優先寄りの手順）を説明する。深さ優先探索の帰りがけ順を逆に並べる方法でも同じ結果が得られる。

  1. 入次数の計算: 各頂点 \(v\) について、\(v\) へ向かう辺の本数（入次数）を数える。
  2. 準備完了集合: 入次数 0 の頂点をキュー（またはリスト）へ入れる。これらはいま確定してよい頂点である。
  3. 取り出し: キューから頂点 \(u\) を 1 つ取り、結果列の末尾へ追加する。
  4. 辺の削除: \(u\) から出る各辺 \(u \to v\) について \(v\) の入次数を 1 減らし、0 になった \(v\) をキューへ追加する。
  5. 繰り返し: キューが空になるまで手順 3〜4 を繰り返す。すべての頂点が結果に入ればトポロジカル順序が完成する。
procedure topological_sort_kahn(V, E)
  for each v in V
    indegree[v] = 0
  for each edge (u → v) in E
    indegree[v] = indegree[v] + 1
  Q = empty queue
  for each v in V
    if indegree[v] = 0 then
      enqueue(Q, v)
  order = empty list
  while Q is not empty
    u = dequeue(Q)
    append u to order
    for each edge (u → v) in E
      indegree[v] = indegree[v] - 1
      if indegree[v] = 0 then
        enqueue(Q, v)
  if length(order) < length(V) then
    report cycle
  return order

各頂点と各辺を定数回しか触らないため、時間は \(O(V + E)\)、入次数表とキューに \(O(V)\) の追加領域を使う。同じ入次数 0 の頂点が複数あるときの取り出し順で結果は変わりうるが、いずれも正当なトポロジカル順序である。依存関係に従う整列であり、同順位の相対順を保つ安定ソートではない。

次の DAG では辺 \(u \to v\) が「\(u\) を \(v\) より前に置く」制約を表す。たとえば 1 → 3 と 2 → 3 があるので、3 は 1 と 2 の両方より後ろになる。

flowchart LR
  n1["1"] --> n3["3"]
  n1 --> n4["4"]
  n2["2"] --> n3
  n2 --> n5["5"]
  n3 --> n6["6"]
  n4 --> n6
  n5 --> n7["7"]
  n6 --> n8["8"]
  n7 --> n8

下のデモは同じ手順を依存グラフで追う。矢印 \(u \to v\) は「\(u\) を \(v\) より先に置く」、各頂点の下の数字はいまの入次数である。

黄色が入次数 0（いま取れる）、緑が処理中、紫が確定済み、オレンジはいま入次数を減らしている辺と先の頂点。下段の丸は確定順（トポロジカル順序）が左から埋まっていく様子を示す。シャッフルで別の DAG を作り直す。

類似アルゴリズムとの相違点

選択ソートは未整列範囲から最小キーを選んで確定位置へ運ぶ。Kahn 法も「いま選んでよい要素」を 1 つずつ確定位置へ運ぶ点は似ているが、選び方の基準がキーの大小ではなく入次数（依存の解消）である。

通常の比較ソート（マージソートやヒープソートなど）は全順序なキー比較を前提にする。トポロジカルソートは辺が与える半順序だけを守り、比較不能な頂点どうしの前後はキューの取り出し順などに委ねる。

深さ優先探索で各頂点の「帰りがけ時刻」を記録し、時刻の降順に並べる方法も同じ DAG に対するトポロジカル順序を返す。Kahn 法は入次数とキューで幅優先に進め、閉路検出も「残頂点の有無」で分かりやすい。