Algorithms and Data Structures · Middle · Question 60 of 75
What is the complexity of BFS or DFS on a graph stored as adjacency lists?
- 1O(V × E)
- ✓Correct answer: O(V + E)
- 3O(V²) in every case
Explanation
Every vertex is processed once and every edge is looked at once (twice for undirected graphs). With an adjacency matrix the same traversal costs O(V²), because each row has V cells.