Traversal Example: The Fewest Moves Through a Maze Grid

Every open cell is a vertex and its four neighbours are its edges, so a grid needs no adjacency list at all.

A grid of open cells and walls is a graph that is never written down: each open cell is a vertex, and its edges go to the open cells directly above, below, left and right of it. This example runs breadth-first search on such a grid to find the fewest moves from the entrance to the exit, and shows the distances spreading one move at a time.

The maze has 4 rows and 5 columns. S is the entrance at the top left, E the exit at the bottom right, and # a wall.

text

S . . # .
# # . # .
. . . . .
. # # . E

The neighbours of the cell at row r and column c come from adding the four offsets (−1, 0), (1, 0), (0, −1) and (0, 1). A neighbour counts only if it is inside the grid and not a wall, and those two checks replace the adjacency list. Everything else is breadth-first search as it was on the six-vertex graph, with a cell as the vertex and the same distance and parent records.

Distances from the entrance, as breadth-first search finds them

Distance 0

The entrance is the only cell at distance 0.

text

0 . . # .
# # . # .
. . . . .
. # # . .

Distances 1 to 3

Walls leave one way out at each step, so a single cell joins at each of distances 1, 2 and 3, down the corridor to the middle row.

text

0 1 2 # .
# # 3 # .
. . . . .
. # # . .

Distance 4

The search reaches the open middle row.

text

0 1 2 # .
# # 3 # .
. . 4 . .
. # # . .

Distance 5

The row splits the search both ways, so two cells join.

text

0 1 2 # .
# # 3 # .
. 5 4 5 .
. # # . .

Distance 6

Three cells join: both ends of the middle row and the cell below the right-hand 5.

text

0 1 2 # .
# # 3 # .
6 5 4 5 6
. # # 6 .

Distance 7

The exit is among the three cells at distance 7, so the fewest moves is 7.

text

Following parents back from the exit gives the route (0,0) (0,1) (0,2) (1,2) (2,2) (2,3) (3,3) (3,4), as (row, column) pairs: 7 moves. Another route of 7 goes through (2,4) instead of (3,3), and breadth-first search returns whichever its neighbour order found first; both are shortest. The run reached 14 open cells in all, the farthest, at the top right, 8 moves away.

The same reading turns many problems into a traversal. A board game's legal moves, a flood fill in a paint program and the spread of something from cell to cell each have a cell as the vertex and a rule for its neighbours. When the question is the fewest moves, the traversal is breadth-first; when it only asks what can be reached, either search will do.

← → move through sections and cards