1

有向グラフですべてのサイクルを見つけたい。深さ優先探索を開始すると、1つのノードからいくつかのサイクルが検出されます（バックエッジの検出）。したがって、グラフ内のすべてのノードにdfsを適用しました（つまり、ルートが異なるノードになるたびに）。これを使用して（重複するものを排除することにより）すべてのサイクルを取得できます。しかし、これがすべてのグラフで機能するかどうか、そしてこれが正しいアプローチであるかどうかはわかりません。これがすべての状況で機能するかどうかを誰かが私に提案できますか？

ありがとう

4

2 に答える 2

0

ノードを切断している場合（グラフが接続されていない場合）、各ノードからグラフをトラバースする必要があります。特定のノードを見つけたときにトラバーサルを停止しないため、DFSとBFSのどちらを使用するかは問題ではありません。

サイクルを回避するために、通常の「パスごと」の祖先リストの代わりに、すでにアクセスしたノードから完全なトラバーサルを実行する必要がないように、グローバルなVisitedNodesリストを保持します。

于 2010-06-25T07:08:42.883 に答える