Engineering-Mathematics
October 5, 2023GATE 2007
October 5, 2023GATE 2008
|
Question 7
|
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
|
θ(n)
|
|
|
θ(m)
|
|
|
θ(m+n)
|
|
|
θ(mn)
|
Question 7 Explanation:
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).
Suppose if we are using Adjacency matrix means it takes θ(n2).
Correct Answer: C
Question 7 Explanation:
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).
Suppose if we are using Adjacency matrix means it takes θ(n2).