Skip to content
BENIBIX Learn

Depth-First Search (DFS)

Development🧮 Algorithms & Data StructuresSearch Algorithms

Also known as DFS, Depth First Search

Walking a graph down one path as far as it goes, then backing up.

Think of it like

Think of it like a maze. Follow one path to the end, then go back and try the next.

Example

Jack's puzzle solver tries one move after another until it gets stuck. Then it backs up one move and tries the next one.

Why it matters

Many puzzle solvers and maze games are built on it.

Definition

Depth-first search walks a graph or tree by going as deep as it can down one path first. When it hits a dead end, it steps back and tries the next branch. It keeps its place with a stack, or by calling itself with recursion. It is good for checking if two nodes connect, finding loops and solving puzzles. It does not promise the shortest path.

Common mistake

Using it to find the shortest route. DFS finds a path, not the shortest one; use BFS for that.

Key takeaways

  1. 1
    Deep first. One path to the end.
  2. 2
    Back up at dead ends. Then try the next branch.
  3. 3
    Stack or recursion. Keeps its place.

Compare