GATE CS 2014 Set 1 Q11 — Graph Traversals (BFS, DFS)

To find the running time of Depth First Search (DFS) on a graph $G$ represented as an adjacency matrix, we analyze the work done during the traversal:

1. Initialization: Initializing the visited array of size $n$ takes $\Theta(n)$ time.
2. Vertex Exploration: DFS visits each of the $n$ vertices exactly once.
3. Finding Neighbors: For each vertex $u$ being visited, we must identify all its adjacent vertices to explore further. In an adjacency matrix of size $n \times n$, finding the neighbors of $u$ requires scanning the entire row corresponding to $u$. This scan takes $\Theta(n)$ time per vertex, independent of the actual number of edges $m$ incident on $u$.

Summing this up over all $n$ vertices:

Thus, the tightest upper bound on the running time of DFS when using an adjacency matrix is $\Theta(n^2)$.