edited by
13,237 views
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

  1. $\Theta(n)$
  2. $\Theta(m)$
  3. $\Theta(m+n)$
  4. $\Theta(mn)$
edited by

6 Answers

Best answer
29 votes
29 votes

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

edited by
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

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

Answer:

Related questions

63 votes
63 votes
11 answers
1
Kathleen asked Sep 12, 2014
27,250 views
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance toonly vertex $a$only vertices $...
31 votes
31 votes
6 answers
2
Kathleen asked Sep 11, 2014
35,333 views
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is:$\text{MNOPQR}$...