GATE CS 2014 Set 1 Q.21 (CS Q.11): Graph Traversals, Topological Sort and Connectivity

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?

$\Theta(n)$

$\Theta(n + m)$

$\Theta(n^2)$

$\Theta(m^2)$

Official answer and solution

Official answer: C
From: Official GATE 2014 answer key

Solution

Analyze the number of operations in Depth First Search when using an adjacency matrix representation.

In Depth First Search (DFS), each of the $n$ vertices is visited at most once.

When a graph is represented as an adjacency matrix of size $n \times n$ :

To determine all outgoing edges from a vertex $u$ , the algorithm must inspect the entire row corresponding to $u$ in the adjacency matrix.
Each row has length $n$ , requiring $\Theta(n)$ time per vertex.
Since there are $n$ vertices, inspecting all rows takes $n \times \Theta(n) = \Theta(n^2)$ time.

Even if the graph is sparse ( $m \ll n^2$ ), the algorithm must still scan all $n^2$ entries of the matrix.

Therefore, the running time is $\Theta(n^2)$ .

Final answer

Common trap

Confusing the adjacency matrix DFS running time $\Theta(n^2)$ with the adjacency list running time $\Theta(n + m)$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 1
Question: 21 of 65, printed as CS Q.11
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source