Breadth-First vs Depth-First Search — lecture notes
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.
0:001. 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.
0:122. 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.
0:333. 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.
0:514. 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.
1:065. 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.
1:186. 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.
Key takeaways
- Breadth-first search uses a queue and finds a shortest path when all steps cost the same.
- Depth-first search uses a stack, needs little memory, but can return long paths.
- On our maze: BFS 205 cells explored and a 37-move path; DFS 185 cells and a 73-move path.
- Both are uninformed — they don’t know where the goal is.
Check yourself
- Which data structure does breadth-first search use?
Show answer
A queue — BFS explores oldest-discovered cells first: first in, first out.
- Which algorithm guarantees a shortest path when every move costs the same?
Show answer
Breadth-first search — BFS expands in order of distance, so its first path to the goal is shortest.
- Why are BFS and DFS called “uninformed”?
Show answer
They use no information about where the goal is — They explore without any estimate of distance to the goal.
Go deeper
- Uninformed Search: BFS, DFS, Uniform-Cost and Iterative Deepening · The AI Lecture Hall
© 2026 Janin A Apurba, CSE, AUST · Advanced ICT Officer, CNRS-UNHCR. All rights reserved. Notes for the animated lecture at https://ai-in-motion.vercel.app/watch/breadth-first-and-depth-first-search.html