Time Complexity Analysis of BFS

Question

I know that there are a ton of questions out there about the time complexity of BFS which is : O(V+E)

However I still struggle to understand why is the time complexity O(V+E) and not O(V*E)

I know that O(V+E) stands for O(max[V,E]) and my only guess is that it has something to do with the density of the graph and not with the algorithm itself unlike say Merge Sort where it's time complexity is always O(n*logn).

Examples I've thought of are :

1. A Directed Graph with |E| = |V|-1 and yeah the time complexity will be O(V)
2. A Directed Graph with |E| = |V|*|V-1| and the complexity would in fact be O(|E|) = O(|V|*|V|) as each vertex has an outgoing edge to every other vertex besides itself

Am I in the right direction? Any insight would be really helpful.

Answer 1

Your "examples of thought" illustrate that the complexity is not O(V*E), but O(E). True, E can be a large number in comparison with V, but it doesn't matter when you say the complexity is O(E).

When the graph is connected, then you can always say it is O(E). The reason to include V in the time complexity, is to cover for the graphs that have many more vertices than edges (and thus are disconnected): the BFS algorithm will not only have to visit all edges, but also all vertices, including those that have no edges, just to detect that they don't have edges. And so we must say O(V+E).

Answer 2

The complexity comes off easily if you walk through the algorithm. Let Q be the FIFO queue where initially it contains the source node. BFS basically does the following

while Q not empty
  pop u from Q
  for each adjacency v of u
     if v is not marked
         mark v
         push v into Q

Since each node is added once and removed once then the while loop is done O(V) times. Also each time we pop u we perform |adj[u]| operations where |adj[u]| is the number of adjacencies of u.

Therefore the total complexity is Sum (1+|adj[u]|) over all V which is O(V+E) since the sum of adjacencies is O(E) (2E for undirected graph and E for a directed one)