Why is the complexity of BFS O(V+E) instead of O(V*E)?

Question

CLRS pseudocode:

begin
   for each vertex u in G.V - {s}, do
      u.color := white
      u.d := infinity
      u.p := NIL
   done
   s.color := green
   s.d := 0
   s.p := NIL
   Q := NULL
   insert s into Q
   while Q is not null, do
      u = delete from Q
      for each v in adjacent to u, do
         if v.color = white
            v.color := green
            v.d := u.d + 1
            v.p := u
            insert v into Q
         end if
      done
      u.color = dark_green
   done
end`

In the clrs it says that the insertion and deletion operations with the queue require an O (1) time, so the total time of operations with the queue is O (V). (V because each vertex is visited at least once). instead the time to inspect the adjacency list of each node is O (E). Then we have another O (V) for initialization. So the total time is O (V + E) which in the worst case becomes O (V ^ 2), this depends on whether the graph is dense or not.

Now my question is: Since we have two cycles nested the complexity shouldn't be O (V * E), I can't understand why a sum operation is performed instead of multiplying.

Answer 1

I will suppose here that the graph is undirected, but the same reasonning can be done with a digraph.

Using an implemention of a graph as an array of adjacency lists, the adjacency list of any vertex $v$ is its number of neighbors, $\deg(v)$.

The BFS inspects each adjacency list at most once during the graph traversal (and exactly once if the graph is connected). That means that the total complexity is: $$\mathcal{O}\left(\sum\limits_{v\in V}(\deg(v) + 1)\right)$$ Here, the $+1$ is necessary, as inspecting an adjacency list costs $\mathcal{O}(1)$ time, even if the list is empty. Now, a very useful formula for complexity on graphs is: $$\sum\limits_{v\in V}\deg(v) = 2|E|$$ It can be proven quite easily when noting that each edge increases the sum of degrees by two (one for each extremity).

Finaly, we conclude that the complexity is: $$\mathcal{O}\left(\sum\limits_{v\in V}(\deg(v) + 1)\right) = \mathcal{O}(2|E| + |V|) = \mathcal{O}(|E| + |V|)$$