Skip to content

Breadth-first search

Explore a graph in rings: first the start, then everything one edge away, then everything two edges away, and so on. A queue keeps the order, and the first time you reach a vertex is by a shortest path.

Time Extra space Finds
\(O(V + E)\) \(O(V)\) fewest-edges distances and paths from one start; everything reachable

The idea

Drop a stone in a pond: the ripple reaches nearby points first and far points later. BFS spreads through a graph the same way. It keeps a queue of vertices that have been reached but not yet explored. It takes the oldest one, looks at its neighbours, and every neighbour not seen before gets distance one more than the current vertex and joins the back of the queue.

Because vertices leave the queue in order of distance (all distance-1 vertices before any distance-2 vertex), the first time BFS reaches a vertex, it has found a path with the fewest possible edges. Remembering who discovered each vertex (its parent) lets you rebuild that path backwards.

How it works

  1. dist[start] = 0, every other distance \(-1\) (unseen); put start in the queue.
  2. While the queue is not empty: take u from the front; for each neighbour v with dist[v] = -1, set dist[v] = dist[u] + 1, parent[v] = u, and add v to the back.

Code

from collections import deque


def bfs(adj, start):
    """Fewest-edges distance from start to every vertex (-1 if unreachable), and each vertex's parent."""
    dist = [-1] * len(adj)
    parent = [-1] * len(adj)
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()                      # the oldest vertex in the queue: nearest first
        for v in adj[u]:
            if dist[v] == -1:                # first time we reach v: this is the shortest way
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    return dist, parent


def path(parent, target):
    """Walks the parents back from target and reverses: the shortest path from the start."""
    out = []
    while target != -1:
        out.append(target)
        target = parent[target]
    return out[::-1]


def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:                       # undirected: store both directions
        adj[u].append(v)
        adj[v].append(u)
    return adj


if __name__ == "__main__":
    adj = build(8, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (2, 5), (6, 7)])
    dist, parent = bfs(adj, 0)
    print(dist)
    print(path(parent, 4), path(parent, 5))
    print([v for v in range(8) if dist[v] == -1])   # not reachable from 0

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Bfs {
    /** Fewest-edges distance from start to every vertex (-1 if unreachable); fills parent[]. */
    static int[] bfs(List<List<Integer>> adj, int start, int[] parent) {
        int[] dist = new int[adj.size()];
        Arrays.fill(dist, -1);
        Arrays.fill(parent, -1);
        dist[start] = 0;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(start);
        while (!q.isEmpty()) {
            int u = q.poll();                         // the oldest vertex in the queue: nearest first
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {                  // first time we reach v: this is the shortest way
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    q.add(v);
                }
            }
        }
        return dist;
    }

    /** Walks the parents back from target and reverses: the shortest path from the start. */
    static List<Integer> path(int[] parent, int target) {
        List<Integer> out = new ArrayList<>();
        for (; target != -1; target = parent[target]) out.add(target);
        Collections.reverse(out);
        return out;
    }

    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }   // undirected
        return adj;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = build(8, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}, {2, 5}, {6, 7}});
        int[] parent = new int[8];
        int[] dist = bfs(adj, 0, parent);
        System.out.println(Arrays.toString(dist));
        System.out.println(path(parent, 4) + " " + path(parent, 5));
        List<Integer> unreachable = new ArrayList<>();
        for (int v = 0; v < 8; v++) if (dist[v] == -1) unreachable.add(v);
        System.out.println(unreachable);
    }
}

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

// Fewest-edges distance from start to every vertex (-1 if unreachable); fills parent.
vector<int> bfs(const vector<vector<int>>& adj, int start, vector<int>& parent) {
    vector<int> dist(adj.size(), -1);
    parent.assign(adj.size(), -1);
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();                  // the oldest vertex in the queue: nearest first
        for (int v : adj[u]) {
            if (dist[v] == -1) {                     // first time we reach v: this is the shortest way
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    return dist;
}

// Walks the parents back from target and reverses: the shortest path from the start.
vector<int> path(const vector<int>& parent, int target) {
    vector<int> out;
    for (; target != -1; target = parent[target]) out.push_back(target);
    reverse(out.begin(), out.end());
    return out;
}

vector<vector<int>> build(int n, const vector<pair<int, int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }   // undirected
    return adj;
}

void print(const vector<int>& a, const char* end = "\n") {
    cout << "[";
    for (size_t i = 0; i < a.size(); i++) cout << (i ? ", " : "") << a[i];
    cout << "]" << end;
}

int main() {
    auto adj = build(8, {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}, {2, 5}, {6, 7}});
    vector<int> parent;
    vector<int> dist = bfs(adj, 0, parent);
    print(dist);
    print(path(parent, 4), " ");
    print(path(parent, 5));
    vector<int> unreachable;
    for (int v = 0; v < 8; v++) if (dist[v] == -1) unreachable.push_back(v);
    print(unreachable);
}

Output: the distances [0, 1, 1, 2, 3, 2, -1, -1], the paths [0, 1, 3, 4] and [0, 2, 5], and [6, 7], the vertices that cannot be reached.

When to use it

  • Shortest paths when every step costs the same: mazes and grids, the fewest moves to solve a puzzle (each state is a vertex), degrees of separation in a social network, the fewest flights.
  • Connected components and flood fill (the paint bucket).
  • Testing whether a graph is bipartite (two-colourable): colour by distance parity.
  • Level-by-level work on trees, web crawling by distance.
  • Not for weighted edges: use Dijkstra.

Common mistakes

  • Marking a vertex as seen when it leaves the queue instead of when it enters: the same vertex can be queued many times, and with weights in mind that is wrong anyway; mark on entry.
  • Using a list with pop(0) in Python as the queue: \(O(V^2)\). Use collections.deque.
  • Using it on weighted graphs: fewest edges is not least total weight.
  • Grids: forgetting to check the bounds or walls before queuing a neighbour.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: BFS from 0

Edges: 0–1, 0–2, 1–3, 2–3, 3–4, 4–5, 2–5, 6–7.

Take from queue New neighbours (distance) Queue after
— start 0 (0) 0
0 1 (1), 2 (1) 1, 2
1 3 (2) 2, 3
2 5 (2) (3 already seen) 3, 5
3 4 (3) 5, 4
5 none (4 already seen) 4
4 none empty

The path to 4 is read backwards from the parents: 4 ← 3 ← 1 ← 0.

The math: why BFS finds shortest paths

Let \(\delta(v)\) be the true fewest-edges distance from the start \(s\).

Claim 1: the queue is sorted by distance and spans at most two levels. At any time, if the queue holds \(v_1, \ldots, v_r\) (front to back), then \(d[v_1] \le d[v_2] \le \cdots \le d[v_r] \le d[v_1] + 1\). Taking \(v_1\) and adding neighbours with distance \(d[v_1] + 1\) at the back keeps this true.

Claim 2: \(d[v] = \delta(v)\) for every reached \(v\). Suppose not, and let \(v\) be a vertex with the smallest \(\delta(v)\) for which \(d[v] > \delta(v)\) (BFS never underestimates, since every \(d\) comes from a real path). Let \(u\) be the vertex before \(v\) on a shortest path, so \(\delta(u) = \delta(v) - 1\) and \(d[u] = \delta(u)\). When \(u\) was taken from the queue, \(v\) was either unseen (then \(d[v] = d[u] + 1 = \delta(v)\), a contradiction) or already seen with, by claim 1, \(d[v] \le d[u] + 1 = \delta(v)\), a contradiction too.

Time. Each vertex enters the queue at most once, and each adjacency list is scanned once when its vertex leaves: \(\sum_v (1 + \deg v) = V + 2E\) for an undirected graph, so \(O(V + E)\).

Watch it step by step

Numbers above vertices are distances. Blue vertices wait in the queue; orange is being explored; purple edges form the shortest-path tree.

Variations and related ideas
  • Multi-source BFS: put several starts in the queue at distance 0 (distance to the nearest fire exit, the nearest shop).
  • 0-1 BFS: for weights 0 and 1, push 0-edges to the front of a deque and 1-edges to the back: \(O(V + E)\).
  • Bidirectional BFS: search from both ends and meet in the middle; for branching factor \(b\) and distance \(d\), about \(2b^{d/2}\) vertices instead of \(b^d\).
  • BFS on implicit graphs: the states of a Rubik's cube or a sliding puzzle are generated on the fly.

See also

References

  • E. F. Moore, "The shortest path through a maze", Proceedings of the International Symposium on the Theory of Switching, Harvard, 1959.
  • T. H. Cormen et al., Introduction to Algorithms, 4th ed., §20.2 (breadth-first search).