The Gateway to Computer Science Excellence

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,648 questions

56,457 answers

195,309 comments

100,136 users