The Gateway to Computer Science Excellence

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

- $\Theta(n)$
- $\Theta(m)$
- $\Theta(m+n)$
- $\Theta(mn)$

+25 votes

Best answer

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??

0

@Vivek Jain can you explain how to use disjoint sets?? I'm not getting what is your approach??

According to me it should be O(m+n) by using dfs or bfs.

+3

Prims algorithm can't be applied on disconnected components (forest).

But if we talk in terms of complexity then prims and kruskal both take $O(m\log n)$ time. And if graph is dense then m=n(n-1)/2 (for complete graph).

Here our intention is not to calculate minimum cost (or mst) , and finding minimum edge(sorting) is going to increase complexity in prim/kruskal.

But if we talk in terms of complexity then prims and kruskal both take $O(m\log n)$ time. And if graph is dense then m=n(n-1)/2 (for complete graph).

Here our intention is not to calculate minimum cost (or mst) , and finding minimum edge(sorting) is going to increase complexity in prim/kruskal.

+2

And these algos will not work for directed graphs..

So in case of directed graph also bfs/dfs are used for finding strongly connected components.. in O(m+n)

So in case of directed graph also bfs/dfs are used for finding strongly connected components.. in O(m+n)

0

I think DFS and BFS both work for `unweighted graph`

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

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

Where as kruskal, prims takes $\Theta \left ( mn \right )$ in worst case,

Which is much larger time than BFS and DFS.

0

what about sparse graph?

O(n logn)

We can't apply directly prims algorithm to disconnected graph. We might be able if we do some modifications.

Bfs/dfs don't care about weighted or unweighted graph. These are just search traversals which forms a tree.(need not be minimum cost tree).

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

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

Sorry mam, i don't remember exact algos and forget some concepts.. So i think i have to revise Algorithm.

You can refer →_→

https://cs.stackexchange.com/questions/10047/is-dijkstras-algorithm-just-bfs-with-a-priority-queue

0

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

+1

@Aks9639 Yes found it. There is no such thing as "connected components" in a directed graph. We use the term "connected components" for undirected graphs and "strongly connected components" for directed graphs. Finding strongly connected components in a directed graph is given by Kosaraju's algo which is an application of DFS. So TC is O(V+E).

+16 votes

–2 votes

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

see this ...

http://www.geeksforgeeks.org/strongly-connected-components/

52,345 questions

60,471 answers

201,798 comments

95,274 users