Kosaraju のアルゴリズムでは、逆グラフから終了時刻が生成されます。次に、DFS を実行することにより、元のグラフから、以前に生成された最大の終了時刻から最小の終了時刻まで、強連結成分が検出されます。
Kosaraju のアルゴリズムの終了時間は、元のグラフから生成できますか? では、最低終了時間から最高終了時間まで DFS を実行すると、強連結成分を発見できるでしょうか?
私にはそのように思えますが、それは私の直感です。
Kosaraju のアルゴリズムでは、逆グラフから終了時刻が生成されます。次に、DFS を実行することにより、元のグラフから、以前に生成された最大の終了時刻から最小の終了時刻まで、強連結成分が検出されます。
Kosaraju のアルゴリズムの終了時間は、元のグラフから生成できますか? では、最低終了時間から最高終了時間まで DFS を実行すると、強連結成分を発見できるでしょうか?
私にはそのように思えますが、それは私の直感です。