トポロジカルソート
どれから手をつければいいのか分からない
ビルドの手順、履修の順番、料理の段取り。どれも「これを終えてからでないと、あれに進めない」という条件の集まりです。条件が 2 つ 3 つならすぐ並べられますが、50 個になると人の頭では並べられません。
条件は「A が終わってから B」という向きのある矢印で書けます。矢印をすべて満たす一列の並びを作るのがトポロジカルソートです。
ここまでと違い、扱うのは 向きのあるつながり です。無向グラフのくせで両方向に辺を張ると「先」と「後」の区別が消えて、答えが出なくなります。一覧の [u, v] は u から v への一方通行として登録します。
待っている数を数える
考え方は現場の段取りと同じです。まず、それぞれの作業が「いくつの作業を待っているか」を数えます。待ち数が 0 の作業は、今すぐ始められます。
Python
prereq = {
"線形代数": [],
"微積分": [],
"機械学習": ["線形代数", "微積分"],
"深層学習": ["機械学習"],
}
waiting = {name: len(reqs) for name, reqs in prereq.items()}
ready = [name for name, count in waiting.items() if count == 0]
print(ready) # ['線形代数', '微積分']待ち数 0 の作業を 1 つ終えたら、その作業を待っていた相手の待ち数を 1 ずつ減らします。減らした結果 0 になった相手は、そのとき初めて手が空きます。
Python
done = "線形代数"
for name, reqs in prereq.items():
if done in reqs:
waiting[name] -= 1 # 0 になったら着手できるこれを、手の空いた作業が無くなるまで繰り返します。取り出した順番が、そのまま答えの並びです。減らすのは 取り出したあと です。取り出す前に減らすと、まだ終わっていない作業の分まで解放してしまいます。
課題では、待ち数 0 の作業が同時に複数あるとき 番号の小さいほうを先に 取り出す決まりにしています。ふつうのキューは入れた順に出るので、小さい順に取り出せる入れ物 (Python なら heapq) を使うか、取り出すたびに最小を選びます。
一周して戻る条件は、並べられない
「A の前に B」「B の前に A」と書かれたら、どう並べても矛盾します。待ち数を減らす方式なら、この状況は自然に見つかります。まだ並べ終わっていないのに、待ち数 0 の作業が 1 つも残っていない状態になるからです。
ビルドツールが circular dependency と怒るのは、まさにこの瞬間です。並べ終えた個数が全体の個数に届いているかを見れば、順番を出すのと同時に循環も検出できます。
やってみよう
- 上の履修表を手で並べる。線形代数と微積分が先、そのあと機械学習、最後に深層学習
- 矢印が 1 本もないとき、答えは全部の点が番号順に並んだものになる
- 鎖状の
[[0,1],[1,2],[2,3]]は並び方が 1 通りしかない。[[0,1],[0,2],[1,3],[2,3]]は複数あるので、取り出し方の決まりが効いてくる
要件
- Kahn のアルゴリズム (入次数を使う BFS) で実装すること
- 同点 (入次数 0 が複数) のときは ID が小さいノードを先に取り出すこと
- 有向エッジは片方向のみ追加すること
入出力例
topoSort(4, [[0,1],[1,2],[2,3]]) → [0,1,2,3]
topoSort(3, []) → [0,1,2]
topoSort(4, [[0,1],[0,2],[1,3],[2,3]]) → [0,1,2,3]
topoSort(5, [[0,1],[0,2],[1,3],[2,3],[3,4]]) → [0,1,2,3,4]
topoSort(1, []) → [0]
topoSort(6, [[0,1],[0,2],[1,3],[2,3],[3,4],[3,5]]) → [0,1,2,3,4,5]ヒント
