All lessons

Breadth-First Search (BFS)

9 min · Python examples

Explore a graph level by level: shortest steps in an unweighted grid or maze.

Techniques · Breadth-First Search (BFS)0/5 cleared

Enemy 1 of 5

This code uses a queue to search a small grid, moving up, down, left, and right around walls, to find the fewest steps from the start corner to the goal corner. Press Run to see the step count.

Why this works

BFS uses a queue: visit a node, enqueue all unvisited neighbors, repeat. First time you reach a cell is via the fewest steps (in unweighted graphs).

On a grid, neighbors are usually up/down/left/right.

You
Hotfix Ember
Loading editor…
Target output: 4