Home/Pathfinding/Depth-first search
Search algorithmsCTRL K

Depth-first search

· depth-first · one corridor at a time
/pathfinding/depth-first-search
EXPANDED
0
closed cells
STACK
1
waiting on the stack
PUSHED
0
cells pushed so far
PATH
—
length once the goal is reached
WALLS
28%
of 880 cells blocked
closedopencurrentpathstart / goal
44×20 · 28% walls · seed 7 · 1086 steps
step 0 / 1085
Walls28
dfs.ts
1
function dfs(grid: Grid, start: Cell, goal: Cell) {
2
  const stack: Cell[] = [start];
3
  const seen = new Set([start]), parent = new Map();
4
  while (stack.length > 0) {
5
    const current = stack.pop()!; // newest first
6
    if (current === goal) return rebuild(parent, current);
7
    for (const neighbor of neighbors(grid, current)) {
8
      if (seen.has(neighbor)) continue;
9
      seen.add(neighbor);
10
      parent.set(neighbor, current);
11
      stack.push(neighbor);
12
    }
13
  }
14
  return null;
15
}
CURRENT STEP
line 2

Start at (12, 1), goal at (5, 42). The open set holds only the start.

// how it works

Understanding Depth-first search

DFS · finds a path, rarely the shortest
01

The idea

Depth-first search takes the newest open cell instead of the oldest: a stack instead of a queue. It dives down one corridor as far as it can, and only when it is stuck does it back up to the last junction with an untried neighbour.

That gives it a long, winding frontier and a path that follows the order neighbours were pushed, not the geometry of the maze. It finds a path if one exists, with tiny memory, but the path is usually far from the shortest.

02

The four stages

1
popthe newest open cell
2
checkis it the goal? then rebuild
3
pushunvisited neighbours go on top
4
pathfollow parents back to start
03

Complexity

best
O(d)the first corridor leads to the goal
average
O(V + E)every cell and edge at most once
worst
O(V + E)goal in the last corridor tried
space
O(V)the stack, usually far smaller than BFS's queue
04

Versus its siblings

PATH LENGTH · 44×20 MAZE
dfs
141
greedy
66
bfs
54
a*
54
dijkstra
54
same maze, same start and goal · only DFS and greedy give up on the shortest path
05

Pseudocode

DFS(start, goal)
  stack ← [start]; seen ← {start}
  while stack not empty
    current ← pop the newest
    if current = goal: return path via parent
    for each neighbour of current not in seen
      add neighbour to seen; parent[neighbour] ← current; push neighbour
06

When to use

Any path will do: maze generation, connectivity checks, flood fills, cycle detection, topological sorts.
Deep, narrow search spaces where memory matters: DFS keeps one path in memory, BFS keeps a whole frontier.
07

Pitfalls

Not shortest: on an open grid the path snakes along the push order and can be several times longer than optimal.
The recursive version overflows the call stack on big grids; use an explicit stack.
Without a visited set it loops forever on any cycle.
08

History

Depth-first search is the maze-walking method Charles Pierre Trémaux described in the 19th century: mark each passage as you enter it and back out of dead ends. John Hopcroft and Robert Tarjan turned it into a linear-time tool for graphs in 1973, and Tarjan's version won them the Turing Award in 1986.

Back to Pathfinding