Time Complexity of breadth first search with adjacency matrix representation?

Question

In bfs we have to look up each node and for each node we have to look all elements of row.Doesn't this require O(V^2)(number of elements in adjacency matrix) time and hence for adjacency matrix shouldn't total time be O(V^2+E).

Answer 1

The complexity of BFS implemented using an Adjacency Matrix will be O(|V|²). 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 off course of length |V|.

Imagine the BFS progressing as frontiers. You take a starting vertex S, which is at level - 0. All the adjacent vertices are 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 one frontier (or level) only. 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 this fact that in Adjacency Matrix, to tell which nodes are adjacent to a given vertex, we take O(|V|) time, irrespective of edges. Whereas, in Adjacency List, it is immediately available to us, takes time proportional to adjacent vertices itself, which on summation over all vertices |V| is |E|. So, BFS by Adjacency List gives O(|V| + |E|).

I hope my answer has helped you, if it did, let me know...! ☺