0

問題: 無向グラフG = (V, E)(V = 頂点、E = エッジ) があり、各頂点を訪れ、各エッジを両方向に通過する必要があります。

グラフについて私が知っている唯一のアルゴリズムは、DFS、BFS、およびいくつかの MST (Kruskal など) です。私の友人と私はこの問題について話し合っていました。指示があれば、単純に DFS を実行し、次に DFS を転置しますが、グラフは残念ながら無向。私の友人は、MST を実行し、MST を DFS してから、MST にないエッジを繰り返し処理して残りのエッジを見つけることを提案しました。彼の言いたいことはなんとなくわかりますが、これが良いアプローチかどうかはわかりません。意見？また、無向の場合、両方向のエッジをどのように通過できますか?

4

1 に答える 1

1

グラフが有向か無向かは関係ありません。すべての無向エッジを 2 つの有向エッジに置き換えて、有向グラフに対して使用しているアルゴリズムを実行するだけです。DFS と BFS の両方が、頂点とエッジ全体をトラバースします。

あなたが探しているのはGraph Traversalと呼ばれるものだと思います。BFS と DFS は 2 つのグラフ トラバーサル アルゴリズムであり、グラフを方向付ける必要はありません。一方、MST はグラフ トラバーサル アルゴリズムではありません。

于 2013-04-03T04:16:44.013 に答える