Breadth-first search

A small maze, explored from its top-left cell. Watch the search spread one layer at a time, with its queue below.

⋯50void bfs(int s)51{52    int ring[V];53    int head = 0, count = 0;54    for (int v = 0; v < V; v++) {55        dist[v] = -1;56        parent[v] = -1;57    }58    dist[s] = 0;59    ring[(head + count) % V] = s;60    count++;61    while (count > 0) {62        int u = ring[head];63        head = (head + 1) % V;64        count--;65        for (const struct enode *e = adj[u]; e != NULL; e = e->next) {66            if (dist[e->to] < 0) {67                dist[e->to] = dist[u] + 1;68                parent[e->to] = u;69                ring[(head + count) % V] = e->to;70                count++;71            }72        }73    }74}75 76int main(void)77{78    const char *maze[ROWS] = { "...#.", ".#...", ".###.", "....." };79    build(maze);80    bfs(START);81    for (int r = 0; r < ROWS; r++) {82        for (int c = 0; c < COLS; c++) {83            if (maze[r][c] == '#')84                printf(" #");85            else86                printf(" %d", dist[r * COLS + c]);87        }88        printf("\n");89    }90    int path[V];91    int len = 0;92    for (int v = GOAL; v != -1; v = parent[v]) {93        path[len] = v;94        len++;95    }96    printf("route:");97    for (int i = len - 1; i >= 0; i--)98        printf(" %d", path[i]);99    printf("\n");100    for (int v = 0; v < V; v++) {

A wave from the start

Breadth-first search explores a graph from a start vertex in layers: first the start, then every vertex one edge away, then every vertex two edges away, and so on. Here the graph is a maze. Each open cell is a vertex, numbered r · 5 + c, and two open cells side by side or one above the other are joined by an edge. The maze’s lists are built as in storing a graph, an arc each way for each pair of open neighbours.

The search keeps a queue, first in, first out, as in ring buffers. It takes the vertex at the front, and puts each of its neighbours that has not been reached yet at the back.

The code and its cost

The queue and the marks

bfs keeps three arrays of 20: dist, a vertex’s distance in edges or −1 while it is unreached; parent, the vertex it was reached from; and ring, the queue.

dist[s] = 0;
ring[(head + count) % V] = s;
count++;
while (count > 0) {
    int u = ring[head];
    head = (head + 1) % V;
    count--;
    for (const struct enode *e = adj[u]; e != NULL; e = e->next) {
        if (dist[e->to] < 0) {
            dist[e->to] = dist[u] + 1;
            parent[e->to] = u;
            ring[(head + count) % V] = e->to;
            count++;
        }
    }
}

A vertex’s distance is set when it is queued, not when it leaves the queue. That is what stops a second neighbour from queueing it again: by then its dist is no longer −1. So each vertex enters the queue at most once, and a ring of V cells never fills.

Layers

The queue holds at most two layers at once: the end of layer k, then the start of layer k + 1 behind it. So the vertices leave in order of distance, every vertex of layer k before any of layer k + 1. From cell 0 the layers are:

The first time a vertex is reached, it is reached by a shortest route in edges, and nothing later improves its number. BFS does not try every route: it reaches each vertex once.

The tree of parents

Each reached vertex but the start has one parent, so the parents form a tree. Following them from any vertex leads back to the start by a shortest route. main reads the route to the goal, cell 4, backwards into path, then prints it from the start:

 0 1 2 # 6
 1 # 3 4 5
 2 # # # 6
 3 4 5 6 7
route: 0 1 2 7 8 9 4

The goal has one open neighbour, cell 9, so its route is the only shortest one.

The cost

Each vertex is queued once and taken once, and each list is walked once, when its vertex is taken. The lists of an undirected graph hold 2E nodes, one for each end of each edge, so that is V + 2E steps in all: O(V + E), for a graph stored as lists.

When it is not enough

BFS finds the route with the fewest edges. When edges have weights, such as road lengths, the fewest edges is not always the least total, and Dijkstra’s algorithm is needed.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic maze.c -o maze
./maze
gcc -std=c11 -Wall -Wextra -pedantic -DSTART=19 maze.c -o maze
./maze

Worked example

The house graph. On the graph of storing a graph, from 0, visiting neighbours smallest first: the distances of vertices 0 to 5 are 0 1 1 2 2 3, the parents of 1 to 5 are 0 0 1 2 4, and the route to 5 is 0 2 4 5.

Another start. From cell 19, the goal is only 3 steps away, 19, 14, 9, 4, though 19 is the farthest cell from 0.

A large grid. On an open 1,000 × 1,000 grid, BFS from a corner reaches all 1,000,000 cells, each once, and the far corner at distance 1,998: 999 steps across and 999 down.

Two checks. Which cells are at distance 6 from 0? (4, 14 and 18.) Why is dist set when a vertex is queued, not when it leaves? (So that no later neighbour queues it again.)

Where it’s used

Routes with equal steps. Moving through a grid or a network where each step costs the same.

Puzzles. Each position of a puzzle is a vertex and each move an edge; BFS finds a solution in the fewest moves.

Social networks. Everyone within two links of a person is the first two layers from them.

Flood fill. A paint program’s fill spreads from the clicked pixel to every touching pixel of the same colour.

Reference card

Next, depth-first search goes deep before it goes wide.

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.