トポロジカルソート

どれから手をつければいいのか分からない

ビルドの手順、履修の順番、料理の段取り。どれも「これを終えてからでないと、あれに進めない」という条件の集まりです。条件が 2 つ 3 つならすぐ並べられますが、50 個になると人の頭では並べられません。

条件は「A が終わってから B」という向きのある矢印で書けます。矢印をすべて満たす一列の並びを作るのがトポロジカルソートです。

ここまでと違い、扱うのは 向きのあるつながり です。無向グラフのくせで両方向に辺を張ると「先」と「後」の区別が消えて、答えが出なくなります。一覧の [u, v] は u から v への一方通行として登録します。

待っている数を数える

考え方は現場の段取りと同じです。まず、それぞれの作業が「いくつの作業を待っているか」を数えます。待ち数が 0 の作業は、今すぐ始められます。

prereq = {
    "線形代数": [],
    "微積分": [],
    "機械学習": ["線形代数", "微積分"],
    "深層学習": ["機械学習"],
}

waiting = {}
ready = []
for name in prereq:
    waiting[name] = len(prereq[name])
    if waiting[name] == 0:
        ready.append(name)
print(ready)      # ['線形代数', '微積分']

待ち数 0 の作業を 1 つ終えたら、その作業を待っていた相手の待ち数を 1 ずつ減らします。減らした結果 0 になった相手は、そのとき初めて手が空きます。

done = "線形代数"
for name in prereq:
    if done in prereq[name]:
        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]] は複数あるので、取り出し方の決まりが効いてくる

演習では配列をソートして選ぶ

最小ヒープの操作を新しく書く代わりに、処理できる頂点を配列へ入れます。

available = [4, 1, 3]
available.sort()
first = available.pop(0)  # 1

辺を処理して入次数が 0 になった頂点は append で追加し、次の取り出し前にまたソートします。毎回のソートには時間がかかるため、大きな入力では最小ヒープが適しています。この演習では選ぶ順番と入次数の更新に集中します。

演習の隣接リストは、空のリストを for のたびに新しく作って append([]) で加えています。各頂点の隣の入れ物は独立しているので、一つに辺を追加しても他の頂点には増えません。

1. Kahn のアルゴリズム (入次数を使う BFS) で実装すること
2. 同点 (入次数 0 が複数) のときは ID が小さいノードを先に取り出すこと
3. 有向エッジは片方向のみ追加すること