Depth-first search

Follow one branch as deep as it goes, then backtrack. BFS with a stack instead of a queue.

The stack makes it go deep

• Recurse into the first unseen neighbor, then ITS first unseen neighbor…
• A recursive call is a push; a return is a pop
• The stack holds only the current root-to-here path → O(depth) memory
• Swap stack → queue and it becomes BFS

Watch it bore in

Orange = visiting · blue = recursion stack (active path) · green = backtracked. One long tendril, not a wave.

DFS wins on memory

Wide tree, 8191 nodes: DFS held 13, BFS held 4096 → 315× less.

What DFS is for

• Cycle detection (three colors: white / gray / black)
• Topological sort (finish-order, next chapter)
• Connected & strongly-connected components
• Backtracking search (try → recurse → undo)

Two traps

• NOT shortest paths — its route can wander (that's BFS)
• Recursive form overflows the call stack on deep graphs → use the iterative stack

Takeaway

BFS and DFS are a matched pair: one data-structure choice apart. Queue = breadth + shortest paths. Stack = depth + structure. Read every graph algorithm as "BFS or DFS, plus what?" Next: topological sort.