Breadth-First vs Depth-First Search
Watch two classic search algorithms explore the same maze — one in ripples, one in deep dives — and see why only one guarantees the shortest path.
📄 Illustrated notes · every chapter as a picture · printable
Quick quiz
3 questions to check your understanding.
Go deeper
University-level written lectures in The AI Lecture Hall:
Transcript
Introduction. Many AI problems are really search problems. From a start state, explore possible moves until you reach a goal. Let us compare two classic ways to explore.
Breadth-first search. Breadth-first search explores in ripples. It visits every cell one step away, then every cell two steps away, and so on. Amber cells are waiting in the queue. Because it expands by distance, the first time it reaches the goal, it has found a shortest path: here, 37 moves.
Depth-first search. Depth-first search dives down one path as far as it can, and only backtracks at dead ends. It uses a stack instead of a queue. It found the goal, but look at the path. It is 73 moves long, nearly twice the shortest route.
Queue vs stack. The only difference is the data structure. Breadth-first uses a queue, first in first out. Depth-first uses a stack, last in first out. That one choice changes everything about how they behave.
Results. On this maze, breadth-first explored 205 cells and found a 37-move path. Depth-first explored slightly fewer, 185 cells, but its path was 73 moves. Cheaper exploration, much worse answer.
Recap. To recap. Breadth-first explores level by level and finds shortest paths. Depth-first dives deep and saves memory. Both are uninformed: they have no idea where the goal is. Next, we will fix that with A star.