Graph Algorithm 14

0. Let G of 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?

Answer
Comment
Array

Option : C
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 neighbour s in an adjacency matrix r equires O(V) time, so overall the running time will be O(V²).

Forgot your password?

I agree with the Terms.