What is the running time of BFS if we represent its input graph by an

adjacency matrix and modify the algorithm to handle this form of input?

I feel if the graph is represented by adjacency matrix, then the time of iterating all the edge becomes O(V^2), so the running time is O(V+V^2).

But I read online that each vertex can be explored once and its adjacent vertices must be determined too. This takes Theta(V^2) time. And now I am confused.

How can we bound the lower limit as well?

=================

If you do it naively then it is O(v3)\mathcal O(v^3) time for the complete graph.

– Jorge Fernández Hidalgo

2 days ago

@JorgeFernándezHidalgo sorry I did not get you. how come?

– Harshit

2 days ago

Nevermind, I got confused , you have O(v2)\mathcal O (v^2) complexity

– Jorge Fernández Hidalgo

2 days ago

=================

=================