アルゴリズム・データ構造図鑑 · 基礎から応用へ

トポロジカルソート:依存を満たす実行順を作る

入次数0の頂点を取り出すKahn法を追い、有向非巡回グラフの条件と閉路検出を学ぶ。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 辺の向きを先に定義する
  2. 入次数0から取り出す
  3. 閉路は残った頂点で分かる
  4. 計算量と一意性を分ける
  5. この記事をロゲイアに質問する理解を確かめる

辺の向きを先に定義する

トポロジカル順序は、有向辺u→vがあるときuをvより前へ置く頂点の並びです。依存関係を表すなら、前提となる作業から後続作業へ辺を張ります。「vがuへ依存する」という言葉だけで向きを逆にすると、出力の解釈も逆になります。この順序が存在するのは有向非巡回グラフ、DAGの場合です。最短路や重みの小さい順序を求めているわけではありません。辺のない頂点も作業として含め、頂点集合全体を扱う必要があります。

入次数0から取り出す

辺A→C、B→C、C→Dなら、最初に入次数0なのはAとBです。Aを取り出してCの入次数を2から1へ減らし、Bを取り出すと0になるのでCを待ち行列へ入れます。Cを取り出してDを0にし、[A,B,C,D]を得ます。AとBの取り出し順を逆にした[B,A,C,D]も正解です。取り出した頂点から出る辺だけを削除したと考え、残るグラフで前提のない頂点を次の候補にするのがKahn法の意味です。

閉路は残った頂点で分かる

全頂点数をVとして、取り出せた頂点がV個未満のまま待ち行列が空になれば、未処理部分に有向閉路があります。例えばC→DにD→Cを加えると、AとBを処理してもCとDは互いに入次数を持ち続けます。ただし残った頂点がすべて閉路上とは限らず、閉路の下流で待たされている頂点も含みます。閉路そのものの列を示したいなら別途探索が必要です。自己ループや多重辺も入次数の計算と減算で一貫して数えます。

計算量と一意性を分ける

隣接リストと通常の待ち行列を使えば、各頂点と各辺を一度ずつ扱うので時間O(V+E)、補助領域O(V)です。隣接リスト自体の保持にはO(V+E)を要します。候補の頂点を辞書順最小で選びたいなら優先度付きキューを使えますが、時間評価は変わります。複数の候補が同時にあることは、正しい順序が一意でない手掛かりです。順序の一意性、辺の整合性、実際の並列実行時に必要な資源制約は、それぞれ別の問題として考えます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 11

学習コースから次を選ぶ