What is time complexity of BFS depending on the representation of the graph?
I was wondering what is the time complexity of BFS, if I use:
- an adjacency matrix
- adjacency list
- edge list
Is it same as their space complexity?
Answer
The complexity of BFS implemented using an Adjacency Matrix will be O(|V|²). And that when implemented by an Adjacency List is O(|V| + |E|).
Why is it more in the case of Adjacency Matrix?
This is mainly because every time we want to find what are the edges adjacent to a given vertex 'U', we would have to traverse the whole array AdjacencyMatrix[U], which is ofcourse of length |V|.
Imagine the BFS progressing as frontiers. You take a starting vertex S, which is at level 0. All the vertices adjacent to S will be at level 1. Then, we mark all the adjacent vertices of all vertices at level 1, which don't have a level, to level 2. So, every vertex will belong to only one frontier. Each of these frontiers correspond to different levels. And when an element is in a frontier, we check once for its adjacent vertices, which takes O(|V|) time. As, the frontier covers |V| elements over the course of the algorithm, the total time would become O(|V| * |V|) which is O(|V|²).
The complexity difference in BFS when implemented by Adjacency Lists and Matrix occurs due to the fact that in Adjacency Matrix, to determine which nodes are adjacent to a given vertex, we take O(|V|) time, irrespective of the number of edges. Whereas, in Adjacency List, the edges that are immediately available to us, thus it takes time proportional to the number of adjacent vertices, which on summation over all vertices |V| is |E|. So, BFS by Adjacency List gives O(|V| + |E|).