操作して学ぶ
トポロジカルソート可視化
パッケージマネージャの依存解決、ビルドパイプラインの実行順序、大学の履修計画…… 「これを先にやらないと次に進めない」という制約を満たす順番を求めるのがトポロジカルソートです。Kahn法（BFS・入次数）とDFS法（帰りがけ順）、 2つの定番アルゴリズムをステップ実行で比べてください。
2つのアルゴリズムの考え方
- Kahn法：各ノードの「入次数（自分より先にやるべきことの数）」を数え、入次数0のノードから順にキューへ。処理し終えたら、そのノードに依存していたノードの入次数を1減らす——0になったら新たにキューへ。全ノードを処理できなければ循環依存がある。
- DFS法：深さ優先で辿り、探索が完全に終わった（これ以上依存先がない）ノードから順にスタックへ積む。最後にスタックを反転させたものが答え。探索中（訪問中）のノードに戻ってきたら、それは循環依存の証拠。
- 順序は一意とは限らない：同じグラフでもKahn法とDFS法で異なる有効な順序が出ることがある——それでもどちらも「制約を満たす」という意味では正しい。