Question 3 Aju implemented a graph G = (V,E) using adjacency lists method.
Palo Alto Networks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Aju implemented a graph G = (V,E) using adjacency lists method. Now he wants to apply bfs to traverse this Graph. What is the time complexity of a breadth-first traversal of G?
Select any one of the following options
Show answer & explanation
Breadth-first search traverses each vertex once and inspects each edge incident to it once (in directed) or twice (in undirected), resulting in O(V + E) time.
Step-by-step Derivation:
Step 1: In BFS with adjacency list representation, each vertex is enqueued and dequeued exactly once, contributing O(V).
Step 2: When dequeuing vertex u, all adjacent edges (u, v) are scanned once, summing over all vertices to O(E).
Step 3: Total time complexity = O(V + E).