トポロジカルソート
01 / 一文での本質
有向非巡回グラフを線形化し、出力中ですべての辺が左から右へ向くようにする — 各ノードは、それを指すすべてのノードが既に出力された後で初めて順序に入る。
問題DAG のトポロジカル順序ノード数4辺数4
入次数を数える。入辺の無いノードが源 — 最初に処理できる。
ステップ
0 / 13
キュー
[—]
動作
初期化
結果
[—]
0 / 13
02 / パターンの骨格
# Kahn のアルゴリズム — 源点キューから入次数を抜いていくin_degree ← ノードごとに入辺を数えるqueue ← in_degree[node] == 0 のノード群result ← []while queue が空でない:u ← queue.pop_front()result.append(u)for v in adj[u]:in_degree[v] -= 1if in_degree[v] == 0: queue.append(v)if len(result) < n: # 閉路を検出return []return result
03 / このパターンを使うべき合図
「前提条件 / 依存」
履修計画、タスク順序、ビルドシステム、パッケージマネージャ、数式付きスプレッドシート。依存グラフがあるものはすべてトポロジカル順序を必要とする。
「そもそも何らかの順序で出来るのか?」
同じアルゴリズムが、そもそも妥当な順序が存在するかも判定する。 Kahn のキューが途中で空になれば、未処理のノードたちが閉路を成している — 答えはNo。 LC 207 はまさにこの問題。
「DAG」
問題文に明確に有向非巡回グラフが出てくる。「DAG」と書いてあれば、 トポロジカルソートが背骨 — DAG 上の最長経路、最短経路、経路数、すべてここからぶら下がっている。
「BFS でいけそうだが順序が大事」
素朴な BFS では隣接ノードを順不同に展開してしまうが、 問題が依存関係を尊重することを要求するなら、 実は依存 DAG 上で Kahn を回している。
04 / よくある落とし穴
i.
辺の向きを取り違える。
入力中の
(a, b) は「a は b の前提」(a → b)かもしれないし、 「a は b に依存」(b → a)かもしれない。問題文をよく読むこと — アルゴリズムはどちらでも正しいが、意図した順序に合うのは片方だけ。 LC 210 では [a, b] が「a を履修するには b を先に履修」を意味し、 典型的な辺の記法とは逆。ii.
「閉路が無い」と「妥当な順序が存在する」を混同する。
DAG ではこれらは同じ条件だが、コード上の失敗の現れ方が違う。 閉路は最後に
len(result) == n を確認して検出する。事前に探そうとしない。 Kahn は閉路入力を自然に拒否する。iii.
順序が一意だと思い込む。
ほとんどの DAG には多数の妥当なトポロジカル順序がある。 「辞書順最小の順序」(LC 269)を求めるなら、キューを最小ヒープに換えればよい — Kahn の残りはそのまま。
05 / LeetCode で練習
ファミリーから 4 問。最初の 2 問は教科書的な「閉路検出 / 順序出力」のペア。 3 問目はアルゴリズムを推論に持ち上げる(単語の順序からアルファベットを割り出す)。 4 問目は並列実行の余裕を導入する。