28 votes 28 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)$ Algorithms gatecse-2008 algorithms graph-algorithms time-complexity normal + – Kathleen asked Sep 11, 2014 • edited Oct 26, 2017 by kenzou Kathleen 13.5k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Manu Thakur commented Dec 29, 2017 reply Follow Share Either BFS or DFS both can do it in $\theta(m+n)$ time. 6 votes 6 votes Vivek Jain commented Nov 10, 2018 reply Follow Share 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?? 0 votes 0 votes palashbehra5 commented Nov 18, 2021 reply Follow Share Vivek Jain https://www.geeksforgeeks.org/number-of-connected-components-of-a-graph-using-disjoint-set-union/ If you meant this algorithm, it takes O(n+m) time as well. 0 votes 0 votes cprdereddyy commented Apr 13 reply Follow Share thoose who don't know what CC arevisit this for a clear approachhttps://www.youtube.com/watch?v=8f1XPm4WOUc 0 votes 0 votes Please log in or register to add a comment.
Best answer 29 votes 29 votes Run DFS to find connected components. Its time complexity is $\Theta(m+n)$, hence (C) is the answer. Happy Mittal answered Aug 22, 2015 • edited Oct 26, 2017 by kenzou Happy Mittal comment Share Follow See all 25 Comments See all 25 25 Comments reply Madhab commented Apr 12, 2016 i edited by Madhab Apr 12, 2016 reply Follow Share The explanation of this ans can be find in :https://www.youtube.com/watch?v=r1-8p11fSPw&index=26&list=PLBF3763AF2E1C572F&nohtml5=False see first 15 minuets portion 12 votes 12 votes Vivek Jain commented Nov 10, 2018 reply Follow Share 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 votes 0 votes Verma Ashish commented Dec 24, 2018 reply Follow Share @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. 0 votes 0 votes srestha commented Jul 1, 2019 reply Follow Share @Verma Ashish What if we use Kruskal or Prims here?? 0 votes 0 votes Verma Ashish commented Jul 1, 2019 reply Follow Share We can't use prims or kruskal algorithm for finding connected components.. 0 votes 0 votes srestha commented Jul 1, 2019 reply Follow Share But why? It finds shortest path. right? So, finds connected component too. Isnot it? 0 votes 0 votes Verma Ashish commented Jul 1, 2019 i edited by Verma Ashish Jul 1, 2019 reply Follow Share 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. 4 votes 4 votes Verma Ashish commented Jul 1, 2019 reply Follow Share 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) 3 votes 3 votes srestha commented Jul 1, 2019 reply Follow Share @Verma Ashish what about sparse graph? 0 votes 0 votes srestha commented Jul 1, 2019 reply Follow Share 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 votes 0 votes Verma Ashish commented Jul 1, 2019 reply Follow Share 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 votes 0 votes Verma Ashish commented Jul 1, 2019 reply Follow Share 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.. 0 votes 0 votes srestha commented Jul 1, 2019 reply Follow Share We can't apply directly prims algorithm to disconnected graph DFS and BFS algo also doesnot support disconnected graph . 1 votes 1 votes Verma Ashish commented Jul 1, 2019 reply Follow Share We can apply DFT/BFT (depth first traversal and breadth first traversal) 0 votes 0 votes srestha commented Jul 1, 2019 reply Follow Share I havenot got what u mean . Can u explain it clearly? 0 votes 0 votes srestha commented Jul 1, 2019 reply Follow Share @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 votes 0 votes Verma Ashish commented Jul 1, 2019 reply Follow Share Sorry mam, i don't remember exact algos and forget some concepts.. So i think i have to revise Algorithm. You can refer →_→ https://stackoverflow.com/questions/3818079/why-use-dijkstras-algorithm-if-breadth-first-search-bfs-can-do-the-same-thing https://cs.stackexchange.com/questions/10047/is-dijkstras-algorithm-just-bfs-with-a-priority-queue 0 votes 0 votes Sambhrant Maurya commented Jul 30, 2019 reply Follow Share @Verma Ashish @Rajesh Pradhan What if the question was about "directed graphs"? How do we find connected components in a directed graph? 0 votes 0 votes Aks9639 commented Sep 28, 2019 reply Follow Share In directed graph same algorithm will work, you get theta(V+E) refer CLRS . 0 votes 0 votes `JEET commented Sep 29, 2019 reply Follow Share I think that is $(V+E)\log V$?? 0 votes 0 votes Aks9639 commented Sep 29, 2019 reply Follow Share @`JEET How you get (V+E) log V ? 0 votes 0 votes Chirag Shilwant commented Dec 9, 2019 reply Follow Share It's not mentioned that the graph is weighted, so no option for using Prim's and Kruskal's. 0 votes 0 votes Sambhrant Maurya commented Dec 9, 2019 i edited by ankitgupta.1729 Dec 9, 2019 reply Follow Share @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). 3 votes 3 votes Abhrajyoti00 commented Dec 11, 2022 reply Follow Share Both BFS and DFS can be used to find in $O(m+n)$ :- Undirected Graph:- Single connected component or not # Of Connected Components in G Single Bi-Connected Component or not # of Bi-Connected Components in G Directed Graph: - Single weakly connected component or not # Of weakly Connected Components in G Single strongly connected Component or not # Of strongly connected Components 1 votes 1 votes sitikant commented Aug 25, 2023 reply Follow Share Although both BFS and DFS can be used. Still DFS is preferred from memory stand points. Give it a read : https://cs.stackexchange.com/questions/73686/why-do-we-prefer-dfs-to-find-connected-components. 0 votes 0 votes Please log in or register to add a comment.
24 votes 24 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 Rajesh Pradhan answered Nov 10, 2016 Rajesh Pradhan comment Share Follow See all 2 Comments See all 2 2 Comments reply habedo007 commented Oct 23, 2017 reply Follow Share $\Theta (m+n)$ when BFS and DFS is implemented using adjacency list, else it is $\Theta (n^2)$ when implemented using adjacency matrix. 10 votes 10 votes syncronizing commented Aug 21, 2018 reply Follow Share Or we can say Max(m,n) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes To find the number of connected components using either BFS or DFS time complexity is θ(m+n). Suppose if we are using Adjacency matrix means it takes θ(n2). varunrajarathnam answered Aug 7, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes BFS and DFS is used for traversing the graph which takes O(m+n). Surya_Dev Chaturvedi answered Jan 15, 2021 Surya_Dev Chaturvedi comment Share Follow See all 0 reply Please log in or register to add a comment.