Using BFS or DFS on a graph stored as adjacency lists, what is the tight…
2025
Using BFS or DFS on a graph stored as adjacency lists, what is the tight worst-case time complexity, expressed in terms of V vertices and E edges, for searching for a vertex?
Answer: A. O(V + E) — ConceptIn an adjacency-list graph, breadth-first search (BFS) and depth-first search (DFS) visit each reachable vertex at most once. Across the whole…
- A.
O(V + E)
- B.
O(log V)
- C.
O(V2)
- D.
O(E log V)
Attempted by 348 students.
Show answer & explanation
Correct answer: A
Concept
In an adjacency-list graph, breadth-first search (BFS) and depth-first search (DFS) visit each reachable vertex at most once.
Across the whole traversal, the algorithm examines each adjacency-list entry at most once, so graph-search time grows with both the number of vertices V and the number of edges E.
Application
Initialize the visited structure and the traversal frontier for the source vertex; the vertex bookkeeping is bounded by O(V).
In the worst case, the target is absent or is reached last, so all V reachable vertices are processed once.
Iterating through all adjacency lists examines every directed edge once; in an undirected graph each edge appears twice, which changes only a constant factor. This work is O(E).
Adding the vertex work and edge work gives O(V) + O(E) = O(V + E).
Cross-check
With an adjacency matrix, examining every possible neighbour of every processed vertex can take quadratic time in V, which is why the representation must be stated explicitly.
For adjacency lists, a complete worst-case search may need to inspect the whole stored graph, whose size is proportional to V + E. Therefore, the result is O(V + E).