GATE CSE 2008 | Question: 7

Question

The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity

• A. $\Theta(n)$
• B. $\Theta(m)$
• C. $\Theta(m+n)$
• D. $\Theta(mn)$

Comments

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.

---

thoose who don't know what CC are

visit this for a clear approach

https://www.youtube.com/watch?v=8f1XPm4WOUc

---

we can take both bfs or dfs but bfs can be best suited as dfs only confirms the connectivity but bfs ensures connectivity as well as shortest path.

Answer 1

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

Comments

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 

 

---

---

But then we can use disjoint sets to find the number of components. Its time complexity is only O(m). Why not option B??

---

@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.

 

---

@Verma Ashish

What if we use Kruskal or Prims here??

---

We can't use prims or kruskal algorithm for finding connected components..

---

But why? It finds shortest path. right? So, finds connected component too. Isnot it?

---

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.

---

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)

---

@Verma Ashish what about sparse graph?

---

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.

---

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). 

---

 

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

---

We can't apply directly prims algorithm to disconnected graph

DFS and BFS algo also doesnot support disconnected graph .

---

We can apply DFT/BFT (depth first traversal and breadth first traversal)

---

I havenot got what u mean . Can u explain it clearly?

---

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

---

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

 

---

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

---

In directed graph same algorithm will work, you get theta(V+E) refer CLRS .

---

I think that is $(V+E)\log V$??

---

@`JEET

How you get (V+E) log V ? 

---

It's not mentioned that the graph is weighted, so no option for using Prim's and Kruskal's.

---

@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).

---

Both BFS and DFS can be used to find in $O(m+n)$ :- 

1. Undirected Graph:-
   1. Single connected component or not
   2. # Of Connected Components in G
   3. Single Bi-Connected Component or not
   4. # of Bi-Connected Components in G
2. Directed Graph: -
   1. Single weakly connected component or not
   2. # Of weakly Connected Components in G
   3. Single strongly connected Component or not
   4. # Of strongly connected Components

---

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. 

Answer 2

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

Comments

$\Theta (m+n)$ when BFS and DFS is implemented using adjacency list, else it is $\Theta (n^2)$ when implemented using adjacency matrix.

---

Or we can say Max(m,n)

Answer 3

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).

Answer 4

To find the number of connected components in a graph, one of the most efficient algorithms you can use is the Depth-First Search (DFS) or Breadth-First Search (BFS). The time complexity of both DFS and BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Here's how you can use DFS or BFS to find the number of connected components:

1. Initialize a count: Start with a count of 0 for connected components.
2. Visit nodes: Use an array or a list to keep track of visited nodes.
3. Loop through all nodes: For each node, if it has not been visited, increment the connected component count, and perform a DFS or BFS starting from that node to mark all reachable nodes as visited.
4. Increment the count: Each time you start a DFS or BFS from an unvisited node, it means you have found a new connected component.

This approach ensures that each node and edge is checked precisely once, leading to the O(V + E) time complexity. This is optimal for most scenarios where you need to process all nodes and edges of a graph to determine connectivity.

Answer 5

BFS and DFS is used for traversing the graph which takes O(m+n).

Answer 6

(C.) θ(m+n)