Breadth-First Search (BFS): Shortest Paths, Grids & Code

Drop a stone in a pond and the ripples spread out in rings. Breadth-first search (BFS) explores a graph the same way: from a start vertex it visits everything one edge away, then everything two edges away, and so on outwards. Because it reaches vertices in order of distance, the first route it finds to a vertex is a shortest one. That makes BFS the answer to every "fewest moves" question on an unweighted graph: the shortest way out of a maze, the fewest flights, the fewest single-letter changes from one word to another.

1. The search starts at A, ring 0. Like a stone dropped in a pond, it spreads outwards one ring at a time: a vertex's ring is the number of edges from A.
2. Ring 1 is B and C: every vertex not reached yet that is a neighbour of ring 0.
3. Ring 2 is D and E: every vertex not reached yet that is a neighbour of ring 1. D is a neighbour of both B and C, but joins the ring once.
4. Ring 3 is F: every vertex not reached yet that is a neighbour of ring 2. F is a neighbour of both D and E, but joins the ring once.
5. Ring 4 is G: every vertex not reached yet that is a neighbour of ring 3. Nothing lies beyond it, so the search is over.
6. Every one of the 8 edges joins a ring to the same ring or the next one; none skips a ring. It cannot: when the nearer end leaves the queue, the farther end is reached at most one ring later. So each vertex is first reached along a fewest-edge route.

This lesson assumes you know how a graph is stored; if not, read Graph Data Structure first.

Why trying every route is too slow

Listing every route and keeping the shortest fails because routes multiply: an open 8 × 8 grid has about 7.9 × 10¹¹ simple paths between opposite corners. BFS needs a few hundred steps: each of the 64 cells once, each of the 112 edges from both ends. It never asks "which route is shortest?", only "which cells are 1 step away? Which are 2?", and it settles each cell the first time it reaches it.

The idea: a queue and a seen mark

• Put the start in a first-in, first-out queue, mark it seen and give it distance 0.
• Take the vertex at the front. Give each neighbour not seen yet a mark, a distance one more than the current vertex, and a parent (the current vertex), and add it to the back.
• Repeat until the queue is empty.

The queue keeps the rings in order: every vertex at distance 1 joins it before any vertex at distance 2. Swap it for a stack, which hands back the newest vertex first, and the search dives down one path instead: that is depth-first search.

1. Start at A: its distance is 0, it is marked as seen, and it is the only node in the queue. The queue is what keeps the search in order of distance.
2. Take A off the front (distance 0). Its unseen neighbours B and C are marked at distance 1 and joined the back of the queue.
3. Take B off the front (distance 1). Its unseen neighbour D is marked at distance 2 and joined the back of the queue; A was already seen and is skipped.
4. Take C off the front (distance 1). Its unseen neighbour E is marked at distance 2 and joined the back of the queue; A and D were already seen and are skipped.
5. Take D off the front (distance 2). Its unseen neighbour F is marked at distance 3 and joined the back of the queue; B and C were already seen and are skipped.
6. Take E off the front (distance 2). Every neighbour (C and F) is already marked, so nothing is added.
7. Take F off the front (distance 3). Its unseen neighbour G is marked at distance 4 and joined the back of the queue; D and E were already seen and are skipped.
8. Take G off the front (distance 4). Every neighbour (F) is already marked, so nothing is added.
9. The queue is empty and every node has its shortest distance from A in edges — G is the farthest at 4. The marked edges are the BFS tree: following them back from any node gives a shortest path. Each node and edge was handled once: O(V + E).

Why BFS finds shortest paths

Two facts carry the proof. The queue is always sorted by distance and holds at most two distances at once, k at the front and k + 1 at the back, because taking a k only ever adds k + 1's. And no edge skips a ring, as the first figure showed: when the nearer end of an edge leaves the queue, the farther end is either seen already or labelled one more. So a vertex at true distance k is first reached from one at distance k − 1, and its label is exactly k.

The proof leans on every edge adding exactly 1 to a route's length. Give the edges weights and it breaks:

1. BFS from A puts B and C in the same ring, because each is one edge from A, so it reports A → C: 1 edge, which costs 5.
2. The cheapest route is A → B → C, cost 2, with more edges. BFS counts edges and never looks at weights, so with weights you need Dijkstra's algorithm, which takes vertices in order of total cost.

With weights you need Dijkstra's algorithm, which takes vertices in order of total weight rather than number of edges.

Mark a vertex when you add it

It is tempting to mark a vertex when it leaves the queue, since that is when it is processed. The animation runs both versions side by side.

1. Two versions of BFS, run side by side from A. They differ in one thing: whether a vertex is marked as seen when it joins the queue (top) or only when it is taken out (bottom).
2. Take A: both add B and C. The top version marks them at once; the bottom one waits until they come out.
3. Take B: both add D. The top version marks it at once; the bottom one waits until it comes out.
4. Take C: the top version sees D already marked and adds only E. In the bottom one D is still waiting unmarked in the queue, so it goes in a second time.
5. Take D: the bottom queue still holds a stale copy, which must be skipped when it comes out or D's neighbours are scanned twice. Every early arrival adds a copy: up to about 2E entries instead of V.

Marking on the way in costs nothing and is safe, because a vertex's distance is already final the first time it is discovered.

Recovering the path

Distances answer "how far?". To answer "which way?", follow the parent links back from the target and reverse what you collect.

1. During the search each vertex records the parent it was discovered from, one step nearer A. Drawn as arrows, the parent links form the BFS tree; the dashed edges were never used to discover anything.
2. To find a shortest path to G, start at G and follow its parent link to F, one ring nearer A.
3. F's parent is D, at distance 2. Each link drops exactly one ring, so the walk takes exactly 4 steps.
4. D's parent is B. The chain only ever moves nearer to A, so it can never loop.
5. B's parent is A, the start, which has no parent of its own: the walk is over after 4 links.
6. The walk reaches A, so the path read backwards and reversed is A → B → D → F → G: 4 edges, matching dist[G]. A → C → E → F → G is just as short (3 shortest paths in all); BFS returns the one its neighbour order found first.

The code

The graph gains an eighth vertex, H, with no edges: its distance stays −1, the value that also means "not seen". Python's collections.deque takes from the front in O(1), unlike list.pop(0); JavaScript's shift() can cost O(n) too, so that program keeps a head index instead.

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

const string NAMES = "ABCDEFGH";

// Breadth-first search from start: each vertex's distance in edges (-1 if
// unreachable), the vertex it was discovered from, and the visiting order.
void bfs(const vector<vector<int>>& adj, int start, vector<int>& dist, vector<int>& parent, vector<int>& order) {
    dist.assign(adj.size(), -1);
    parent.assign(adj.size(), -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;  // mark on enqueue: v joins the queue once
                parent[v] = u;
                q.push(v);
            }
        }
    }
}

// Walks the parent links back from target, then reverses them.
vector<int> pathTo(const vector<int>& parent, int target) {
    vector<int> path;
    for (int v = target; v != -1; v = parent[v]) path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    // A-B, A-C, B-D, C-D, C-E, D-F, E-F, F-G; H has no edges at all.
    int n = 8;
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}, {5, 6}};
    vector<vector<int>> adj(n);
    for (const vector<int>& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    vector<int> dist, parent, order;
    bfs(adj, 0, dist, parent, order);
    cout << "Visit order:";
    for (int v : order) cout << " " << NAMES[v];
    cout << "\nDistances from A:";
    for (int v = 0; v < n; v++) cout << " " << NAMES[v] << "=" << dist[v];
    cout << "\n";
    for (int target : {6, 7}) {
        if (dist[target] == -1) {
            cout << "No path from A to " << NAMES[target] << "\n";
        } else {
            vector<int> path = pathTo(parent, target);
            cout << "Shortest path A to " << NAMES[target] << ":";
            for (size_t i = 0; i < path.size(); i++) cout << (i > 0 ? " -> " : " ") << NAMES[path[i]];
            cout << " (" << dist[target] << " edges)\n";
        }
    }
    return 0;
}

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

public class Main {
    static final String NAMES = "ABCDEFGH";
    static int[] dist, parent;
    static List<Integer> order = new ArrayList<>();

    // Breadth-first search from start: each vertex's distance in edges (-1 if
    // unreachable), the vertex it was discovered from, and the visiting order.
    static void bfs(List<List<Integer>> adj, int start) {
        dist = new int[adj.size()];
        parent = new int[adj.size()];
        Arrays.fill(dist, -1);
        Arrays.fill(parent, -1);
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        dist[start] = 0;
        queue.add(start);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order.add(u);
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1; // mark on enqueue: v joins the queue once
                    parent[v] = u;
                    queue.add(v);
                }
            }
        }
    }

    // Walks the parent links back from target, then reverses them.
    static List<Integer> pathTo(int target) {
        List<Integer> path = new ArrayList<>();
        for (int v = target; v != -1; v = parent[v]) path.add(v);
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        // A-B, A-C, B-D, C-D, C-E, D-F, E-F, F-G; H has no edges at all.
        int n = 8;
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 5}, {4, 5}, {5, 6}};
        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]);
        }

        bfs(adj, 0);
        StringBuilder line = new StringBuilder("Visit order:");
        for (int v : order) line.append(" ").append(NAMES.charAt(v));
        System.out.println(line);
        line = new StringBuilder("Distances from A:");
        for (int v = 0; v < n; v++) line.append(" ").append(NAMES.charAt(v)).append("=").append(dist[v]);
        System.out.println(line);
        for (int target : new int[] {6, 7}) {
            if (dist[target] == -1) {
                System.out.println("No path from A to " + NAMES.charAt(target));
            } else {
                List<Integer> path = pathTo(target);
                line = new StringBuilder("Shortest path A to " + NAMES.charAt(target) + ":");
                for (int i = 0; i < path.size(); i++) line.append(i > 0 ? " -> " : " ").append(NAMES.charAt(path.get(i)));
                System.out.println(line + " (" + dist[target] + " edges)");
            }
        }
    }
}

from collections import deque

NAMES = "ABCDEFGH"


def bfs(adj, start):
    """Breadth-first search from start: each vertex's distance in edges (-1 if
    unreachable), the vertex it was discovered from, and the visiting order."""
    dist = [-1] * len(adj)
    parent = [-1] * len(adj)
    order = []
    queue = deque([start])
    dist[start] = 0
    while queue:
        u = queue.popleft()  # O(1), unlike list.pop(0)
        order.append(u)
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1  # mark on enqueue: v joins the queue once
                parent[v] = u
                queue.append(v)
    return dist, parent, order


def path_to(parent, target):
    """Walk the parent links back from target, then reverse them."""
    path = []
    v = target
    while v != -1:
        path.append(v)
        v = parent[v]
    return path[::-1]


# A-B, A-C, B-D, C-D, C-E, D-F, E-F, F-G; H has no edges at all.
n = 8
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5), (5, 6)]
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

dist, parent, order = bfs(adj, 0)
print("Visit order:", " ".join(NAMES[v] for v in order))
print("Distances from A:", " ".join(f"{NAMES[v]}={dist[v]}" for v in range(n)))
for target in (6, 7):
    if dist[target] == -1:
        print(f"No path from A to {NAMES[target]}")
    else:
        route = " -> ".join(NAMES[v] for v in path_to(parent, target))
        print(f"Shortest path A to {NAMES[target]}: {route} ({dist[target]} edges)")

const NAMES = "ABCDEFGH";

// Breadth-first search from start: each vertex's distance in edges (-1 if
// unreachable), the vertex it was discovered from, and the visiting order.
function bfs(adj, start) {
  const dist = new Array(adj.length).fill(-1);
  const parent = new Array(adj.length).fill(-1);
  const order = [];
  const queue = [start];
  let head = 0; // queue[head] is the front; shift() can cost O(n) per call
  dist[start] = 0;
  while (head < queue.length) {
    const u = queue[head++];
    order.push(u);
    for (const v of adj[u]) {
      if (dist[v] === -1) {
        dist[v] = dist[u] + 1; // mark on enqueue: v joins the queue once
        parent[v] = u;
        queue.push(v);
      }
    }
  }
  return { dist, parent, order };
}

// Walks the parent links back from target, then reverses them.
function pathTo(parent, target) {
  const path = [];
  for (let v = target; v !== -1; v = parent[v]) path.push(v);
  return path.reverse();
}

// A-B, A-C, B-D, C-D, C-E, D-F, E-F, F-G; H has no edges at all.
const n = 8;
const edges = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 4], [3, 5], [4, 5], [5, 6]];
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
  adj[u].push(v);
  adj[v].push(u);
}

const { dist, parent, order } = bfs(adj, 0);
console.log(`Visit order: ${order.map((v) => NAMES[v]).join(" ")}`);
console.log(`Distances from A: ${dist.map((d, v) => `${NAMES[v]}=${d}`).join(" ")}`);
for (const target of [6, 7]) {
  if (dist[target] === -1) {
    console.log(`No path from A to ${NAMES[target]}`);
  } else {
    const route = pathTo(parent, target).map((v) => NAMES[v]).join(" -> ");
    console.log(`Shortest path A to ${NAMES[target]}: ${route} (${dist[target]} edges)`);
  }
}

Visit order: A B C D E F G
Distances from A: A=0 B=1 C=1 D=2 E=2 F=3 G=4 H=-1
Shortest path A to G: A -> B -> D -> F -> G (4 edges)
No path from A to H

BFS on a grid: the shortest way through a maze

On a grid the loop is the same, with a cell (r, c) in place of a vertex and four direction offsets in place of the adjacency list. A 2D dist array does double duty: −1 means not seen, anything else is the distance.

1. S is distance 0 and the only cell in the queue. Walls never enter it, so the search can only flow through open cells, one step in four directions at a time.
2. Distances 1 to 3: every open cell within 3 steps is numbered, each when it is first reached, and the number never changes. The queue always holds the frontier, the cells numbered last.
3. Distances 4 to 6: the wave has split around the walls and moves on 3 fronts at once, (1, 3), (3, 3) and (4, 2). The queue takes them in turn, so no front gets ahead.
4. Distances 7 to 9: the front from (4, 2) ran into a dead end and stopped; the queue simply has nothing more from it. Two fronts are still moving, at (0, 5) and (2, 5).
5. Distances 10 to 11: both fronts have reached the right-hand column. (0, 7) is 4 steps from E, (2, 7) only 2, so the lower front will arrive first.
6. Distance 12: the fronts are at (1, 7) and (3, 7), and one of them is beside E. Every cell 12 steps away is reached before any cell 13 steps away.
7. E is numbered 13. The route along the top row would have taken 15 steps, but BFS reaches every cell at distance 13 before any at 14, so the first number E gets is the shortest. The search stops here.
8. Following the parent links back from E, one cell nearer S each time, marks the route: 13 steps. Each open cell entered the queue at most once, so the whole search was O(rows × columns).

The program prints the length and draws the route with stars. Each parent is stored as one number, r × cols + c, and the search stops as soon as E leaves the queue, since its distance is final by then. The bounds check comes before the maze is read, because maze[-1][c] is undefined behaviour in C++, an exception in Java and JavaScript, and a silent read of the last row in Python.

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

const int DR[4] = {-1, 1, 0, 0};  // up, down, left, right
const int DC[4] = {0, 0, -1, 1};

int main() {
    vector<string> maze = {
        "S.#.....",
        ".##.###.",
        "....#...",
        ".##...#.",
        "...#.#.E",
    };
    int rows = maze.size(), cols = maze[0].size();
    int sr = 0, sc = 0, er = 0, ec = 0;
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (maze[r][c] == 'S') sr = r, sc = c;
            if (maze[r][c] == 'E') er = r, ec = c;
        }

    vector<vector<int>> dist(rows, vector<int>(cols, -1));    // -1: not seen yet
    vector<vector<int>> parent(rows, vector<int>(cols, -1));  // previous cell as r * cols + c
    queue<pair<int, int>> q;
    dist[sr][sc] = 0;
    q.push({sr, sc});
    while (!q.empty()) {
        int r = q.front().first, c = q.front().second;
        q.pop();
        if (r == er && c == ec) break;  // the exit's distance is final: stop here
        for (int d = 0; d < 4; d++) {
            int nr = r + DR[d], nc = c + DC[d];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;  // bounds first
            if (maze[nr][nc] == '#' || dist[nr][nc] != -1) continue;     // a wall, or seen
            dist[nr][nc] = dist[r][c] + 1;
            parent[nr][nc] = r * cols + c;
            q.push({nr, nc});
        }
    }

    if (dist[er][ec] == -1) {
        cout << "No way out\n";
        return 0;
    }
    cout << "Shortest path: " << dist[er][ec] << " steps\n";
    for (int at = parent[er][ec]; at != sr * cols + sc; at = parent[at / cols][at % cols])
        maze[at / cols][at % cols] = '*';  // walk back from the exit, marking the route
    for (const string& row : maze) cout << row << "\n";
    return 0;
}

import java.util.ArrayDeque;
import java.util.Arrays;

public class Main {
    static final int[] DR = {-1, 1, 0, 0}; // up, down, left, right
    static final int[] DC = {0, 0, -1, 1};

    public static void main(String[] args) {
        String[] lines = {
            "S.#.....",
            ".##.###.",
            "....#...",
            ".##...#.",
            "...#.#.E",
        };
        int rows = lines.length, cols = lines[0].length();
        char[][] maze = new char[rows][];
        int sr = 0, sc = 0, er = 0, ec = 0;
        for (int r = 0; r < rows; r++) {
            maze[r] = lines[r].toCharArray();
            for (int c = 0; c < cols; c++) {
                if (maze[r][c] == 'S') { sr = r; sc = c; }
                if (maze[r][c] == 'E') { er = r; ec = c; }
            }
        }

        int[][] dist = new int[rows][cols];   // -1: not seen yet
        int[][] parent = new int[rows][cols]; // previous cell as r * cols + c
        for (int[] row : dist) Arrays.fill(row, -1);
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        dist[sr][sc] = 0;
        queue.add(new int[] {sr, sc});
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];
            if (r == er && c == ec) break; // the exit's distance is final: stop here
            for (int d = 0; d < 4; d++) {
                int nr = r + DR[d], nc = c + DC[d];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // bounds first
                if (maze[nr][nc] == '#' || dist[nr][nc] != -1) continue;    // a wall, or seen
                dist[nr][nc] = dist[r][c] + 1;
                parent[nr][nc] = r * cols + c;
                queue.add(new int[] {nr, nc});
            }
        }

        if (dist[er][ec] == -1) {
            System.out.println("No way out");
            return;
        }
        System.out.println("Shortest path: " + dist[er][ec] + " steps");
        for (int at = parent[er][ec]; at != sr * cols + sc; at = parent[at / cols][at % cols])
            maze[at / cols][at % cols] = '*'; // walk back from the exit, marking the route
        for (char[] row : maze) System.out.println(new String(row));
    }
}

from collections import deque

DR = [-1, 1, 0, 0]  # up, down, left, right
DC = [0, 0, -1, 1]

maze = [list(row) for row in [
    "S.#.....",
    ".##.###.",
    "....#...",
    ".##...#.",
    "...#.#.E",
]]
rows, cols = len(maze), len(maze[0])
for r in range(rows):
    for c in range(cols):
        if maze[r][c] == "S":
            sr, sc = r, c
        if maze[r][c] == "E":
            er, ec = r, c

dist = [[-1] * cols for _ in range(rows)]    # -1: not seen yet
parent = [[-1] * cols for _ in range(rows)]  # previous cell as r * cols + c
queue = deque([(sr, sc)])
dist[sr][sc] = 0
while queue:
    r, c = queue.popleft()
    if r == er and c == ec:
        break  # the exit's distance is final: stop here
    for d in range(4):
        nr, nc = r + DR[d], c + DC[d]
        if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
            continue  # bounds first
        if maze[nr][nc] == "#" or dist[nr][nc] != -1:
            continue  # a wall, or seen
        dist[nr][nc] = dist[r][c] + 1
        parent[nr][nc] = r * cols + c
        queue.append((nr, nc))

if dist[er][ec] == -1:
    print("No way out")
else:
    print(f"Shortest path: {dist[er][ec]} steps")
    at = parent[er][ec]
    while at != sr * cols + sc:  # walk back from the exit, marking the route
        r, c = divmod(at, cols)
        maze[r][c] = "*"
        at = parent[r][c]
    for row in maze:
        print("".join(row))

const DR = [-1, 1, 0, 0]; // up, down, left, right
const DC = [0, 0, -1, 1];

const maze = [
  "S.#.....",
  ".##.###.",
  "....#...",
  ".##...#.",
  "...#.#.E",
].map((row) => row.split(""));
const rows = maze.length;
const cols = maze[0].length;
let sr = 0, sc = 0, er = 0, ec = 0;
for (let r = 0; r < rows; r++) {
  for (let c = 0; c < cols; c++) {
    if (maze[r][c] === "S") [sr, sc] = [r, c];
    if (maze[r][c] === "E") [er, ec] = [r, c];
  }
}

const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1)); // -1: not seen yet
const parent = Array.from({ length: rows }, () => new Array(cols).fill(-1)); // previous cell as r * cols + c
const queue = [[sr, sc]];
let head = 0;
dist[sr][sc] = 0;
while (head < queue.length) {
  const [r, c] = queue[head++];
  if (r === er && c === ec) break; // the exit's distance is final: stop here
  for (let d = 0; d < 4; d++) {
    const nr = r + DR[d];
    const nc = c + DC[d];
    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // bounds first
    if (maze[nr][nc] === "#" || dist[nr][nc] !== -1) continue; // a wall, or seen
    dist[nr][nc] = dist[r][c] + 1;
    parent[nr][nc] = r * cols + c;
    queue.push([nr, nc]);
  }
}

if (dist[er][ec] === -1) {
  console.log("No way out");
} else {
  console.log(`Shortest path: ${dist[er][ec]} steps`);
  for (let at = parent[er][ec]; at !== sr * cols + sc; at = parent[Math.floor(at / cols)][at % cols]) {
    maze[Math.floor(at / cols)][at % cols] = "*"; // walk back from the exit, marking the route
  }
  for (const row of maze) console.log(row.join(""));
}

Shortest path: 13 steps
S.#.....
*##.###.
****#***
.##***#*
...#.#.E

Nearest Exit from Entrance in Maze is this program with "any open border cell" as the exit.

Multi-source BFS: many starts at once

In Rotting Oranges every rotten orange rots its fresh neighbours each minute. A separate BFS from each of k sources would cost O(k × R × C). Instead, put all the sources in the queue at distance 0 before the loop starts: the queue is then in order of distance from the nearest source, and one pass costs O(R × C). It is one BFS from an imaginary vertex joined to every source, with its first step skipped.

1. 2 is rotten, 1 fresh, 0 empty. Both rotten oranges, (0, 0) and (2, 4), go into the queue before the loop starts, all at minute 0, so the rot spreads from both at once; 10 oranges are fresh.
2. Minute 1: the queue held 2 cells, and taking exactly that many is one whole level. Their fresh neighbours, (1, 0), (0, 1), (1, 4) and (2, 3), rot together and wait in the queue for minute 2.
3. Minute 2: the queue held 4 rotten oranges, so exactly 4 are taken — one whole level. Their fresh neighbours (1, 1), (0, 2), (0, 4), (1, 3) and (2, 2) rot and join the queue for the next minute.
4. Minute 3: (2, 1) rots and no fresh orange is left, so the answer is 3. An orange walled off by empty cells would still be fresh when the queue ran dry, and the answer would be −1.

To count minutes rather than cells, take exactly as many cells as the queue held when the minute began. Count the fresh oranges first, so that one nobody can reach shows up as −1. 01 Matrix is the same idea with every 0 as a source.

Other shapes of BFS

• State graphs. Open the Lock and Word Ladder generate each configuration's neighbours as they go and keep seen states in a hash set.
• Level-order traversal of a binary tree, with no seen set, since each node has one parent.
• Bipartite check. Colour each new vertex opposite to its parent; an edge between two of the same colour means no split exists: Is Graph Bipartite?.
• 0-1 BFS. When edges weigh 0 or 1, a double-ended queue puts 0-edges at the front and 1-edges at the back: Minimum Obstacle Removal to Reach Corner.

Time and space complexity

Each vertex enters the queue once, because it is marked on the way in, and its adjacency list is read once when it leaves: O(V + E).

How to recognise a BFS problem

• "Minimum number of steps, moves or changes", "shortest path" or "nearest", with every move costing the same.
• A grid with moves in four or eight directions and a question about distance.
• Something that spreads at the same time from several places: multi-source BFS.
• Configurations and moves between them: BFS over a state graph.

If moves have different costs, use Dijkstra's algorithm. If the question is only whether something can be reached, depth-first search does as well.

Common mistakes

• Marking on the way out. A vertex can then be added, and processed, many times.
• A slow queue. list.pop(0) and shift() can cost O(n) per call.
• Reading the grid before checking bounds.
• BFS on a weighted graph. It returns the fewest edges, not the cheapest route.
• Forgetting the start. Mark it before the loop, and handle a start that is the target and a target never reached.

Practice in this order

1. Flood Fill: BFS on a grid, and the trap when the new colour equals the old.
2. Find if Path Exists in Graph: the plain loop on an adjacency list.
3. Keys and Rooms: reachability on a directed graph given as lists.
4. Nearest Exit from Entrance in Maze: the maze program, exits on the border.
5. Shortest Path in Binary Matrix: grid BFS with eight directions.
6. Rotting Oranges: multi-source BFS counted in levels.
7. 01 Matrix: multi-source BFS from every zero.
8. Open the Lock: a state graph with forbidden states.
9. Word Ladder: a state graph whose edges you generate efficiently.

The breadth-first search problem list has every BFS problem in the catalogue, easiest first. Next comes the other way to walk a graph, deep before wide: depth-first search.