1. The Central Idea
Depth-First Search explores a graph by following one path as far as possible before exploring alternative paths.
Starting from a source vertex s, the algorithm repeatedly moves to an unvisited neighbor until it reaches a vertex that has no unexplored edges.
2. Deep Exploration
DFS expands the search by always selecting a neighbor that has not yet been visited.
This produces long exploration chains that follow a single branch of the graph.
Only when no further expansion is possible does the algorithm return to the previous vertex and continue exploring.
3. Backtracking
When a vertex has no unvisited neighbors, DFS performs backtracking.
The algorithm returns to the most recent vertex that still has unexplored edges.
4. The Implicit Stack
The exploration process naturally forms a stack structure.
- Each recursive call pushes a vertex onto the stack
- Returning from recursion pops the vertex
DFS can therefore be implemented either with recursion or with an explicit stack.
5. Visual Intuition
The traversal behaves like exploring a maze.
- Choose a direction
- Walk forward until you hit a dead end
- Go back to the last intersection
- Try another direction
This strategy systematically explores every reachable path.
Next: Part 3 — The Algorithm (CLRS Pseudocode)
Now that we understand the intuition behind DFS, we formalize the algorithm using the classical pseudocode from Introduction to Algorithms (CLRS).