![GATE 2014 [Set-1]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
Question 8113 – Data-Structures
April 17, 2024Question 8516 – Data-Structures
April 17, 2024GATE 2014 [Set-1]
| Question 21 |
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
| θ(n) | |
| θ(n+m) | |
| θ(n2) | |
| θ(m2) |
Question 21 Explanation:
DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V2).
Correct Answer: C
Question 21 Explanation:
DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V2).