Answer

Correct Option: (i) $O(|V|+|E|)$

Explanation

Breadth-First Search (BFS) using adjacency list:

Complexity Analysis

1. Initialization: $O(|V|)$ — mark all vertices unvisited, enqueue source.
2. Each vertex is enqueued and dequeued exactly once → $O(|V|)$.
3. Each edge is examined twice (once from each endpoint in undirected graph, once in directed) when exploring adjacency list of its source vertex → $O(|E|)$.

Total:
$$T(V,E) = O(|V|) + O(|E|) = O(|V|+|E|)$$

Why other options are wrong

• (ii) $O(|V|)$: Ignores edge scanning. Correct only if graph is empty ($|E|=0$).
• (iii) $O(|E|)$: Ignores vertex initialization and isolated vertices.
• Adjacency matrix BFS would be $O(|V|^2)$, but with adjacency list (standard) it is $O(|V|+|E|)$.

Final Answer

BFS running time is $O(|V|+|E|)$ → Option (i).