Breadth-first search

Breadth-first search (BFS) finds the fewest edges from one vertex to every other vertex of a graph in which every edge counts the same, such as flights between cities or moves in a maze. If the edges have different lengths, use Dijkstra's algorithm instead.

Explanation

For example, 6 cities (vertices) are joined by direct flights (edges). How many flights does it take to get from city 1 to each city? City 1 needs 0. Its neighbours, cities 2 and 3, are 1 flight away. Their neighbours, cities 4, 5 and 6, are 2 flights away. The answer spreads from city 1 like ripples on water, one layer at a time.

Fig. 1. The answers spread from city 1, one layer at a time.

This map has no cycles: you can't fly away from a city and come back to it by another route. So there is only one way to reach each city, and the first time we reach a city, we already know how many flights it takes.

A bigger map has 8 cities and 9 flights, and we look for the fewest flights from city 1 to city 5.

Fig. 2. Find the fewest flights from city 1 to city 5. City 8 has no flights.

This map has cycles, so a city can be reached in several ways. City 5 can be reached through city 2, or through cities 3 and 4. We need a way to make sure that the route we find first is the shortest one.

The obvious way to explore is to go deep: keep flying on from the newest city you found. City 1 finds cities 2 and 3. Going on from city 3, the newest, finds cities 4 and 6. City 6 finds city 7. Then city 4 finds city 5 and writes 3 flights, along the red route through cities 3 and 4, but a shorter (blue) route to city 5 exists.

Fig. 3. Going deep reaches city 5 along the red route (3 flights). The blue route needs 2.

The fix is to go wide before going deep: check all neighbours of a city before going on from any of them. In practice, handle the cities in the order they were found, oldest first. A city found earlier is never farther away than a city found later, so all cities 1 flight away are handled before any city 2 flights away, just like the ripples on the tree. A list where cities join at the back and leave from the front is a queue.

Breadth-first search (BFS) takes the cities from a queue in the order they were found and gives each new neighbour one flight more than the city it was found from.

City 1 gets distance 0 and joins the queue.

City 1 is taken from the front of the queue.

City 2 is found from city 1 and gets distance 0 + 1 = 1. It joins the back of the queue.

City 3 is found from city 1 and gets distance 0 + 1 = 1. It joins the back of the queue.

City 2 is taken from the front of the queue.

City 1 was already found, so it keeps its distance 0.

City 4 is found from city 2 and gets distance 1 + 1 = 2. It joins the back of the queue.

City 5 is found from city 2 and gets distance 1 + 1 = 2. It joins the back of the queue.

City 3 is taken from the front of the queue.

City 1 was already found, so it keeps its distance 0.

City 4 was already found, so it keeps its distance 2.

City 6 is found from city 3 and gets distance 1 + 1 = 2. It joins the back of the queue.

City 4 is taken from the front of the queue.

City 2 was already found, so it keeps its distance 1.

City 3 was already found, so it keeps its distance 1.

City 6 was already found, so it keeps its distance 2.

City 5 was already found, so it keeps its distance 2.

City 5 is taken from the front of the queue.

City 2 was already found, so it keeps its distance 1.

City 4 was already found, so it keeps its distance 2.

City 6 is taken from the front of the queue.

City 4 was already found, so it keeps its distance 2.

City 3 was already found, so it keeps its distance 1.

City 7 is found from city 6 and gets distance 2 + 1 = 3. It joins the back of the queue.

City 7 is taken from the front of the queue.

City 6 was already found, so it keeps its distance 2.

The queue is empty. City 8 was never found: no flight leads to it.

1/27

Fig. 4. Step through BFS on the 8-city map with the buttons. Green cities are taken, light blue cities are found and wait in the queue, shown below the map. A grey arrow points to a city that was already found.

City 5 gets 2 as soon as city 2 is taken, so the fewest flights from city 1 to city 5 is 2. The same run also gives the fewest flights from city 1 to every other city: 1 for cities 2 and 3, 2 for cities 4, 5 and 6, and 3 for city 7. City 8 is never found, because no flight leads to it. The fewest flights to a city is its distance.

Each city can also remember the city it was found from. Following these back from city 5 gives the route 5, 2, 1, as Fig. 5 shows.

Fig. 5. Each city's distance is next to it, and the dark lines are the flights each city was found from. Following them back from city 5 gives the blue route 5, 2, 1.

Mazes

The same wave works on a maze. Each open cell is a city, a move to a side neighbour is a flight, and the grey cells are walls. Starting from S, the cells 1 move away light up first, then the cells 2 moves away, and so on. The wave reaches the exit E after 8 moves, so the fewest number of moves from S to E is 8.

Fig. 6. The wave spreads from S through the open cells, one layer per step, and reaches E after 8 moves.

Implementation

In code and in the proof we say vertex and edge; the map examples keep cities and flights. The start vertex is s. Let's keep the distances in an array d: d[v] is the distance of vertex v. When BFS ends, d[v] is the fewest edges from s to v. Before v is reached, d[v] = -1, so we need no separate array of marks. In the code comments, the step in which a vertex is reached is called "mark it".

A city that has been found is reached, and handling it is taking it from the queue. The queue holds the vertices that are reached but not yet taken: the boxes under the map in Fig. 4. Looking at every neighbour of a taken vertex is called expanding its edges. Neighbours that are already reached are skipped: these are the grey arrows in Fig. 4.

A vertex is reached at the moment it is pushed, not when it is taken. So each vertex enters the queue once.

For a start vertex s, the algorithm is:

1. Initialise: d[v] = -1 for every vertex, d[s] = 0, and the queue holds s.

2. Take the next vertex v from the front of the queue.

3. Expand its edges: look at each neighbour u of v.

4. Mark it: if d[u] == -1, then u is reached: set d[u] = d[v] + 1 and push u to the back of the queue.

5. Stop when the queue is empty; otherwise repeat from step 2.

The program reads n and m, then m lines u v: a two-way edge between u and v. Vertices are numbered from 1 to n, and the start is vertex 1. The program prints the distance to every vertex, and -1 for a vertex that can't be reached. Then it prints a shortest route from vertex 1 to a target t, using parent[u]: the vertex that reached u (the dark edges in Fig. 5). Walking back along parent from t ends at vertex 1, where parent[1] = 0. For the 8-city map the input is:

8 9
1 2
1 3
2 4
3 4
2 5
4 6
3 6
6 7
4 5

The graph is stored as an adjacency list, where adj[v] lists the neighbours of v. The comments name the steps above.

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);   // remove this line if the graph is directed
    }

    int s = 1;
    vector<int> d(n + 1, -1);
    vector<int> parent(n + 1, 0);   // only needed to print the route
    queue<int> q;

    // initialise
    d[s] = 0;
    q.push(s);

    while (!q.empty()) {          // stop: when the queue is empty
        // take the next vertex
        int v = q.front();
        q.pop();

        // expand its edges
        for (int u : adj[v]) {
            if (d[u] == -1) {
                // mark it
                d[u] = d[v] + 1;
                parent[u] = v;   // only needed to print the route
                q.push(u);
            }
        }
    }

    for (int v = 1; v <= n; v++) {
        cout << d[v] << (v < n ? ' ' : '\n');
    }

    // print a shortest route from s to t; remove this block if you only need distances
    int t = 7;
    if (d[t] != -1) {
        vector<int> route;
        for (int v = t; v != 0; v = parent[v]) route.push_back(v);
        reverse(route.begin(), route.end());
        for (int v : route) cout << v << ' ';
        cout << '\n';
    }
}

If only one target matters, the loop can stop as soon as the target is reached.

Each vertex is pushed and taken at most once, and each edge is checked twice in an undirected graph, once from each end, and once in a directed graph. So BFS takes O(n + m) time and O(n + m) memory for adj, d and the queue.

For t = 7 the program prints the route 1 3 6 7. The order of the neighbours in adj does not change the distances, but when there are several shortest routes it can change which one parent gives.

BFS on a grid

Here is the maze from Fig. 6, with # for walls. Each move goes to one of the four side neighbours of a cell.

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

Each open cell is a vertex, and two open side neighbours are joined by an edge. We write (r, c) for the cell in row r and column c, numbered from 0 as in the code, so S is (0, 0) and E is (4, 4).

In the code, a vertex is a pair (r, c), d is a two-dimensional array filled with $-1$, the queue holds pairs, and the four moves are listed in dr and dc. Before reading a cell, check that it is inside the grid and is not a wall. Here g holds the rows of the maze as strings, the grid has R rows and C columns, and S is at row sr, column sc:

int dr[] = {-1, 1, 0, 0};   // up, down, left, right
int dc[] = {0, 0, -1, 1};

// initialise
vector<vector<int>> d(R, vector<int>(C, -1));
queue<pair<int, int>> q;
d[sr][sc] = 0;
q.push({sr, sc});

while (!q.empty()) {
    // take the next vertex
    auto [r, c] = q.front();
    q.pop();

    // expand its edges
    for (int k = 0; k < 4; k++) {
        int nr = r + dr[k], nc = c + dc[k];
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;  // outside the grid
        if (g[nr][nc] == '#') continue;                        // wall
        if (d[nr][nc] == -1) {
            // mark it
            d[nr][nc] = d[r][c] + 1;
            q.push({nr, nc});
        }
    }
}

Each cell has at most 4 edges, so BFS on the grid takes O(R \cdot C) time. A 1000 \times 1000 grid needs about 4 \cdot 10^6 edge checks.

Correctness proof

BFS keeps an invariant on the queue, which always holds some vertices with distance $k$ at the front and possibly some with k + 1 behind them.

At the start the queue holds only $s$, so the invariant holds. When a vertex $v$ with distance $k$ is taken, every vertex left in the queue has $k$ or k + 1. The vertices it reaches get k + 1 and go to the back. So the queue still holds $k$ values, then k + 1 values. The queue rows in the step figure show this. As a result, vertices are taken in layers: all of layer 0, then all of layer 1, then all of layer 2, and so on.

Take a vertex $u$ that is first reached from $v$, so d_u = d_v + 1, and assume that every vertex taken before $u$ already has the fewest edges as its distance. This holds for $s$, and the argument below carries it on to each next vertex. Could a route to $u$ have fewer edges? The vertex just before $u$ on that route would have distance less than d_v. Vertices are taken in order of distance, so it would have been taken before $v$, and it would have reached $u$ first with a smaller distance. That did not happen, so no shorter route exists, and d_u is the fewest edges.

When edges have different lengths

The proof counts edges. If each flight has a length and the question asks for the shortest total length, BFS gives the wrong answer. Take a map of 4 cities with the flights 1–2, 2–4, 1–3 and 3–4, and give the flight 2–4 length 5 and every other flight length 1.

Fig. 7. Both routes to city 4 take 2 flights. The red route has length 6, the blue route has length 2.

BFS handles city 2 before city 3, so it reaches city 4 through city 2, along the red route of length 6. The blue route through city 3 also takes 2 flights but has length 2. BFS only counts flights, so it can't tell the two routes apart. When flights have different lengths, use Dijkstra's algorithm.

Common mistakes

• Giving a vertex its distance when it is taken instead of when it is reached, so a vertex already in the queue can be pushed again and get a larger distance. Set d[u] at the push, and only if d[u] == -1.

• Using depth-first search to find the fewest edges: it goes deep first and often finds a vertex along a longer route. Use BFS; depth-first search gives correct distances only on a tree.

• Forgetting d[s] = 0, so the start keeps $-1$, is reached again from a neighbour, and every distance shifts. Set d[s] = 0 before the loop.

• Taking vertices from the top of a stack instead of the front of a queue, which loses the order by distance and gives some vertices too large a distance. Use a queue.

Similar algorithms

Depth-first search also reaches every vertex that can be reached, in O(n + m). Use it to check reachability, find connected components or cycles.

Dijkstra's algorithm solves the same problem when edges have different lengths that are not negative. It uses a priority queue and gives a vertex its final distance when it is taken, not when it is pushed, and runs in O((n + m) \log m).

0-1 BFS handles edges of length 0 or 1. It replaces the queue with a deque, pushes a vertex to the front for a 0-edge and to the back for a 1-edge, and still runs in O(n + m).

BFS from several start vertices finds the distance to the nearest of them: push all of them with distance 0 before the loop and leave the rest unchanged.

In many problems the graph is not given. The vertices are numbers, board positions or pairs (cell, extra information), and the edges are the allowed moves. BFS works the same on such a state graph, as long as each move counts as one edge.

Practice