Lesson 21.1 · Breadth-First Search

The BFS Template and Shortest Paths

A queue and a visited array. Mark nodes when you add them, process level by level, and the level number is the distance.

14 min

Think of it like this

Dropping a stone into a pond: the ripple reaches everything 1 metre away, then 2 metres, then 3. Whatever the ripple touches first is the closest.

1.The template

Put the start in a queue and mark it visited. Repeat: take the front node, look at its neighbours, and enqueue every one that isn't visited yet, marking it as you enqueue so it can't be added twice.

Process the queue in levels (read size at the start of each level, as in tree level order) or store dist[v] = dist[u] + 1 when you enqueue v. Both give fewest steps. Cost: O(V + E), since every node is enqueued once and every edge examined once (twice if undirected).

Main.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
        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]); }

        int[] dist = new int[n];
        Arrays.fill(dist, -1);                // -1 = not visited
        Deque<Integer> q = new ArrayDeque<>();
        dist[0] = 0;
        q.offer(0);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] != -1) continue;
                dist[v] = dist[u] + 1;        // mark when enqueuing
                q.offer(v);
            }
        }
        System.out.println(Arrays.toString(dist));
    }
}

Output

[0, 1, 1, 2, 3]

▶ Dry run: BFS from node 0edges = [[0,1],[0,2],[1,3],[2,3],[3,4]], start = 0

queue(queue)

dist(map)

0: 0

Step 1/4Start: 0 at distance 0.

Remember

Queue + visited, marked on enqueue.
First visit = shortest path in unweighted graphs.
O(V + E).

Common mistakes

Marking on dequeue (a node can be queued many times).
Using BFS for weighted shortest paths.

Words used in this lesson

BFS: Breadth-first search: explore nodes in order of distance from the start.
Unweighted: Every edge counts as one step.

Command Palette

The BFS Template and Shortest Paths

1.The template