Course contentsShow
← Computer Science
Lesson 712 of 2,87217. Graph Traversal AlgorithmsFree lesson

DFS Tree Edges and Classification

Classify edges as tree, back, forward, or cross edges during DFS traversal.

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 v is unvisited: tree edge
  • If v is currently being visited (still on the call stack): back edge
  • If v is 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.