Lesson 22.4 · Depth-First Search
Enumerating Paths: DFS + Backtracking
To list every path, keep the current path, add a node before recursing and remove it after. In a DAG no visited set is needed.
10 min
Think of it like this
Writing down every route from home to school on a map with one-way streets: you trace a route, note it, then erase back to the last turn and try the other street.
1.Path, recurse, undo
This is backtracking (Module 13) on a graph. In a DAG, the same node may appear on several different paths, so you don't mark it visited globally. In a graph with cycles, mark nodes only for the current path (unmark on the way back) to avoid looping.
The number of paths can be exponential, so the output size dominates the cost.
Remember
- Add, recurse, remove.
- DAG: no global visited set.
- Exponential output is expected.
Common mistakes
- Adding the shared path list to the answer without copying it.