6

無向グラフの場合、循環を見つける必要がある場合は、この古い質問で説明されているように深さ優先検索を使用します。これはよく知られた方法であり、最適です。

しかし、有向グラフの場合、この他の質問はトポロジカルソートの使用を提案しています。

私の質問は、有向グラフのサイクルをチェックするために、無向グラフに使用するのと同じ手法を使用できないのはなぜですか? 私はさまざまなケースを考えてきましたが、アルゴリズムは常に一致しているようです。

DFSがサイクルを見つけることができず、トポロジーソートが見つけることができる有向グラフの例を誰か思いつくことができますか?

4

1 に答える 1

9

あなたの質問は次のようです:無向グラフのサイクルを検出するために深さ優先検索を使用できますか、または代わりにトポロジカルソートを使用する必要がありますか?

答えは、両方のアプローチが機能するということです。有向グラフにサイクルがある場合は、グラフに対して深さ優先検索を実行することでこれを検出できます。サイクル内のノードから検索を開始するとすぐに、最終的にサイクルを発見することが保証されます。

トポロジカル ソートと DFS は、次のように密接に関連していることがわかります。グラフで DFS を実行し、サイクルが見つからない場合、各ノードを完全に探索済みとしてマークした逆の順序でトポロジカル ソートが得られます。グラフの一種。つまり、「トポロジカル ソートを使用する」ソリューションと「DFS を使用する」ソリューションは、トポロジカル ソートを実装する 1 つの方法が DFS であるため、非常に類似したアルゴリズムと考えることができます。

お役に立てれば！

于 2013-05-27T19:57:03.547 に答える