トポロジカルソート
「A の後に B」という依存関係を全部守る 順番を、矢印グラフから導きます。
0
前提が残っている（入次数 > 0）
取り出せる（入次数 0）
今回取り出す
確定済み
確定した実行順
作業や科目には「これを終えてからでないと次に進めない」という依存関係があります。
これを矢印（有向辺）で表したグラフ（DAG：閉路のない有向グラフ）から、
全ての依存を満たす実行順を求めるのが トポロジカルソートです。
手順（カーンのアルゴリズム）：各ノードの 入次数（自分に入ってくる矢印の数）を数え、 入次数 0＝前提がもう無いノードを 1 つ取り出す。取り出したら、その先のノードの入次数を 1 減らす。 これを繰り返すと、依存を破らない順番が並びます。
手順（カーンのアルゴリズム）：各ノードの 入次数（自分に入ってくる矢印の数）を数え、 入次数 0＝前提がもう無いノードを 1 つ取り出す。取り出したら、その先のノードの入次数を 1 減らす。 これを繰り返すと、依存を破らない順番が並びます。
いま何をしている？
ここがポイント
- 入次数 0 ＝「前提となる作業がもう残っていない」→ 今すぐ着手できる。
- 取り出すたびに、その先の入次数を減らす → 新たに着手可能なノードが現れる。
- 入次数 0 が複数あるときの順番は自由 ── トポロジカル順序は 1 通りとは限らない。
- もし閉路があると入次数 0 が尽きて全部は並べられない（依存が循環＝実行不能）。