ここにいくつかの疑似コードがあります（私のスタイルは無視してください）
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) であると思われます。誰かこれを説明してくれませんか?
ベストアンサー1
E は各頂点に隣接する辺の数ではなく、実際にはグラフ内の辺の合計数です。すべての頂点に必ずしも同じ数の辺があるとは限らないため、このように定義すると便利です。
DFS が終了するまでに各エッジが 1 回訪問されるため、その部分から O(E) の複雑度が得られます。次に、各頂点を 1 回訪問するための O(V) を追加し、合計で O(V + E) になります。