DFS tree properties and edge classification

When you run depth-first search on a graph, the edges you traverse form a structure called the DFS tree. Edges not in the DFS tree have special properties that reveal information about the graph's shape.

Understanding DFS tree structure is the foundation for many advanced graph algorithms. Topological sorting uses the finish times from DFS. Strongly connected components algorithms use the DFS tree of the graph and its transpose. Offline lowest-common-ancestor queries use DFS ordering.

The DFS tree

When you start at a node and recursively explore all its neighbors, the edges you use to discover new nodes form a tree. If a node is already visited, the edge is not part of the tree, but it still conveys information.

Classify each edge as you encounter it:

A tree edge leads to a node you have never seen before. When you follow a tree edge, you discover a new node and add it to the DFS tree.

A back edge points to an ancestor in the DFS tree. If you reach a node that is currently on the recursion stack, you have found a back edge. Back edges indicate cycles.

A forward edge points to a descendant in the DFS tree. This happens only in directed graphs. When you finish exploring a subtree, you might encounter an edge to a node you have already fully processed.

A cross edge points to a node that is neither an ancestor nor a descendant. In undirected graphs, cross edges do not exist because an undirected edge can only be a tree edge or a back edge.

Discovery and finish times

As DFS runs, assign each node a discovery time when you first reach it and a finish time when you have explored all its neighbors. These times reveal the structure of the DFS tree.

If you discover node A before node B, and finish B before A, then B is in a subtree rooted at A. Tree edges and back edges connect nodes whose time intervals either contain or are disjoint from each other. Forward and cross edges connect nodes with non-overlapping intervals.

1import sys2
3
4def dfs(node, adj, state, discovery, finish, time_counter):5    state[node] = 'gray'6    discovery[node] = time_counter[0]7    time_counter[0] += 18
9    for neighbor in adj[node]:10        if state[neighbor] == 'white':11            dfs(neighbor, adj, state, discovery, finish, time_counter)12
13    state[node] = 'black'14    finish[node] = time_counter[0]15    time_counter[0] += 116
17
18def main() -> None:19    input_data = sys.stdin.read().split()20    if not input_data:21        return22
23    idx = 024    n = int(input_data[idx])25    m = int(input_data[idx + 1])26    idx += 227
28    adj = [[] for _ in range(n)]29    for _ in range(m):30        u = int(input_data[idx])31        v = int(input_data[idx + 1])32        idx += 233        adj[u].append(v)34
35    state = ['white'] * n36    discovery = [-1] * n37    finish = [-1] * n38    time_counter = [0]39
40    for i in range(n):41        if state[i] == 'white':42            dfs(i, adj, state, discovery, finish, time_counter)43
44    result = []45    for i in range(n):46        result.append(str(i) + " " + str(discovery[i]) + " " + str(finish[i]))47
48    sys.stdout.write("\n".join(result) + "\n")49
50
51if __name__ == "__main__":52    main()

5 6
0 1
0 2
1 3
2 3
3 4
2 4

0 0 9
1 1 6
2 7 8
3 2 5
4 3 4

The program walks a graph and records when each node is discovered and finished. In the output, node 0 is discovered at time 0 and finishes at time 9. Nodes 1 and 2 are discovered and finished while processing node 0, so their time intervals are nested inside 0's interval.

Cycle detection

A directed graph has a cycle if and only if DFS finds a back edge. When you encounter an edge to a node that is currently on the recursion stack, you have found a cycle. You can detect this by marking nodes as visited but not yet finished.

def is_back_edge(state, neighbor):    return state[neighbor] == "gray"  # gray: currently on the recursion stack

Use three states: white (never visited), gray (visiting, on stack), and black (finished). A back edge always goes from a gray node to another gray node.

Topological sorting

In a directed acyclic graph, ordering nodes by decreasing finish time gives a topological sort. Finish times capture the dependency structure: if A must finish before B, then A has a smaller or equal finish time.

Tree edges and back edges respect this ordering. Forward and cross edges point from higher finish times to lower finish times, which is consistent with topological order. If your graph has a cycle, a back edge will always appear, which you can use to detect cycles before attempting a sort.

A topological sort is useful for scheduling tasks with dependencies. If task A must finish before task B, draw an edge from A to B. A topological sort gives a valid order to execute all tasks: do task 0, then task 1, and so on. Any task's dependencies are already complete when you reach it.

A second example: cycle detection in a project graph

A software project has 5 tasks: parsing (0), type checking (1), optimization (2), code generation (3), and linking (4). Parsing has no dependencies. Type checking depends on parsing, optimization depends on type checking, code generation depends on both optimization and type checking, and linking depends on code generation.

Now suppose someone incorrectly adds an edge: linking creates a job that modifies the parser (adding a feature), so parsing now depends on linking. This creates a cycle: 0 → 1 → 2 → 3 → 4 → 0.

DFS starting at node 0 discovers 0, then 1, then 2, then 3, then 4 in turn, each one gray while its own exploration is still in progress. From node 4, there is an edge back to node 0. Node 0 is still gray, since the whole chain is still on the recursion stack waiting for node 0 to finish. That gray state is exactly what marks 4 → 0 as a back edge, and a cycle. If you only tracked visited versus not-visited, you would miss it: node 0 was already marked visited long before you got to node 4.

Common mistakes

One mistake is to forget that back edges only exist in directed graphs. In an undirected graph, an edge to a visited neighbor is always a back edge, not a separate edge type. Many graph algorithms assume directed graphs, so read the problem carefully before applying DFS tree classification.

Another mistake is to confuse discovery time and finish time when classifying edges. Discovery time is when you first enter a node. Finish time is when you have explored all neighbors and return from the recursive call. An edge from node A to node B is a tree edge if B is white (never visited). It is a back edge if B is gray (currently on the recursion stack). It is a forward edge if B is black and discovery[A] < discovery[B]. It is a cross edge if B is black and discovery[A] > discovery[B]. Getting these conditions wrong causes misclassification and breaks algorithms that depend on the classification.

A third mistake is to not mark nodes as being on the current recursion stack. If you only mark nodes as visited or finished, you cannot distinguish back edges from cross edges. You need a three-state system: white (never visited), gray (currently visiting, on the recursion stack), and black (finished). When you encounter an edge to a gray node, you have a back edge and possibly a cycle. Skipping the gray state allows cross edges to masquerade as back edges, producing false cycle detections.

Recap

The DFS tree captures the structure of a graph during depth-first search. Edges not in the tree are classified as back, forward, or cross based on their relationship to the tree structure. Discovery and finish times capture the nesting structure of the DFS tree. Back edges indicate cycles, and finish-time ordering gives topological sorts. Understanding DFS tree properties is essential for advanced graph algorithms.