The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
2.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)$
in Algorithms by Veteran (52.1k points)
edited by | 2.6k 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

+23 votes
Best answer

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

by Boss (11.2k points)
edited by
0

 

and undirect or directed doesnot matter much for these algos. Right? 

Yes. (And prim and kruskal only work for undirected graph)

And In DFS among vertices and edges , which will be greater will be answer, Means if m>n, ans will be Θ(m) and if m<n ans will be Θ(n). right? 

Hmm..

+1

We can't apply directly prims algorithm to disconnected graph

DFS and BFS algo also doesnot support disconnected graph .

0
We can apply DFT/BFT (depth first traversal and breadth first traversal)
0
I havenot got what u mean . Can u explain it clearly?
0

@Verma Ashish

Dijkstra uses BFS but Dijkstra T.C. more than BFS. Right?

That is why BFS also not a suitable option here. right??


Another question coming here, though Dijkstra uses BFS, but why Dijkstra T.C. greater than BFS?? Can u answer it?

0
0

@Verma Ashish @Rajesh Pradhan What if the question was about "directed graphs"? How do we find connected components in a directed graph?

0
In directed graph same algorithm will work, you get theta(V+E) refer CLRS .
0
I think that is $(V+E)\log V$??
0

@`JEET

How you get (V+E) log V ? 

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

by Boss (23.6k points)
+6
$\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)
–2 votes
Answer is C.
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
50,309 questions
55,743 answers
192,226 comments
90,496 users