GATE CSE 2014 | Set 1 | Question: 11

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 on $G$, when $G$ is represented as an adjacency matrix?

• A. $\Theta(n)$
• B. $\Theta(n+m)$
• C. $\Theta(n^2)$
• D. $\Theta(m^2)$

Comments

What is dense graph ? Is a graph with maximum edges ?

---

in dense graph , order of no. of edges = O(|V|)^2

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

---

this is asking for theta, not big Oh

Answer 1

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)$.

Correct Answer: $C$

Comments

$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)$

---

Useful : CS161Lecture09.pdf (stanford.edu)

---

got it

---

also even in adjacency list representation, if our graph is a complete graph then the time complexity to find neighbours is O(v) only

---

to whomever confusing whether it is n^2 or m^2 dfs and bfs both are based on vertices but not edges so its n^2 not m^2

Answer 2

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

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

Answer 3

Ans (C)

http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html

Comments

link not working

---

Working link: Graph Searching (archive.org)

Answer 4

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).

Answer 5

For  V  vertices and  E  edges,

Both BFS & DFS take O( V + E ) if implemented with adjacency list

& O(V^2) time if implemented with adjacency matrix.