DFS Trace Workshop: Timestamps and Edge Types

How to Read a DFS Trace

A depth-first search (DFS) follows one path as far as possible before returning to explore another. Its output depends on the order in which roots and neighbors are considered, so a trace is not reproducible unless those orders are stated. This workshop fixes those choices, records the search forest and timestamps, and classifies every edge.

Graphs are finite and simple. A directed graph has ordered edges, called arcs; an undirected graph has unordered edges. We use a recursive DFS: when a vertex is first reached, mark it discovered, then scan its neighbors in the stated order. If a neighbor has not been discovered, recursively search from it and record the edge as a tree edge. Once all neighbors have been scanned, mark the vertex finished. When a search from one root finishes, choose the next undiscovered root in the stated root order. The resulting collection of tree edges is the DFS forest.

For a directed graph, each arc receives one of four labels. A tree edge discovers its endpoint. A back edge points to a currently active vertex, which is an ancestor in the recursive call stack. A forward edge points to a descendant already discovered by a different tree edge. A cross edge joins vertices for which neither is an ancestor of the other. For an undirected graph, each edge is considered once: it is either a tree edge or a back edge joining a vertex to an ancestor. In an adjacency list an undirected edge appears at both endpoints; the second scan does not give it a new classification.

Timestamp Intervals and Edge Types

The interval \([d(v),f(v)]\) records the period in which \(v\) is active in the recursive search. If \(v\) is an ancestor of \(u\), then \(v\) is discovered before \(u\), and it finishes after \(u\). Their intervals are nested. If neither vertex is an ancestor of the other, their search calls finish one after the other, so their intervals are disjoint.

Proof. Consider the moment when the search scans \(uv\). The vertex \(u\) is active, so \(d(u)<f(u)\) and \(f(u)\) has not yet occurred. If \(v\) is undiscovered, this scan discovers it; the recursive call from \(u\) finishes only after the call from \(v\), giving \(d(u)<d(v)<f(v)<f(u)\), and \(uv\) is a tree edge. If \(v\) is active, it is on the current recursion stack. The stack consists of the active ancestors of \(u\), so \(d(v)<d(u)<f(u)<f(v)\), and the arc is back. If \(v\) is finished, it cannot be an active ancestor. If it is a descendant of \(u\), its interval lies inside \(u\)'s interval, and the arc is forward unless it was the edge that discovered \(v\). Otherwise the two vertices lie in separate completed search calls, so their intervals are disjoint and the arc is cross. These cases cover every possible state of \(v\) when the arc is scanned. \(\square\)

Proof. Let \(uv\) be an edge whose endpoints lie in different branches, so neither is an ancestor of the other. Whichever endpoint is discovered first, say \(u\), is still active when its adjacency list is scanned. At that time \(v\) cannot already be finished: the recursive search from \(u\) has not finished, and a separate branch containing \(v\) cannot have been completed inside that unfinished call without making \(v\) a descendant of \(u\). Thus \(v\) is undiscovered when \(uv\) is scanned, and DFS would discover \(v\) through \(uv\), making it a tree edge. This contradicts the assumption that it is a non-tree edge. Hence every non-tree edge joins an ancestor and a descendant. \(\square\)

Directed DFS: A Complete Trace

Notice that an endpoint being finished does not by itself make an arc cross. The interval test matters: a finished descendant gives a forward edge, while a finished vertex in a separate branch gives a cross edge.

Undirected DFS: Count Each Edge Once

Disconnected Graphs and Search Forests

A DFS started at one vertex only visits vertices reachable from that root by directed paths in a directed graph, or paths in an undirected graph. To search every vertex, the outer loop must start a fresh DFS at each still-undiscovered vertex. Each fresh start adds a root to the DFS forest and receives timestamps from the same continuing clock.

Common Pitfalls and a Reliable Checklist

Wrong calculation: In the first example, one might call \(AD\) a cross edge because \(D\) is black when \(A\) scans it. That ignores the timestamps. Since \(d(A)=1\), \(d(D)=3\), \(f(D)=4\), and \(f(A)=8\), the strict nesting \(1<3<4<8\) shows that \(D\) is a descendant of \(A\); \(AD\) is forward, not cross. The search record confirms it was not the edge that discovered \(D\).

Other errors often come from changing the convention mid-trace. State the root order and neighbor order first. Advance the clock only at discovery and finish events, not at edge scans. In an undirected graph, classify each edge once rather than counting both appearances in adjacency lists. Finally, distinguish the search forest from the whole graph: only the edges that discover new vertices belong to the forest.

For a final audit, check that every vertex has exactly one discovery and one finish time, every tree edge discovers one new vertex, and every graph edge or arc has exactly one classification. In a directed graph, use interval nesting or disjointness to verify the non-tree labels. In an undirected graph, verify that each non-tree edge joins a vertex to an ancestor.