3.3Depth-first search and edge types
The idea
Depth-first search goes as deep as possible before backing up, recording start and finish times. Its non-tree edges reveal cycles.
Think of it like this: Exploring a maze by always taking the next unexplored corridor and backtracking at dead ends.
Why it exists
Cycle detection, topological sort and strongly connected components all use DFS.
How it works
- Visit a vertex and stamp its discovery time.
- Recurse into each unvisited neighbour.
- When all neighbours are done, stamp the finish time.
- Classify every other edge: back, forward or cross.
Worked example: Directed graph with edge D → B where B is an ancestor
D → B points to a vertex still on the stack: a back edge, so the graph has a cycle.
Now play with it
- →Run the undirected DFS, then the directed one with edge classes.
- →Spot the red back edge that closes the cycle.
Yellow = waiting, white fill = current, green = finished. Thick green edges are tree / MST edges.
- discover A at time 1
- discover B at time 2
- discover C at time 3
- discover F at time 4
- discover E at time 5
- edge E-B reaches an already visited vertex: back edge (cycle)
- discover D at time 6
- edge D-A reaches an already visited vertex: back edge (cycle)
- discover G at time 7
- edge G-E reaches an already visited vertex: back edge (cycle)
- edge G-F reaches an already visited vertex: back edge (cycle)
- finish G at time 8
- finish D at time 9
- finish E at time 10
- finish F at time 11
- finish C at time 12
- finish B at time 13
- finish A at time 14
Uses recursion or a stack. Time O(V + E). In an undirected graph every non-tree edge is a back edge.
Yellow = waiting, white fill = current, green = finished. Thick green edges are tree / MST edges.
- discover A at time 1
- discover B at time 2
- discover C at time 3
- discover D at time 4
- edge D→B is a back edge (v is still on the stack: a cycle!)
- finish D at time 5
- finish C at time 6
- finish B at time 7
- edge A→D is a forward edge
- discover F at time 8
- edge F→A is a back edge (v is still on the stack: a cycle!)
- discover E at time 9
- edge E→D is a cross edge
- finish E at time 10
- finish F at time 11
- finish A at time 12
Green = tree, red = back (to an ancestor still on the stack: cycle), yellow = forward or cross. A directed graph has a cycle iff DFS finds a back edge.
Check yourself
A directed graph has a cycle if and only if DFS finds
Exam notes (the dense version)
DFS uses recursion (a stack) and records discovery d[v] and finish f[v] times. Time O(V + E). Edge classes in a directed graph: tree, back, forward, cross. A directed graph has a cycle iff DFS finds a back edge. In an undirected graph every non-tree edge is a back edge. Articulation points and bridges come from low-link values.
Previous year questions: Graph Algorithms (35)
PYQs are grouped by topic, so this is the full set for Graph Algorithms; try the ones that match this subtopic. Open all 35 on the topic page.