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

–2 votes
–2 votes
Answer is C.
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}$...