The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+10 votes
1.4k views

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 (68.8k points)
edited by | 1.4k views
Either  BFS or DFS both can do it in $\theta(m+n)$ time.

3 Answers

+16 votes
Best answer

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

answered by Veteran (11.1k points)
edited by

The explanation of this ans can be find in :

see first 15 minuets portion 



 


 

+7 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 Veteran (22.7k points)
$\Theta (m+n)$ when BFS and DFS is implemented using adjacency list, else it is $\Theta (n^2)$ when implemented using adjacency matrix.
0 votes
Answer is C.
answered by Veteran (19.6k 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 ...

http://www.geeksforgeeks.org/strongly-connected-components/
This is an overkill for undirected graphs. For undirected graphs, you need to run DFS just once.
ok ok....  Thank you ... :)


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

32,470 questions
39,199 answers
108,999 comments
36,575 users