The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2k views

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. $\Theta(n)$
  2. $\Theta(n+m)$
  3. $\Theta(n^2)$
  4. $\Theta(m^2)$
asked in Algorithms by Veteran (115k points)
edited by | 2k views
0
explainaton?
+1
with Adjacency List:  O(E+V)
Adjacency matrix: O( V^2)

By the way in dense graph, E is nearly equal to V sq...so adjacency list will also take O(V^2,V)=O(V^2)
0
What is dense graph ? Is a graph with maximum edges ?
+1
in dense graph , order of no. of edges = O(|V|)^2

in sparse graph, it is O(|V|)

3 Answers

+12 votes
Best answer

Depth First Search of a graph takes $O(m+n)$ time when the graph is represented using adjacency list. In adjacency matrix representation, graph is represented as an $n * n$ matrix. To do DFS, for every vertex, we traverse the row corresponding to that vertex to find all adjacent vertices (In adjacency list representation we traverse only the adjacent vertices of the vertex). Therefore time complexity becomes $O(n^2)$.

answered by Loyal (9.3k points)
edited by
0
$O(V)$ calls are made to DFS visit and in DFS visit, examining neighbour of each vertex takes $O(V)$ times so total time $O(V^2)$
+14 votes
answered by Loyal (6.1k points)
edited by
+10 votes

1. Depth-first search requires O(V + E) time if implemented with adjacency lists

2. Depth-first search requires O(V2) time if implemented with an adjacency matrix

answered by (101 points)
edited by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,925 questions
52,325 answers
182,358 comments
67,785 users