TwiddleLab / Artificial Intelligence / Search, Games and Plans

Breadth-First and Depth-First

Lesson 2 of 11 · 7 min · Free, no account needed

What you will learn

• A search keeps a waiting list of squares it has found but not checked yet.
• Breadth-first takes the oldest card (a queue). It spreads in rings and finds the shortest path.
• Depth-first takes the newest card (a stack). It dives deep and finds a path, not always the shortest.
• In code the difference is one line: todo.pop(0) or todo.pop().

Start the lesson

How the lesson goes

1. The robot only sees the squares next to it. Which plan is sure to find the shortest way to the star?

2. Plan one: the ripple.

   Step through it. Each checked square shows how many steps it is from the start.

3. Your turn to be the ripple. Tap the square it checks next.

   Yellow squares are on the waiting list. The ripple always takes the oldest card.

4. Plan two: the dive.

   Same maze, same list. Only one thing changes: it takes the newest card.

5. The two plans have names.

   Breadth-first search takes the oldest card. A list like that is a queue: first in, first out. Depth-first search takes the newest card. That list is a stack: last in, first out.

6. Now be the dive. Tap the square it checks next.

   Depth-first takes the newest card on the list.

7. This robot should be breadth-first, but it dives. Fix its code.

   In Python the waiting list is a list called todo. Run it, change one line, run again.

   New squares are appended to the end of todo. todo.pop() takes the end, the newest: depth-first. todo.pop(0) takes the front, the oldest: breadth-first. One line decides the whole search.

8. Send the dive on a detour.

   Add walls to this open maze until the dive's path is at least 32 steps.

9. A rescue drone must reach the star by the shortest route through your maze. Which list should it use?

   Play both, then tap the board you would trust.

   Breadth-first checks squares in order of distance, so the first time it reaches the star it has found the shortest path. Depth-first may get there sooner or later, but its path can be much longer.

10. Speed round: four small mazes. Tap the next square.

    Each board says which plan it runs. Three lives.

Previous lesson: AI as Search · Next lesson: Heuristics: A* Finds the Way · Part of the course: Search, Games and Plans

Lessons are interactive and need JavaScript. Turn it on to play them.