DFS Tree Edges and Classification
What you'll learn: How to classify every edge in a graph into four distinct categories based on what DFS discovers about them.
The Core Idea
When you run DFS on a graph, you don't just visit nodes—you also traverse edges. Each edge tells a story about how nodes relate to each other in the DFS exploration. By classifying edges, you gain insight into the graph's structure: which edges form the search tree, which create cycles, and which connect separate branches.
The Four Edge Types
Tree Edges
These are edges you actually follow when discovering a new node during DFS. They form the DFS tree—the backbone of your traversal. Think of them as the main roads you took to explore new territory.
Back Edges
These point from a node back to one of its ancestors in the DFS tree. They always indicate a cycle in directed graphs. Like finding a shortcut that loops you back to a place you've already been.
Forward Edges
In a directed graph, these skip ahead from an ancestor to a descendant that was discovered via a different path. Like seeing a distant cousin who's already been visited down another family branch.
Cross Edges
These connect nodes that have no ancestor-descendant relationship—they're in completely different subtrees or on the same level. Like bridges between separate neighborhoods you've explored.
How to Classify
During DFS, track each node's state (unvisited, visiting, or visited). When you encounter an edge u → v:
- If
vis unvisited: tree edge - If
vis currently being visited (still on the call stack): back edge - If
vis already finished and is a descendant: forward edge - Otherwise: cross edge
Key Takeaway: DFS edge classification reveals the hidden structure of graphs—tree edges build the traversal skeleton, back edges expose cycles, and forward/cross edges show alternative connections.