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?