Depth-First Search (DFS)
Depth-first search (DFS) traverses a graph by exploring as deep as possible along each branch before backtracking, using a stack or recursion.
START
Stack (LIFO)
Visit order
Nothing visited yet
Start at A. Push it onto the stack.
Next
Pop A and mark it visited — position 1 in the order.
Start
Edges
Intuition
Imagine solving a maze.
You follow a path until you hit a dead end, then you backtrack to the last junction and try a different path.
DFS explores as far as possible along each branch before backtracking. It dives deep!
Concept
Depth-First Search (DFS) is a graph traversal algorithm that explores as deep as possible along each branch before backtracking.
It uses a Stack (Last-In-First-Out) data structure, or implicit recursion stack.
How it Works
- Push the starting node to Stack (or call recursive function).
- Mark node as visited.
- Process node.
- For every unvisited neighbor:
- Recursively call DFS (or push to Stack).
Step-by-Step Breakdown
Watch the visualization above:
- Solid blue node: The node just popped and visited.
- Pale blue node with a blue outline: On the stack, not yet visited.
- Green node: Visited.
- Stack (LIFO) panel: The last entry is the top and is popped next. A red entry was already visited by another branch and is discarded when popped.
When to Use
Use DFS when:
- Solving puzzles with valid solutions (mazes, sudoku).
- Detecting cycles in a graph.
- Checking if a graph is bipartite.
- Topological sorting.
- Finding strongly connected components.
When NOT to Use
- Shortest Path: DFS does NOT guarantee the shortest path. It might go down a very long rabbit hole first.
- Stack Overflow: Deep recursion on very large graphs can cause stack overflow errors.
How to Identify
Problems asking to "visit all nodes", "find any path", "detect cycle", or "backtracking" usually imply DFS.
Preparing for interviews? This topic is also taught as a pattern:
Introduction to DFS
Applying for software engineering roles? Free, no sign-up: