5. Edge Classification
- Why DFS classifies edges
- The four edge types
- Tree edges and DFS structure
- Back edges and cycle detection
- Forward and cross edges
- How timestamps reveal edge types
- Why this matters for DAGs and graph analysis
Once DFS timestamps are available, edges are no longer just connections in the graph. They acquire a structural meaning relative to the DFS forest.
In this part, we classify edges according to how they connect vertices in the recursive exploration.
5.1 Why Edge Classification Matters
DFS assigns discovery and finish times to vertices, and these timestamps allow us to interpret each edge in relation to the DFS forest.
This classification is fundamental for:
- cycle detection
- topological sorting
- reasoning about DAGs
- structural analysis of directed graphs
5.2 The Four Edge Types
In a directed graph, every edge (u, v) encountered during DFS falls into one of four categories:
| Type | Meaning |
|---|---|
| Tree edge | The edge discovers a new WHITE vertex. |
| Back edge | The edge points to an ancestor in the DFS tree. |
| Forward edge | The edge points to a proper descendant that was not discovered by this edge. |
| Cross edge | The edge connects unrelated DFS branches or different DFS trees. |
5.3 Tree Edges
An edge (u, v) is a tree edge if v is WHITE when the edge is explored.
In that case, DFS sets:
and the edge becomes part of the DFS tree (or DFS forest).
5.4 Back Edges
An edge (u, v) is a back edge if it points from a vertex to one of its ancestors in the DFS tree.
Operationally, this often appears when v is GRAY at the moment the edge is examined.
This is why DFS is the classical tool for cycle detection.
5.5 Forward Edges
An edge (u, v) is a forward edge if it points from a vertex to a proper descendant in the DFS tree, but the edge itself was not used to discover that descendant.
So the ancestor–descendant relation exists, but the edge is not a tree edge.
5.6 Cross Edges
An edge (u, v) is a cross edge if it connects vertices that are not in an ancestor–descendant relation.
Cross edges may connect:
- different branches of the same DFS tree
- different trees in the DFS forest
5.7 Characterization by Timestamps
DFS timestamps let us reason about edge types formally.
If v is a descendant of u, then:
If the intervals are disjoint, the vertices are in separate branches:
5.8 Special Case: Undirected Graphs
In undirected graphs, DFS edge classification is simpler.
Every edge is either:
- a tree edge, or
- a back edge
There are no forward or cross edges in the undirected case.
5.9 Consequence for DAGs
A directed graph is acyclic if and only if DFS finds no back edges.
This result is one of the most important consequences of DFS edge classification, and it leads directly to topological sorting.
5.10 Mini Summary
- Tree edges discover new vertices.
- Back edges point to ancestors and indicate cycles.
- Forward edges point to descendants.
- Cross edges connect separate branches.
- In undirected graphs, only tree edges and back edges occur.
Next: Part 6 — Applications I (Cycles & Topological Sorting)
Now that we know how DFS classifies edges, we can apply these structural properties to concrete problems.
In Part 6, we study how DFS detects cycles and why finish times lead naturally to topological sorting.