The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity

  1. $\Theta(n)$
  2. $\Theta(m)$
  3. $\Theta(m+n)$
  4. $\Theta(mn)$
asked in Algorithms by Veteran (59.6k points)
edited by | 1.9k views
Either  BFS or DFS both can do it in $\theta(m+n)$ time.

3 Answers

+19 votes
Best answer

Run DFS to find connected components. Its time complexity is $\Theta(m+n)$, hence (C) is the answer.

answered by Boss (11.3k points)
edited by

The explanation of this ans can be find in :

see first 15 minuets portion 


+13 votes

Both BFS or DFS can be used to find number of connected components.

The Time complexity of BFS and DFS is $\Theta$(m+n).

Hence C is Ans

answered by Boss (22.9k points)
$\Theta (m+n)$ when BFS and DFS is implemented using adjacency list, else it is $\Theta (n^2)$ when implemented using adjacency matrix.
Or we can say Max(m,n)
–1 vote
Answer is C.
answered by Boss (19.7k points)
Question asks for connected components in an undirected graph, you have given reference for finding strongly connected components in a directed graph.
ok... but is it really effect ? i mean we cant use for undirected graph ...

see this ...
This is an overkill for undirected graphs. For undirected graphs, you need to run DFS just once.
ok ok....  Thank you ... :)
what about the directed graphs???

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,748 questions
47,471 answers
62,234 users