The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
2k 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 (59.7k points)
edited by | 2k views
+1
Either  BFS or DFS both can do it in $\theta(m+n)$ time.
0
But then we can use disjoint sets to find the number of connected components. Its time complexity is only O(m). Why not option B??

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
+6

The explanation of this ans can be find in :

see first 15 minuets portion 



 


0
But then we can use disjoint sets to find the number of components. Its time complexity is only O(m). Why not option B??
+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 (23.1k points)
+5
$\Theta (m+n)$ when BFS and DFS is implemented using adjacency list, else it is $\Theta (n^2)$ when implemented using adjacency matrix.
0
Or we can say Max(m,n)
–1 vote
Answer is C.
answered by Boss (19.9k points)
+2
Question asks for connected components in an undirected graph, you have given reference for finding strongly connected components in a directed graph.
+1
ok... but is it really effect ? i mean we cant use for undirected graph ...

see this ...

http://www.geeksforgeeks.org/strongly-connected-components/
+2
This is an overkill for undirected graphs. For undirected graphs, you need to run DFS just once.
0
ok ok....  Thank you ... :)
0
what about the directed graphs???
Answer:

Related questions



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

44,474 questions
49,930 answers
165,530 comments
65,900 users