Sign in to watch this lesson
Algorithms - Graphs I · 4:28
Depth-First Search
Depth-first search follows one road as far as it goes and backs up only when stuck, and one clock that stamps every entry and exit turns that order into structure. On a seven-node directed graph we watch nodes go white, gray and black, see the [in, out] intervals nest like parentheses (an O(1) ancestor test), and classify every edge as tree, back, forward or cross. Then we measure the price of recursion on this Mac: 64 bytes per call, so an 8 MB stack overflows around 130,000 levels, and an explicit stack of (node, next edge) frames fixes it.
You will learn
- Implement DFS with white/gray/black colours and entry/exit timestamps from a single clock, in O(n + m)
- Use the nesting of [in, out] intervals to test ancestry in O(1)
- Classify every edge of a directed graph as tree, back, forward or cross, and explain why undirected graphs have only tree and back edges
- Estimate when recursion overflows the stack and rewrite DFS with explicit (node, next-edge) frames that keep the true exit order