xkcd/292

**Depth-First Search – Analysis**

**Time Complexity**

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

**Paranthesis Theorem**

Theorem: Let be the graph on which the Depth-First Search algorithm gets executed. Let and be any two vertices in . Exactly one of the following three conditions must hold:

- The intervals and are entirely disjoint and neither nor are descendants of each other in the depth-first forest.
- The interval is contained entirely in the interval and is a descendant of in a depth-first tree.
- The interval is contained entirely in the interval and is a descendant of in a depth-first tree.

Proof: Proof by case analysis. We begin with the case when . There can be two subcases.

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

Subcase 2: . Since, in a depth first search, for any vertex searched by the algorithm, it must be true that . This means that the intervals and 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 is similar.

Corollary 1: Let and be any two vertices in a depth-first forest of a graph . is a proper descendant of if and only if .

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

### Like this:

Like Loading...

*Related*