Depth-First Search (DFS)
Visualize Depth-First Search (DFS). Learn how to traverse graphs by exploring as deep as possible using a Stack or Recursion.
Ready to start
Stack (LIFO)
Traversal Order
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.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:
- Orange (Primary-500) Node: Currently being processed.
- Dark Orange (Primary-300) Nodes: In the Stack (waiting to be visited).
- Emerald (Emerald-500) Nodes: Completely visited.
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.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.