Algorithms Notes – Chapter 9

goto

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s