# Algorithms Notes – Chapter 9

xkcd/292

Depth-First Search – Analysis

Time Complexity

Let $G = (V, E)$ be the graph on which the Depth-First Search algorithm gets executed. Not taking into account the time taken by $DFS-VISIT$, the time taken by $DFS$ is essentially of the same order as the time taken by both the for loops in $DFS$. Since both for loops have time $latex\Theta(|V|)$, $DFS$ takes time $\Theta(|V|)$ if one excludes the calls to $DFS-VISIT$. Since $DFS-VISIT$ is called exactly once for each vertex in the graph $G$, the for loop in $DFS-VISIT$ executes $Adj[v]$ times for any vertex $v$ on which it is run. Hence (by the handshaking lemma) the total time for running $DFS-VISIT$ on all vertices in $G$ is $\sum_{v \in V} = \Theta (|E|)$. Hence the time complexity of the algorithm is $\Theta (|V| + |E|)$.

Paranthesis Theorem

Theorem: Let $G = (V, E)$ be the graph on which the Depth-First Search algorithm gets executed. Let $u$ and $v$ be any two vertices in $G$. Exactly one of the following three conditions must hold:

1. The intervals $[u.d, u.f]$ and $[v.d, v.f]$ are entirely disjoint and neither $u$ nor $v$ are descendants of each other in the depth-first forest.
2. The interval $[u.d, u.f]$ is contained entirely in the interval $[v.d, v.f]$ and $u$ is a descendant of $v$ in a depth-first tree.
3. The interval $[v.d, v.f]$ is contained entirely in the interval $[u.d, u.f]$ and $v$ is a descendant of $u$ in a depth-first tree.

Proof: Proof by case analysis. We begin with the case when $u.d < v.d$. There can be two subcases.

Subcase 1: $v.d < u.f$. This means that $v$ was discovered when $u$ was gray and, hence, $v$ is a descendant of $u$. Since $v$ was discovered after you, its adjacency list scan has to be completed before the search returns to scanning the adjacency list of $u$. Hence it must be true that $v.f < u.f$. In other words, case 2 of the theorem is true in this subcase.

Subcase 2: $u.f < v.d$. Since, in a depth first search, $w.d < w.f$ for any vertex $w$ searched by the algorithm, it must be true that $u.d < u.f < v.d < v.f$. This means that the intervals $[u.d, u.f]$ and $[v.d, v.f]$ are disjoint. Since the intervals are disjoint, neither of the two vertices was discovered while the other was gray. In other words, neither vertex is a descendant of the other.

The proof for the case when $v.d < u.d$ is similar. $\square$

Corollary 1: Let $v$ and $u$ be any two vertices in a depth-first forest of a graph $G$. $v$ is a proper descendant of $u$ if and only if $u.d < v.d < v.f < u.f$.

Proof: Immediate from the paranthesis theorem. (Once again, don’t blame me for lack of explanation. Blame the textbook Introduction to Algorithms 3rd Edition by Cormen et al.).