NIELIT 2017 July Scientist B (CS) - Section B: 42

Question

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 of $G$, when $G$ is represented using adjacency matrix?

• A. $O(n)$
• B. $O(m+n)$
• C. $O(n^2)$
• D. $O(mn)$

Comments

previous year

https://gateoverflow.in/1771/gate2014-1-11

Answer 1

Option C

Let G be a graph with n vertices and m edges. the tightest upper bound on the running time of Depth First Search of G,

when G is represented as an adjacency matrix=$O(n^{2})$

when G is represented as an adjacency list=$O(n+m)$

Answer 2

option c

adjacency matrix    O(N^2)