Breadth First Search

BFS explores layer by layer using a queue. $O(V+E)$. Because it reaches every vertex by the fewest possible edges, it gives shortest paths on unweighted graphs — the first time a vertex is dequeued, its distance is final.

Standard BFS

vector<int> dist, par;
 
void bfs(int s) {
    dist.assign(n, -1);
    par.assign(n, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u])
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                par[v] = u;
                q.push(v);
            }
    }
}
 
vector<int> path(int s, int t) {
    if (dist[t] == -1) return {};
    vector<int> p;
    for (int at = t; at != -1; at = par[at]) p.push_back(at);
    reverse(p.begin(), p.end());
    return p;
}

Marking dist[v] when pushing, not when popping, is essential — otherwise a vertex can enter the queue many times and the complexity degrades.

BFS on grids

Grids are implicit graphs. Do not build an adjacency list; use direction vectors.

int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, 1, -1};
// 8 directions: dr[8] = {-1,-1,-1,0,0,1,1,1}, dc[8] = {-1,0,1,-1,1,-1,0,1};
 
int bfsGrid(vector<string>& g, pair<int,int> s, pair<int,int> t) {
    int R = g.size(), C = g[0].size();
    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int,int>> q;
    dist[s.first][s.second] = 0;
    q.push(s);
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        if (make_pair(r, c) == t) return dist[r][c];
        for (int d = 0; d < 4; d++) {
            int rr = r + dr[d], cc = c + dc[d];
            if (rr < 0 || cc < 0 || rr >= R || cc >= C) continue;
            if (g[rr][cc] == '#' || dist[rr][cc] != -1) continue;
            dist[rr][cc] = dist[r][c] + 1;
            q.push({rr, cc});
        }
    }
    return -1;
}

The BFS family

Variant	When	Complexity
Plain BFS	all edges weight 1	$O(V+E)$
Multi-source BFS	distance to the nearest of several sources	$O(V+E)$ — push all sources at distance 0
0-1 BFS	weights in $\{0,1\}$	$O(V+E)$ — deque, push-front on 0
Dial’s algorithm	small integer weights $\le C$	$O(V\cdot C+E)$ — $C+1$ buckets
Bidirectional BFS	one source, one target, huge state space	$O(b^{d/2})$ instead of $O(b^d)$
BFS on a layered graph	state-dependent movement	$O(kV+kE)$
Dijkstra	arbitrary non-negative weights	$O((V+E)\log V)$

Multi-source BFS

Seed the queue with every source at distance 0. One pass then gives, for every cell, the distance to its nearest source — the standard solution to “distance to the nearest 1 in a binary matrix” and to fire/water spreading problems.

Bidirectional BFS

Run BFS from both ends, always expanding the smaller frontier, and stop when they meet. For a branching factor $b$ and answer depth $d$ this turns $b^d$ into $2b^{d/2}$ — the difference between hopeless and instant on puzzle state spaces like the 15-puzzle.

Layered / state BFS

When movement depends on carried state (keys, fuel, parity, moves used mod $k$), make the vertex a pair:

// dist[v][mask] = shortest path to v holding key set `mask`
queue<pair<int,int>> q;

This is the single most common way a “BFS won’t work here” problem turns out to be a BFS after all.

See also: Depth First Search · 0-1 BFS · Shortest Paths