DFS Forests and Edge Types
Depth-first search (DFS) explores a vertex by recursively exploring each as-yet-unvisited neighbor before returning to the current vertex. Its discovery and finish times record when each recursive call begins and ends. These times reveal how an edge relates to the search: it may discover a new vertex, point back along the active recursion, point forward to a descendant already explored, or cross to a vertex completed in a different branch.
Throughout, a directed graph has directed edges and no loops or multiple edges. An undirected graph is finite and simple. A DFS run uses a fixed order for the vertices considered as possible roots and a fixed order for each vertex’s neighbors. Changing either order can change the DFS forest and edge classifications.
A vertex is white before it is discovered, gray from its discovery until its finish, and black after it finishes. Write \(d(v)\) for its discovery time and \(f(v)\) for its finish time. A single clock increases by one at every discovery and finish event, so all these times are distinct. The recursive invariant is that the gray vertices are exactly the vertices whose DFS calls are currently active; they lie on the call stack.
Directed Edges and Timestamp Intervals
The interval from \(d(v)\) to \(f(v)\) records the lifetime of \(v\)'s recursive call. For an edge \(u\to v\), the four types have these timestamp patterns:
| Type | Timestamp pattern | Relationship |
|---|---|---|
| Tree | \(d(u)<d(v)<f(v)<f(u)\) | \(v\) is a child of \(u\) |
| Back | \(d(v)<d(u)<f(u)<f(v)\) | \(v\) is an ancestor of \(u\) |
| Forward | \(d(u)<d(v)<f(v)<f(u)\) | \(v\) is a proper descendant of \(u\), but not its child |
| Cross | \(d(v)<f(v)<d(u)<f(u)\), or the reverse ordering of the two intervals | Neither endpoint is an ancestor of the other |
Tree and forward edges have the same interval pattern; the distinction is whether the edge itself discovered \(v\). A tree edge is therefore identified by the DFS parent relation as well as its times. For any non-tree edge, the timestamp pattern determines its type.
Proof. Consider an edge \(u\to v\) when the search examines it. If \(v\) is white, the search discovers \(v\) from \(u\), so the edge is a tree edge and \(v\)'s recursive call finishes before \(u\)'s call finishes. Thus \(d(u)<d(v)<f(v)<f(u)\). If \(v\) is gray, then \(v\) is on the active call stack. Since \(u\) is also active, \(v\) is an ancestor of \(u\); the edge is back, with \(d(v)<d(u)<f(u)<f(v)\). If \(v\) is black, its call has finished. When \(d(u)<d(v)\), \(v\) was discovered and finished during \(u\)'s active call, giving \(d(u)<d(v)<f(v)<f(u)\). This is a forward edge unless the edge discovered \(v\), in which case it is a tree edge. When \(d(v)<d(u)\), \(v\) cannot be an active ancestor of \(u\), because it is black. Its call finished before \(u\)'s call began, so \(d(v)<f(v)<d(u)<f(u)\); the edge is cross. These cases exhaust the possible colors of \(v\) when the edge is examined. For a non-tree edge, the ancestor or descendant relation in the nested cases gives the stated type, and the disjoint case gives a cross edge. \(\square\)
Worked Directed Classification
Worked Example: All Four Directed Edge Types
Let \(G\) have vertex set \(\{1,2,3,4,5,6\}\) and directed edge set \(\{1\to2,1\to3,1\to6,2\to4,4\to1,4\to3,3\to2,3\to5,6\to3\}\). Start at vertex \(1\), and examine each vertex’s outgoing neighbors in the order shown by the edge list. The DFS follows \(1\to2\to4\to3\to5\) before returning to \(1\), then discovers \(6\).
The event sequence, with the clock increasing by one at each event, is:
- Discover \(1\) at time \(1\), \(2\) at time \(2\), \(4\) at time \(3\), \(3\) at time \(4\), and \(5\) at time \(5\).
- Finish \(5\) at time \(6\), \(3\) at time \(7\), \(4\) at time \(8\), and \(2\) at time \(9\).
- Discover \(6\) at time \(10\), finish \(6\) at time \(11\), and finish \(1\) at time \(12\).
The tree edges are \(1\to2, 2\to4, 4\to3, 3\to5,\) and \(1\to6\), because each discovers its endpoint. The remaining classifications follow from the timestamps:
- \(4\to1\) and \(3\to2\) are back edges. For \(4\to1\), \(1<3<8<12\); for \(3\to2\), \(2<4<7<9\). In each case the target is an ancestor.
- \(1\to3\) is a forward edge: \(1<4<7<12\). Vertex \(3\) is a descendant of \(1\), but \(1\to3\) did not discover it.
- \(6\to3\) is a cross edge: \(4<7<10<11\). The interval for \(3\) has finished before \(6\) is discovered.
Check: There are five tree edges and four non-tree edges, accounting for all nine edges in the specified set. The non-tree edges have been classified as two back, one forward, and one cross.
Why Undirected DFS Has No Cross Edges
For undirected graphs, DFS edge classification has a simpler form: every edge is either a tree edge or a back edge. Here a non-tree edge is called a back edge when it joins a vertex to one of its ancestors. The edge is undirected, so it is not helpful to orient it as “forward”; the classification is about the relationship between its endpoints in the DFS tree.
Proof. Consider an undirected edge \(uv\), and consider the first time either endpoint examines it. If the other endpoint is white, DFS discovers it through this edge, which makes \(uv\) a tree edge. Otherwise the other endpoint is gray or black. It cannot be black at this first examination: if it had already finished, it would previously have examined \(uv\) while \(u\) was still white, and that examination would have discovered \(u\). If the other endpoint is gray, both endpoints are on the active DFS call stack. Active calls form one chain, so one endpoint is an ancestor of the other. Thus every edge is a tree edge or joins an ancestor and a descendant. A cross edge would have endpoints in separate branches, neither an ancestor of the other, which the argument rules out. \(\square\)
When an undirected graph is stored with each edge listed at both endpoints, the same edge can be encountered twice. For classification, count the edge once: it is a tree edge when it first discovers a vertex, and otherwise it joins that vertex to an ancestor. The second encounter does not create a new edge type.
Worked Example: Classifying an Undirected DFS
Let \(G\) have vertex set \(\{a,b,c,d,e\}\) and edge set \(\{ab,ac,bc,bd,de\}\). Start at \(a\) and examine neighbors in alphabetical order.
Discover \(a\) at time \(1\). Its first neighbor \(b\) is white, so \(ab\) is a tree edge and \(b\) is discovered at time \(2\). At \(b\), the neighbor \(a\) is its parent, so the edge \(ab\) is already accounted for. The next neighbor \(c\) is white: \(bc\) is a tree edge, and \(c\) is discovered at time \(3\). At \(c\), the edge \(ca\) joins \(c\) to its gray ancestor \(a\), so \(ac\) is a back edge. Finish \(c\) at time \(4\), then return to \(b\). Its next unvisited neighbor \(d\) gives the tree edge \(bd\), with \(d\) discovered at time \(5\). The edge \(de\) discovers \(e\) at time \(6\); finish \(e,d,b\) at times \(7,8,9\), respectively. Finally finish \(a\) at time \(10\).
The tree edges are \(ab,bc,bd,de\), and the only non-tree edge is \(ac\), a back edge. The intervals for \(a\) and \(c\) are \([1,10]\) and \([3,4]\), so \(c\)'s interval lies inside \(a\)'s, as expected for an ancestor-descendant edge.
Check: The five listed edges consist of four tree edges and one back edge. The DFS tree has five vertices and four edges, and the remaining graph edge is \(ac\).
Search Order and a Common Pitfall
Edge types describe a particular DFS run, not just the graph. The same edge may be classified differently if the neighbor order changes. In the directed example, \(1\to3\) was forward because \(3\) was found inside the search started from \(1\), through \(1\to2\to4\to3\). A different neighbor order could make \(1\to3\) a tree edge instead. The graph still has the same edges; its DFS forest and timestamps have changed.
Common mistake: calling every edge to a black vertex a cross edge. In the directed example, \(1\to3\) points to a black vertex when examined, but its interval satisfies \(1<4<7<12\), so \(3\) is a descendant of \(1\) and the edge is forward. By contrast, \(6\to3\) has \(4<7<10<11\), so its intervals are disjoint and it is cross. The correction is to compare both endpoints’ discovery and finish times, rather than using the target’s black color alone.
For a directed graph, a back edge points from a vertex to an ancestor and therefore gives a directed cycle along the tree path from that ancestor to the vertex, followed by the back edge. Forward and cross edges do not have this interpretation from their classification alone. In undirected DFS, non-tree edges always go between ancestor and descendant, a fact useful when analyzing algorithms that inspect the DFS tree and its remaining edges.
Check Your Understanding
Use the definitions and timestamp patterns to answer these questions.
- A directed edge \(u\to v\) is non-tree and has \(d(u)=2,\ d(v)=5,\ f(v)=8,\ f(u)=11\). Classify it and explain which interval pattern applies.
- In a directed DFS, what relationship between the endpoints makes a non-tree edge a back edge?
- Can an undirected DFS have a non-tree edge between vertices in separate DFS-tree branches? Justify your answer.
- For the directed graph in the first worked example, why is \(1\to3\) not a tree edge even though its timestamp interval is nested?
- Why should a DFS trace specify the order in which each vertex’s neighbors are examined?