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