Motivation

トポロジカル順序は、グラフに閉路（サイクル）がない場合にのみ存在します。入次数が0の頂点を繰り返し削除するKahnのアルゴリズムを使用して、これを構築します。

なぜトポロジカルソートを学ぶのか？

• 制約のある順序付け: ビルドシステム、タスクスケジューリング、履修科目の前提条件、スプレッドシートの再計算などはすべてこれに依存しています。
• 閉路検出: すべての頂点を順序付けできない場合、そのグラフには閉路が含まれている必要があります。
• DAGアルゴリズムの基礎: DAG（有向非巡回グラフ）における最短経路や最長経路は、トポロジカル順序で計算されます。

有効な順序は複数存在する可能性があります。予測可能な1つの結果を得るために、常に入次数が0である頂点のうち、最も番号の小さいものを削除します。