in Algorithms recategorized by
890 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)$
in Algorithms recategorized by
by
890 views

1 comment

Correct option is C
0
0

2 Answers

0 votes
0 votes

option C

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

for explanation  refer the link

https://gateoverflow.in/405/gate2008-7

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