Project ForgeAlgorithms
Graph Algorithms
GATE 2008
Easy
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)
- Θ(m+n)
- DΘ(mn)
Explanation
A single BFS or DFS traversal, restarting from any unvisited vertex, visits every vertex and edge exactly once (amortized), counting connected components as the number of restarts needed — giving Θ(m+n) time.
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.