Perché la complessità di BFS O (V + E) invece di O (V * E)?

Question

Alcuni pseudocode qui (ignorare il mio stile)

A partire da v1 (accodato):

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

Poiché ci sono V vertici nel grafico, e questi vertici V sono collegati ai bordi E, e visitare sempre i nodi connessi (equivalenti ai bordi connessi alla visita) si trovano nel ciclo interno (il ciclo esterno è la ricorsione stessa), mi sembra che la complessità debba essere O (V * E) piuttosto che O (V + E). Qualcuno può spiegarlo per me?

Answer 1

E non è il numero di lati adiacenti a ciascun vertice - in realtà è il numero totale di bordi nel grafico. Definirlo in questo modo è utile perché non si ha necessariamente lo stesso numero di spigoli su ogni singolo vertice.

Poiché ogni spigolo viene visitato una volta che termina il DFS, si ottiene la complessità O (E) da quella parte. Quindi aggiungi la O (V) per visitare ogni vertice una volta e ottieni O (V + E) sul totale.