recategorized by
892 views
3 votes
3 votes

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

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

2 Answers

0 votes
0 votes
we   can find  the  no of  connected   components by   BFS  DFS  

apply  bfs   dfs   in graph

no of times bfs/dfs  applied to complete traversal =no of components

so O(m+n)
Answer:

Related questions

0 votes
0 votes
1 answer
4
admin asked Apr 2, 2020
1,631 views
The advantage of better testing in software development is in waterfall modelprototypingiterativeall of these