41

BFS と DFS の実行時間が O(V+E) である理由は、特に次のサイトのこの例のように、頂点から到達できるノードに有向エッジを持つノードがある場合です。

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

4

5 に答える 5

47

E は、G={V,E} として、グラフ内のすべてのエッジのセットです。だから、|E| グラフ内のすべてのエッジの数です。

これだけで、全体の複雑さが |V| にならないことを納得させるのに十分なはずです。各頂点のグラフ内のすべてのエッジを反復していないため、|E| 回です。

隣接リスト表現では、頂点 v ごとに、それに隣接するノードのみをトラバースします。

|V| |V|+|E| の係数 実行されたキュー操作の数から来ているようです。

アルゴリズムの複雑さは、使用されるデータ構造に依存することに注意してください。事実上、グラフの表現に存在する各情報にアクセスしています。これが、グラフの行列表現の複雑さが V の 2 乗になる理由です。

コーメンからの引用、

「エンキューとデキューの操作には O(1) 時間がかかるため、キュー操作に費やされる合計時間は O( V) です。各頂点の隣接リストは、頂点がデキューされたときにのみスキャンされるため、各隣接リストは次の時点でスキャンされます。すべての隣接リストの長さの合計は Θ(E) であるため、隣接リストのスキャンに費やされる合計時間は O( E) です。初期化のオーバーヘッドは O( V) であり、したがって合計実行時間はBFS は O( V + E) です。」

于 2012-03-04T10:23:23.140 に答える
24

この問題は私の時間の 4 時間のように消費されましたが、最終的には、全体像をつかむ簡単な方法があると思います。

Cormen で見つけたアルゴリズムを要約すると、http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htmでも同じです。次のようなものがあります。

for (vi in V)
{
   Some O(1) instructions
   for ( e in Adj(vi) ) {
      Some O(1) instructions
   }
}

問題は、ここで実行される命令の数です。これが Sigma-Sum (Adj(vi)) になり、この値の上限は 2|E| になります。

最初は自動的に内側ループと外側ループの反復回数を乗算することを考えますが、この場合、内側ループの反復回数の合計は外側反復子の関数であるため、乗算はできません。

于 2012-06-16T10:51:35.620 に答える
11

すべてのエッジに最大 2 回アクセスします。E エッジがあります。したがって、2*E のエッジ アクセス操作が行われます。さらに、エッジを持たない、つまり次数が 0 のノードを追加します。そのようなノードは最大で V 個存在できます。したがって、複雑さは次のようになります。 O(2*E + V) = O(E + V)

于 2015-08-02T15:06:38.227 に答える
1

|V| を反復処理します。ノード、最大 |V| 回。|E| の上限があるので、グラフ内のエッジの合計で、最大で |E| をチェックします。エッジ。異なる頂点にはさまざまな数の隣接ノードがあるため、|V|*|E| を単純に掛けることはできません。(これは、頂点ごとに |E| 個のエッジをトラバースすることを意味しますが、これは正しくありません。|E| はすべてのノードのエッジの総数です)、むしろ、V 個のノードをチェックし、合計 E 個をチェックします。エッジ。最後に、O(|V|+|E|) があります。

DFS の場合も同様で、すべての頂点隣接リストをループし、アクセスされていない場合は DFS(v) を呼び出します。つまり、|V| が発生します。時間ステップ、および隣接するノードを訪問するために発生した時間 (基本的に、これらはエッジを形成し、合計 |E| 個のエッジがあるため、O(V+E) 時間になります。

    private static void visitUsingDFS(Node startNode) {
        if(startNode.visited){
            return;
        }
        startNode.visited = true;
        System.out.println("Visited "+startNode.data);
        for(Node node: startNode.AdjacentNodes){
            if(!node.visited){
                visitUsingDFS(node);
            }
        }
    }
于 2014-11-09T04:17:06.917 に答える