18

ここにいくつかの疑似コードがあります（私のスタイルは無視してください）

v1 (エンキュー) から開始:

function BFS(queue Q)
  v2 = dequeue Q
  enqueue all unvisited connected nodes of v2 into Q
  BFS(Q)
end // maybe minor problems here

グラフには V 個の頂点があり、これらの V 個の頂点は E エッジに接続されており、接続されたノードを取得すること (接続されたエッジを訪問することと同等) は内側のループ (外側のループは再帰そのもの) にあるため、私にはそう思われます。複雑さは O(V+E) ではなく O(V*E) であるべきです。誰かが私のためにこれを説明できますか?

4

1 に答える 1

21

E は各頂点に隣接するエッジの数ではなく、実際にはグラフ内のエッジの総数です。すべての頂点に同じ数のエッジがあるとは限らないため、このように定義すると便利です。

各エッジは DFS が終了するまでに 1 回アクセスされるため、その部分から O(E) の複雑さが得られます。次に、各頂点を 1 回訪問するための O(V) を追加し、合計で O(V + E) を取得します。

于 2013-09-04T03:19:37.820 に答える