The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.6k 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.4k points)
edited by | 1.6k views
0
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.2k points)
edited by
+5

The explanation of this ans can be find in :

see first 15 minuets portion 



 


 

+10 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.5k points)
+4
$\Theta (m+n)$ when BFS and DFS is implemented using adjacency list, else it is $\Theta (n^2)$ when implemented using adjacency matrix.
–1 vote
Answer is C.
answered by Boss (19.7k 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 ... :)


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

34,781 questions
41,758 answers
118,934 comments
41,400 users