Obligatory Computer Science Comic
Depth-First Search – Analysis (continued)
White Path Theorem
Theorem: Let be a directed or undirected graph on which a depth-first search is executed. Let and be two vertices in . is a descendant of if and only if at the time when the algorithm discovers , there is a path from to that consists entirely of white vertices.
Proof: Since this is an if-and-only-if theorem, we must prove both sides of the implication.
Proof of : Suppose is a descendant of in the depth-first forest. By corollary 1 (from the last chapter), we know that . So is not discovered before is discovered, hence is white at time . Since can be any descendant of , all vertices in the unique simple path from to in the depth-first forest must be white at time . In the case that , the path just contains the vertex which is still white when the value of is set by the algorithm.
Proof of : Suppose there is a path containing only white vertices from to at time and does not become a descendant of . Let be the closest non-descendant vertex to in the path. Let be the predecessor of . Since is the closest non-descendant vertex to , is a descendant of . By corollary 1 from the last chapter, we know that (and if and are the same vertex). Since is a descendant of , it must be discovered after is discovered and before the adjacency list scan of is finished. Hence, it must be true that . The parenthesis theorem then implies that is contained entirely within the interval . By corollary 1, this means that is still a descendant of .
Note: A depth-first forest is often denoted by by convention. Just like we denote a graph as and vertices as and . Not necessary at all, just a convention.
We can use a depth-first forest to classify edges into four types:
- Tree Edges – Let be a vertex discovered by a DFS. If was first discovered by exploring any edge then that edge is a tree edge. (i.e the edges that are part of a depth-first forest .
- Back Edges – Let and be vertices in a depth-first tree such that is a descendant of . An edge connecting to its ancestor is a back-edge. In a directed graph, a self-loop is also a back-edge.
- Forward Edges – Non-tree edges that connect two vertices and such that is a descendant of in a depth-first tree.
- Cross Edges – All edges that are not tree edges, back edges or forward edges (i.e an edge that is not in any of the above three categories is a cross edge).
Let be an edge explored by the depth-first search algorithm. The color of the vertex indicates the type of edge is:
- White – tree edge
- Gray – back edge
- Black – forward or cross edge
Note: I do not understand the proof of this relation between vertex color and type of edge properly myself. The book doesn’t deal with it very formally, in my opinion. Anyway, onto the next theorem.
Theorem 2: Let be any undirected graph. In a depth-first search of , every edge of is either a tree edge or a back edge.
Proof: Let be any edge in . Suppose (without loss of generality). Then before the algorithm finishes , it must discover and finish while the color of remains gray, since is in the adjacency list of . If the direction of the edge is from to the first time the algorithm explores it, then the vertex has not been discovered before that time. This is true because if it had been discovered previously, the algorithm would have already explored the edge in the direction from to .
Since, at the time is first explored, is undiscovered, its color is white. Hence becomes a tree edge. If the algorithm explores first in the direction from to instead then, since the color of is gray, the edge becomes a back edge.