Question on graphs


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 ?

  1. Θ(n)
  2. Θ(n + m)
  3. Θ(n2)
  4. Θ(m2)


Option C is correct. The tight upper bound is n2, because each vertex may be connected to every other vertex in the worst case, i.e. fully connected graph.