The most efficient algorithm for finding the number of connected components in…
2008
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
- A.
θ(n)
- B.
θ(m)
- C.
θ(m + n)
- D.
θ(mn)
Attempted by 179 students.
Show answer & explanation
Correct answer: C
Answer: Θ(n + m)
Method: Run a graph traversal (BFS or DFS) on an adjacency-list representation to count connected components.
Initialize all vertices as unvisited.
For each vertex, if it is unvisited, start a BFS or DFS from that vertex and mark all reachable vertices. Each such traversal identifies one connected component.
Time complexity: Each vertex is discovered and processed once (O(n)), and each undirected edge is examined at most twice (once from each endpoint), contributing O(m). Therefore the total running time is Θ(n + m).
Alternative: You can also use a union-find (disjoint set) data structure to merge endpoints of edges and count components; this runs in near-linear time O((n + m) α(n)), where α(n) is the inverse-Ackermann function (practically constant).
A video solution is available for this question — log in and enroll to watch it.