Dlaczego złożoność BFS O (V + E) zamiast O (V * E)?

Question

Niektóre Pseudokod tutaj (lekceważyć mój styl)

Zaczynając od V1 (skolejkowany):

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

Ponieważ istnieją V wierzchołków w grafie, a te V wierzchołki są połączone krawędziami E i odwiedzając coraz połączone węzły (równoważne odwiedzeniu połączonych krawędzi) znajdują się w wewnętrznej pętli (zewnętrzna pętla jest samą rekursją), wydaje mi się, że złożoność powinna być O (V * E), a nie O (V + E). Czy ktoś może mi to wyjaśnić?

Answer 1

E to nie liczba krawędzi przylegających do każdego wierzchołka - faktycznie jest to całkowita liczba krawędzi na wykresie. Definiowanie go w ten sposób jest użyteczne, ponieważ niekoniecznie masz taką samą liczbę krawędzi na każdym pojedynczym wierzchołku.

Ponieważ każda krawędź zostanie odwiedzona raz do czasu zakończenia DFS, otrzymasz złożoność O (E) od tej części. Następnie dodajesz O (V) do odwiedzania każdego wierzchołka raz i otrzymujesz O (V + E) w sumie.