Card 01/ 08
Grid Traversal: A Grid Is a Graph Whose Edges You Never Build
Every cell is a vertex and its neighbours above, below, left and right are its edges, so a search needs only the grid and four directions.
A grid of cells is a graph: each open cell is a vertex, and its edges join it to the open cells directly above, below, left and right. The cue is a property of the problem, a map of cells where movement goes from a cell to a cell beside it, whatever the map is called. No adjacency list is ever built, because a cell's neighbours are four additions away: from (row, column), add or subtract one from the row or the column and check that the result is on the grid and open. Breadth-first search, which visits a graph in waves of increasing distance using a queue, is the Graph Traversal topic in Algorithms; here it runs on a grid of 3 rows and 4 columns, from S at (0, 0) to T at (2, 3), with # for a wall. Rows are numbered from 0 at the top and columns from 0 at the left.
The search keeps one invariant: every cell in the queue is at distance d or d + 1 from the start, so the first time a cell is reached, it is reached by a shortest route.
S . # .
. . . .
# . # THow many moves is T from S?
5: down to (1, 0) or right to (0, 1), on to (1, 1), then right along row 1 to (1, 3) and down to T. The wall at (2, 2) and the one at (0, 2) block the shorter-looking ways.
Each step shows the grid at the start of a wave, with the distance written in every cell reached so far and . in the cells not yet reached, then the cells waiting in the queue. A cell gets its distance when it is first reached, so the next wave's cells are already numbered before their turn.
Breadth-first search from (0, 0), one wave at a time
Wave 0: the start
0 . # .
. . . .
# . # .
queue: (0, 0)Wave 1: the two neighbours of the start
0 1 # .
1 . . .
# . # .
queue: (1, 0) (0, 1)Wave 2: one cell, (1, 1)
0 1 # .
1 2 . .
# . # .
queue: (1, 1)Wave 3: two cells, around the wall at (0, 2)
0 1 # .
1 2 3 .
# 3 # .
queue: (2, 1) (1, 2)Wave 4: the end of row 1
0 1 # .
1 2 3 4
# 3 # .
queue: (1, 3)Wave 5: T, at distance 5
0 1 # 5
1 2 3 4
# 3 # 5
queue: (0, 3) (2, 3)Every cell enters the queue once and looks at four neighbours, so the search is O(R · C) time and space for a grid of R rows and C columns: the graph has R · C vertices and at most 4 edges each.
A stone dropped in a pond spreads the same way: the ripple reaches every point at the same distance at the same moment, and the first ripple to reach a point came the shortest way. The likeness breaks at the moves. A ripple spreads in every direction at once and smoothly, while the search moves in whole steps and only up, down, left and right, so a diagonal neighbour is two moves away.
← → move through sections and cards