有向非循環グラフ（DAG）のトポロジカルソート

トポロジカルソート

トポロジカルソートは、有向非循環グラフ（DAG）の頂点の線形順序を生成し、すべての辺(u, v)においてuがvの前に来るようにします。DAGでのみ定義されます。

Kahnのアルゴリズム（BFSベース）

1. すべてのノードの入次数を計算
2. 入次数0のすべてのノードをキューに追加
3. キューが空でない間：
   • ノードuをデキューし、結果に追加
   • uの各隣接ノードvの入次数を減らす
   • vの入次数が0になったらキューに追加
4. 結果にすべてのノードが含まれれば有効、そうでなければサイクルが存在

DFSベースのアルゴリズム

1. DFSを実行し、各ノードの終了時刻を記録
2. ノードを終了時刻の逆順にソート
3. これが有効なトポロジカル順序

複数の有効な順序

DAGは多くの有効なトポロジカル順序を持つ場合があります。

時間計算量

両方のアルゴリズムとも**O(V + E)**で実行されます。