BFS and DFS: searching a maze
Send a search through a maze, one cell at a time. Breadth-first search spreads out in rings with a queue and finds the shortest way; depth-first search dives down one corridor with a stack. Compare the paths they find and how many cells each one visits.
Core concept
Breadth-first search (BFS) visits cells in order of distance using a queue, so its path is always a shortest one; depth-first search (DFS) follows one way as far as it can using a stack, so its path can be longer
Topic: Algorithms
A maze is a grid of cells, some of them walls. To find the way from the start S to the flag, a program keeps a list of cells it still has to look at. It takes one cell out, checks whether it is the flag, and if not adds that cell's open neighbours that it has not seen yet. The only difference between the two searches is which cell it takes out next. Breadth-first search (BFS) keeps the list as a queue and takes the oldest cell, so it spreads out evenly, one step further each time, like ripples in a pond. Its path is always a shortest one. Depth-first search (DFS) keeps the list as a stack and takes the newest cell, so it rushes down one corridor until it is stuck, then backs up. Its path can be much longer. Both remember where each cell was reached from, so at the end the path is traced back from the flag.
What you will learn
- Trace BFS with a queue and DFS with a stack, cell by cell.
- Explain why BFS always finds a shortest path in a grid.
- Compare the paths and the cells visited by BFS and DFS.
- Explain how a search knows that there is no way at all.
Before you start
- Know what a queue (first in, first out) and a stack (last in, first out) are.
Materials
- Squared paper to draw your own maze
Equipment
- None
Procedure
- Run breadth-first search on the open maze and note the path length and the cells visited.
- Run depth-first search on the same maze and compare.
- Try the walled maze, then the corridor maze, with both searches.
- Answer the practice challenges.