22.3 Depth-first search

22.3-1

Make a $3$-by-$3$ chart with row and column labels $\text{WHITE}$, $\text{GRAY}$, and $\text{BLACK}$. In each cell $(i, j)$, indicate whether, at any point during a depth-first search of a directed graph, there can be an edge from a vertex of color $i$ to a vertex of color $j$. For each possible edge, indicate what edge types it can be. Make a second such chart for depth-first search of an undirected graph.

According to Theorem 22.7 (Parenthesis theorem), there are 3 cases of relationship between intervals of vertex $u$ and $v$:

• $[u.d, u.f]$ and $[v.d, v.f]$ are entirely disjointed,
• $[u.d, u.f] \subset [v.d, v.f]$, and
• $[v.d, v.f] \subset [u.d, u.f]$.

We judge the possibility according to this Theorem.

• For directed graph, we can use the edge classification given by exercise 22.3-5 to simplify the problem.

  $$\begin{array}{c|ccc} from \diagdown to & \text{WHITE} & \text{GRAY} & \text{BLACK} \\ \hline \text{WHITE} & \text{All kinds} & \text{Cross, Back} & \text{Cross} \\ \text{GRAY} & \text{Tree, Forward} & \text{Tree, Forward, Back} & \text{Tree, Forward, Cross} \\ \text{BLACK} & - & \text{Back} & \text{All kinds} \end{array}$$

• For undirected graph, starting from directed chart, we remove the forward edge and the cross edge, and

  • when a back edge exist, we add a tree edge;
  • when a tree edge exist, we add a back edge.

  This is correct for the following reasons:

  1. Theorem 22.10: In a depth-first search of an undirected graph $G$, every edge of $G$ is either a tree or back edge. So tree and back edge only.
  2. If $(u, v)$ is a tree edge from $u$'s perspective, $(u, v)$ is also a back edge from $v$'s perspective.

  $$\begin{array}{c|ccc} from \diagdown to & \text{WHITE} & \text{GRAY} & \text{BLACK} \\ \hline \text{WHITE} & - & \text{Tree, Back} & \text{Tree, Back} \\ \text{GRAY} & \text{Tree, Back} & \text{Tree, Back} & \text{Tree, Back} \\ \text{BLACK} & \text{Tree, Back} & \text{Tree, Back} & - \end{array}$$

22.3-2

Show how depth-first search works on the graph of Figure 22.6. Assume that the for loop of lines 5–7 of the $\text{DFS}$ procedure considers the vertices in alphabetical order, and assume that each adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex, and show the classification of each edge.

The following table gives the discovery time and finish time for each vetex in the graph.

See the C++ demo.

$$\begin{array}{ccc} \text{Vertex} & \text{Discovered} & \text{Finished} \\ \hline q & 1 & 16 \\ r & 17 & 20 \\ s & 2 & 7 \\ t & 8 & 15 \\ u & 18 & 19 \\ v & 3 & 6 \\ w & 4 & 5 \\ x & 9 & 12 \\ y & 13 & 14 \\ z & 10 & 11 \end{array}$$

• Tree edges: $(q, s)$, $(s, v)$, $(v, w)$, $(q, t)$, $(t, x)$, $(x, z)$, $(t, y)$, $(r, u)$.
• Back edges: $(w, s)$, $(z, x)$, $(y, q)$.
• Forward edges: $(q, w)$.
• Cross edges: $(r, y)$, $(u, y)$.

22.3-3

Show the parenthesis structure of the depth-first search of Figure 22.4.

The parentheses structure of the depth-first search of Figure 22.4 is $(u(v(y(xx)y)v)u)(w(zz)w)$.

22.3-4

Show that using a single bit to store each vertex color suffices by arguing that the $\text{DFS}$ procedure would produce the same result if line 3 of $\text{DFS-VISIT}$ was removed.

Change line 3 to color = BLACK and remove line 8. Then, the algorithm would produce the same result.

22.3-5

Show that edge $(u, v)$ is

a. a tree edge or forward edge if and only if $u.d < v.d < v.f < u.f$,

b. a back edge if and only if $v.d \le u.d < u.f \le v.f$, and

c. a cross edge if and only if $v.d < v.f < u.d < u.f$.

a. $u$ is an ancestor of $v$.

b. $u$ is a descendant of $v$.

c. $v$ is visited before $u$.

22.3-6

Show that in an undirected graph, classifying an edge $(u, v)$ as a tree edge or a back edge according to whether $(u, v)$ or $(v, u)$ is encountered first during the depth-first search is equivalent to classifying it according to the ordering of the four types in the classification scheme.

By Theorem 22.10, every edge of an undirected graph is either a tree edge or a back edge. First suppose that $v$ is first discovered by exploring edge $(u, v)$. Then by definition, $(u, v)$ is a tree edge. Moreover, $(u, v)$ must have been discovered before $(v, u)$ because once $(v, u)$ is explored, $v$ is necessarily discovered. Now suppose that $v$ isn't first discovered by $(u, v)$. Then it must be discovered by $(r, v)$ for some $r\ne u$. If $u$ hasn't yet been discovered then if $(u, v)$ is explored first, it must be a back edge since $v$ is an ancestor of $u$. If $u$ has been discovered then $u$ is an ancestor of $v$, so $(v, u)$ is a back edge.

22.3-7

Rewrite the procedure $\text{DFS}$, using a stack to eliminate recursion.

See the C++ demo.

Also, see this issue for @i-to's discussion.

DFS-STACK(G)
    for each vertex u ∈ G.V
        u.color = WHITE
        u.π = NIL
    time = 0
    for each vertex u ∈ G.V
        if u.color == WHITE
            DFS-VISIT-STACK(G, u)

DFS-VISIT-STACK(G, u)
    S = Ø
    PUSH(S, u)
    time = time + 1             // white vertex u has just been discovered
    u.d = time
    u.color = GRAY
    while !STACK-EMPTY(S)
        u = TOP(S)
        v = FIRST-WHITE-NEIGHBOR(G, u)
        if v == NIL
            // u's adjacency list has been fully explored
            POP(S)
            time = time + 1
            u.f = time
            u.color = BLACK     // blackend u; it is finished
        else
            // u's adjacency list hasn't been fully explored
            v.π = u
            time = time + 1
            v.d = time
            v.color = GRAY
            PUSH(S, v)

FIRST-WHITE-NEIGHBOR(G, u)
    for each vertex v ∈ G.Adj[u]
        if v.color == WHITE
            return v
    return NIL

22.3-8

Give a counterexample to the conjecture that if a directed graph $G$ contains a path from $u$ to $v$, and if $u.d < v.d$ in a depth-first search of $G$, then $v$ is a descendant of $u$ in the depth-first forest produced.

Consider a graph with $3$ vertices $u$, $v$, and $w$, and with edges $(w, u)$, $(u, w)$, and $(w, v)$. Suppose that $\text{DFS}$ first explores $w$, and that $w$'s adjacency list has $u$ before $v$. We next discover $u$. The only adjacent vertex is $w$, but $w$ is already grey, so $u$ finishes. Since $v$ is not yet a descendant of $u$ and $u$ is finished, $v$ can never be a descendant of $u$.

22.3-9

Give a counterexample to the conjecture that if a directed graph $G$ contains a path from $u$ to $v$, then any depth-first search must result in $v.d \le u.f$.

Consider the directed graph on the vertices $\{1, 2, 3\}$, and having the edges $(1, 2)$, $(1, 3)$, $(2, 1)$ then there is a path from $2$ to $3$. However, if we start a $\text{DFS}$ at $1$ and process $2$ before $3$, we will have $2.f = 3 < 4 = 3.d$ which provides a counterexample to the given conjecture.

22.3-10

Modify the pseudocode for depth-first search so that it prints out every edge in the directed graph $G$, together with its type. Show what modifications, if any, you need to make if $G$ is undirected.

If $G$ is undirected we don't need to make any modifications.

See the C++ demo.

DFS-VISIT-PRINT(G, u)
    time = time + 1
    u.d = time
    u.color = GRAY
    for each vertex v ∈ G.Adj[u]
        if v.color == WHITE
            print "(u, v) is a tree edge."
            v.π = u
            DFS-VISIT-PRINT(G, v)
        else if v.color == GRAY
            print "(u, v) is a back edge."
        else if v.d > u.d
            print "(u, v) is a forward edge."
        else
            print "(u, v) is a cross edge."
    u.color = BLACK
    time = time + 1
    u.f = time

22.3-11

Explain how a vertex $u$ of a directed graph can end up in a depth-first tree containing only $u$, even though $u$ has both incoming and outgoing edges in $G$.

Suppose that we have a directed graph on the vertices $\{1, 2, 3\}$ and having edges $(1, 2)$ and $(2, 3)$. Then, $2$ has both incoming and outgoing edges.

If we pick our first root to be $3$, that will be in its own $\text{DFS}$ tree. Then, we pick our second root to be $2$, since the only thing it points to has already been marked $\text{BLACK}$, we won't be exploring it. Then, picking the last root to be $1$, we don't screw up the fact that $2$ is along in a $\text{DFS}$ tree even though it has both an incoming and outgoing edge in $G$.

22.3-12

Show that we can use a depth-first search of an undirected graph $G$ to identify the connected components of $G$, and that the depth-first forest contains as many trees as $G$ has connected components. More precisely, show how to modify depth-first search so that it assigns to each vertex $v$ an integer label $v.cc$ between $1$ and $k$, where $k$ is the number of connected components of $G$, such that $u.cc = v.cc$ if and only if $u$ and $v$ are in the same connected component.

The modifications work as follows: each time the if-condition of line 8 is satisfied in $\text{DFS-CC}$, we have a new root of a tree in the forest, so we update its $cc$ label to be a new value of $k$. In the recursive calls to $\text{DFS-VISIT-CC}$, we always update a descendant's connected component to agree with its ancestor's.

See the C++ demo.

DFS-CC(G)
    for each vertex u ∈ G.V
        u.color = WHITE
        u.π = NIL
    time = 0
    cc = 1
    for each vertex u ∈ G.V
        if u.color == WHITE
            u.cc = cc
            cc = cc + 1
            DFS-VISIT-CC(G, u)

DFS-VISIT-CC(G, u)
    time = time + 1
    u.d = time
    u.color = GRAY
    for each vertex v ∈ G.Adj[u]
        if v.color == WHITE
            v.cc = u.cc
            v.π = u
            DFS-VISIT-CC(G, v)
    u.color = BLACK
    time = time + 1
    u.f = time

22.3-13 $\star$

A directed graph $G = (V, E)$ is singly connected if $u \leadsto v$ implies that $G$ contains at most one simple path from $u$ to $v$ for all vertices $u, v \in V$. Give an efficient algorithm to determine whether or not a directed graph is singly connected.

This can be done in time $O(|V||E|)$. To do this, first perform a topological sort of the vertices. Then, we will contain for each vertex a list of it's ancestors with $in\text-degree$ $0$. We compute these lists for each vertex in the order starting from the earlier ones topologically.

Then, if we ever have a vertex that has the same degree $0$ vertex appearing in the lists of two of its immediate parents, we know that the graph is not singly connected. however, if at each step we have that at each step all of the parents have disjoint sets of degree $0$ vertices as ancestors, the graph is singly connected. Since, for each vertex, the amount of time required is bounded by the number of vertices times the $in\text-degree$ of the particular vertex, the total runtime is bounded by $O(|V||E|)$.