22-1 Classifying edges by breadth-first search

A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first tree can also be used to classify the edges reachable from the source of the search into the same four categories.

a. Prove that in a breadth-first search of an undirected graph, the following properties hold:

  1. There are no back edges and no forward edges.
  2. For each tree edge $(u, v)$, we have $v.d = u.d + 1$.
  3. For each cross edge $(u, v)$, we have $v.d = u.d$ or $v.d = u.d + 1$.

b. Prove that in a breadth-first search of a directed graph, the following properties hold:

  1. There are no forward edges.
  2. For each tree edge $(u, v)$, we have $v.d = u.d + 1$.
  3. For each cross edge $(u, v)$, we have $v.d \le u.d + 1$.
  4. For each back edge $(u, v)$, we have $0 \le v.d \le u.d$.

a.

  1. Suppose $(u, v)$ is a back edge or a forward edge in a $\text{BFS}$ of an undirected graph. Then one of $u$ and $v$, say $u$, is a proper ancestor of the other ($v$) in the breadth-first tree. Since we explore all edges of $u$ before exploring any edges of any of $u$'s descendants, we must explore the edge $(u, v)$ at the time we explore $u$. But then $(u, v)$ must be a tree edge.
  2. In $\text{BFS}$, an edge $(u, v)$ is a tree edge when we set $v.\pi \leftarrow u$. But we only do so when we set $v.d \leftarrow u.d + 1$. Since neither $u.d$ nor $v.d$ ever changes thereafter, we have $v.d=u.d+1$ when $\text{BFS}$ completes.
  3. Consider a cross edge $(u, v)$ where, without loss of generality, $u$ is visited before $v$. At the time we visit $u$, vertex $v$ must already be on the queue, for otherwise $(u, v)$ would be a tree edge. Because $v$ is on the queue, we have $v.d \le u.d + 1$ by Lemma 22.3. By Corollary 22.4, we have $v.d \ge u.d$. Thus, either $v.d = u.d$ or $v.d = u.d + 1$.

b.

  1. Suppose $(u, v)$ is a forward edge. Then we would have explored it while visiting $u$, and it would have been a tree edge.
  2. Same as for undirected graphs.
  3. For any edge $(u, v)$, whether or not it's a cross edge, we cannot have $v.d > u.d + 1$, since we visit $v$ at the latest when we explore edge $(u, v)$. Thus, $v.d \le u.d + 1$.
  4. Clearly, $v.d \ge 0$ for all vertices $v$. For a back edge $(u, v)$, $v$ is an ancestor of $u$ in the breadth-first tree, which means that $v.d\le u.d$. (Note that since self-loops are considered to be back edges, we could have $u = v$.)