1

この特定の質問に対する答えはO（V + E）であり、木のようなグラフの場合、各頂点が1回だけ探索されるため、それは理にかなっています。

ただし、グラフにサイクルがあるとしましょう。

たとえば、4つの頂点ABCDを持つ無向グラフを取り上げましょう。
AはBとCの両方に接続され、BとCの両方がDに接続されています。したがって、合計で4つのエッジがあります。A-> B、A-> C、B-> D、C-> D、およびその逆。

DFS（A）をやってみましょう。

最初にBを探索し、Bの隣接DとDの隣接Cを探索します。その後、Cにはエッジがないため、DとB、次にAに戻ります。

次に、Aは2番目のエッジをトラバースし、Cを探索しようとします。すでに探索されているため、Aは何も実行せず、DFSは終了します。

しかし、ここでは、頂点「C」が1回ではなく、2回トラバースされています。明らかに最悪の場合の時間計算量はVに正比例する可能性があります。

何か案は？

4

2 に答える 2

3

すでにアクセスしたノードへの再アクセスを回避するために使用するvisitedセットを維持しない場合、DFSはそうではありません。実際、これは完全なアルゴリズムではありません。したがって、パスが存在する場合でも、パスが無限ループでスタックするため、パスが見つからない可能性があります。O(V+E)

s無限グラフの場合、訪問先セットを維持していても、からへのパスを探している場合はt、無限ブランチでスタックする可能性があるため、完了が保証されないことに注意してください。

完全でありながら、効率的なスペース消費というDFSの利点を維持することに関心がある場合は、反復深化DFSを使用できますが、特定のグラフへのパスではなく、グラフ全体を検出しようとしている場合は、問題を簡単に解決することはできません。ノード。

編集：セットされたDFS擬似コードvisited。

DFS(v,visited):
  for each u such that (v,u) is an edge:
       if (u is not in visited):
            visited.add(u)
            DFS(u,visited)

頂点がまだ訪問されていない場合にのみ、頂点で再帰を呼び出すことは簡単にわかります。したがって、答えは頂点とエッジの数で実際に線形です。

于 2012-08-03T20:15:48.847 に答える
0

グラフの各頂点とエッジに一定の回数アクセスしても、O（V + E）のままです。別の見方をすると、コストは頂点ではなくエッジに請求されます。

于 2012-08-03T20:16:00.303 に答える