Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Pathfinding

Depth-First Search Visualiser

A stack, so the search runs down one corridor before trying another.

Drawthen drag on the board
Board

Depth-first search: a stack, so the newest cell comes out first. That runs down one corridor before trying another.

Cells expanded
0
On the stack
1
O(cells + edges)extra space O(cells) for the stack

There are 303 cells to search on this board. The gap between that and the cells expanded is what a better search order buys you — walls and mud change it, so redraw the board and watch it move.

  • Start
  • End
  • Wall
  • Mud (costs 5)
  • Waiting to be expanded
  • Expanded
  • Route
function dfs(grid, start, end) {
const stack = [start];
const cameFrom = new Map([[start, null]]);
while (stack.length > 0) {
const cell = stack.pop(); // the newest waiting cell
if (cell === end) return path(cameFrom, end);
for (const next of neighbours(grid, cell)) {
if (cameFrom.has(next)) continue;
cameFrom.set(next, cell);
stack.push(next);
}
}
return null; // the end is walled off
}

The highlighted line is the one that produced the picture on the left.

What Depth-First Search does

Depth-first search is breadth-first search with a stack instead of a queue. Taking the newest cell rather than the oldest means it commits to a direction and keeps going until it hits a wall, then backs up to the most recent place it had a choice. It finds a route, but almost never the shortest one.

How it works, step by step

  1. Put the starting cell on a stack and record that it came from nowhere.
  2. Take the cell from the top of the stack — the one added most recently.
  3. If it is the goal, follow the recorded parents back to rebuild the route.
  4. Otherwise push every unseen neighbour, and carry on from the last one pushed.

What to watch for

  • The visited cells form a long snaking line rather than a growing blob. That line is the search committing to a direction.
  • The route it reports usually wanders badly, even on an empty board with the goal in plain sight.
  • It can expand far fewer cells than BFS, or far more, depending entirely on whether its first guess pointed the right way.
  • Recursive DFS is the same algorithm: the call stack is the stack.

Cost

TimeO(cells + edges)
Extra spaceO(cells) for the stack
FindsSome route, rarely the shortest
Handles costsNo
Waiting listStack (last in, first out)

When to reach for it

When you need to reach everything rather than reach it quickly: exploring a whole graph, finding connected regions, detecting cycles, generating mazes, or backtracking through a puzzle. Never use it when the shortest route is what you are after.

Read more