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

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