Multiple choice

An undirected graph G with 'n' vertices and 'e' edges is represented by adjacency list. What is the time required to generate all the connected components?

  1. O(n)

  2. O(e)

  3. O(e + n)

  4. O(e2)
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

To find all connected components, one must visit every vertex and every edge once using a graph traversal like BFS or DFS. The complexity is proportional to the sum of vertices and edges, O(n + e).

Keep practicing — related questions