Breadth-first search

coreCommon atGoogleMetaAmazonAnthropicRead firstGraph representationQueues and dequesPractise in the Sandbox →

Breadth-first search (BFS) visits nodes in order of distance from the start: all nodes 1 edge away, then all 2 edges away, and so on. A FIFO queue enforces that order. When every edge costs the same, the first time BFS reaches a node is along a shortest path. It runs in O(V + E).

The idea in plain words

Drop a stone in a pond. The ripple reaches everything 1 metre away before anything 2 metres away. BFS is that ripple on a graph.

The trick is the queue. You take the oldest item from the front and add newly found neighbours to the back. So everything at distance d sits in the queue ahead of everything at distance d + 1. That ordering is the whole proof that BFS finds shortest paths:

• Invariant: the queue holds at most two distances, d at the front and d + 1 at the back.
• Consequence: when a node is first discovered from a node at distance d, no shorter route exists, because every node at distance < d was already processed.

Two words you’ll hear: the frontier is the set of discovered-but-unprocessed nodes (the queue). A layer or level is all nodes at the same distance.

See it

Click cells to draw walls, move the source S or the target E, then step through. Numbers are distances. Switch to multi-source to put several S cells in the queue at once and watch one combined ripple.

BFS ripples out one layer at a time

click to edit, then step

MazeOpen room3 sourcesClear walls

S

E

queue (front → back), 1 cells

(0,0) d=0

dequeued0

queue1

dequeued now / final routejust discoveredin the queue (frontier)finished

Put the source in the queue with distance 0 and mark it seen. Marking on enqueue (not on dequeue) keeps each cell in the queue at most once.

↺◀▶ Play▶1 / 44

Things to try:

• Open room: the frontier is a diamond, because grid distance with 4-way moves is Manhattan distance.
• Seal off E with walls: the queue empties and BFS reports it unreachable.
• Multi-source: each cell ends up labelled with its distance to the nearest source. No extra work: it’s still one BFS.

When to reach for it

The problem says…	Why BFS fits
“fewest moves / steps / hops / transformations”	Unweighted shortest path is exactly what BFS computes.
a grid where each move costs 1	A grid is a graph: cells are nodes, adjacent open cells are edges.
“minimum number of rounds to reach the target”	Each round is one BFS layer.
“distance from every cell to the nearest X”	Multi-source BFS from all X at once, not one BFS per cell.
“level order”, “nodes at depth k” in a tree	A tree is a graph; BFS by layers gives each level.
“is B reachable from A?”	BFS or DFS both work; BFS also gives the distance for free.

Weights break plain BFS

If edges have different costs, the fewest-edges path is not the cheapest. Use Dijkstra for non-negative weights, or 0-1 BFS when weights are only 0 and 1.

How it works

1. Put the source in the queue, set its distance to 0, and mark it seen.
2. Pop the node at the front of the queue.
3. For each neighbour not yet seen: mark it seen, set dist = dist[u] + 1, record parent = u, push it on the back.
4. Repeat until the queue is empty (or you just discovered the target). Rebuild a path by following parent from the target back to the source.

Python

bfs + path_to.py

from collections import deque


def bfs(adj: dict[str, list[str]], source: str) -> tuple[dict[str, int], dict[str, str]]:
    """Fewest-edges distance and BFS-tree parent for every node reachable from source."""
    dist = {source: 0}
    parent: dict[str, str] = {}
    queue = deque([source])              # 1. seed the queue with the source
    while queue:
        u = queue.popleft()              # 2. FIFO: nearest unfinished node first
        for v in adj.get(u, []):
            if v not in dist:            # 3. mark on enqueue, so v enters the queue once
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)
    return dist, parent


def path_to(parent: dict[str, str], source: str, target: str) -> list[str]:
    """Walk parent pointers back from target (4. rebuild the route)."""
    if target != source and target not in parent:
        return []
    path = [target]
    while path[-1] != source:
        path.append(parent[path[-1]])
    return path[::-1]


if __name__ == "__main__":
    g = {"a": ["b", "c"], "b": ["d"], "c": ["d", "e"], "d": ["f"], "e": ["f"], "f": []}
    dist, parent = bfs(g, "a")
    assert dist == {"a": 0, "b": 1, "c": 1, "d": 2, "e": 2, "f": 3}
    assert path_to(parent, "a", "f") == ["a", "b", "d", "f"]
    assert path_to(parent, "a", "z") == []
    assert path_to(parent, "a", "a") == ["a"]
    print("ok")

TypeScript

bfs + path_to.ts

import assert from "node:assert/strict";

/** Fewest-edges distance and BFS-tree parent for every node reachable from source. */
export function bfs(adj: Map<string, string[]>, source: string) {
  const dist = new Map<string, number>([[source, 0]]);
  const parent = new Map<string, string>();
  const queue: string[] = [source]; // 1. seed the queue with the source
  // An index instead of shift(): Array.shift is O(n) in JS, which would make BFS O(V^2).
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head]; // 2. FIFO: nearest unfinished node first
    for (const v of adj.get(u) ?? []) {
      if (!dist.has(v)) { // 3. mark on enqueue, so v enters the queue once
        dist.set(v, dist.get(u)! + 1);
        parent.set(v, u);
        queue.push(v);
      }
    }
  }
  return { dist, parent };
}

/** Walk parent pointers back from target (4. rebuild the route). */
export function pathTo(parent: Map<string, string>, source: string, target: string): string[] {
  if (target !== source && !parent.has(target)) return [];
  const path = [target];
  while (path[path.length - 1] !== source) path.push(parent.get(path[path.length - 1])!);
  return path.reverse();
}

const g = new Map(Object.entries({ a: ["b", "c"], b: ["d"], c: ["d", "e"], d: ["f"], e: ["f"], f: [] }));
const { dist, parent } = bfs(g, "a");
assert.deepEqual(Object.fromEntries(dist), { a: 0, b: 1, c: 1, d: 2, e: 2, f: 3 });
assert.deepEqual(pathTo(parent, "a", "f"), ["a", "b", "d", "f"]);
assert.deepEqual(pathTo(parent, "a", "z"), []);
assert.deepEqual(pathTo(parent, "a", "a"), ["a"]);
console.log("ok");

C#

bfs + path_to.cs

var g = new Dictionary<string, List<string>>
{
    ["a"] = ["b", "c"], ["b"] = ["d"], ["c"] = ["d", "e"], ["d"] = ["f"], ["e"] = ["f"], ["f"] = [],
};
var (dist, parent) = Bfs(g, "a");
if (dist["f"] != 3 || dist["d"] != 2 || dist.Count != 6) throw new Exception("bad distances");
if (string.Join(",", PathTo(parent, "a", "f")) != "a,b,d,f") throw new Exception("bad path");
if (PathTo(parent, "a", "z").Count != 0) throw new Exception("z is unreachable");
Console.WriteLine("ok");

// Fewest-edges distance and BFS-tree parent for every node reachable from source.
static (Dictionary<string, int>, Dictionary<string, string>) Bfs(Dictionary<string, List<string>> adj, string source)
{
    var dist = new Dictionary<string, int> { [source] = 0 };
    var parent = new Dictionary<string, string>();
    var queue = new Queue<string>([source]);          // 1. seed the queue with the source
    while (queue.Count > 0)
    {
        var u = queue.Dequeue();                       // 2. FIFO: nearest unfinished node first
        foreach (var v in adj.GetValueOrDefault(u, []))
        {
            if (dist.ContainsKey(v)) continue;         // 3. mark on enqueue, so v enters once
            dist[v] = dist[u] + 1;
            parent[v] = u;
            queue.Enqueue(v);
        }
    }
    return (dist, parent);
}

// Walk parent pointers back from target (4. rebuild the route).
static List<string> PathTo(Dictionary<string, string> parent, string source, string target)
{
    if (target != source && !parent.ContainsKey(target)) return [];
    var path = new List<string> { target };
    while (path[^1] != source) path.Add(parent[path[^1]]);
    path.Reverse();
    return path;
}

Mark on enqueue, not on dequeue

If you only mark a node when you pop it, the same node can be pushed many times by different neighbours before it’s popped. The result is still correct, but the queue can grow to O(E) and you do redundant work. Marking at push time guarantees each node enters the queue once.

Level by level, and many sources

When you need “how many rounds”, process the queue one whole layer at a time. Seeding the first layer with several sources gives multi-source BFS: the distance each node gets is to its nearest source, because the rings from all sources grow at the same speed.

Python

layers (multi-source).py

def layers(adj: dict[int, list[int]], sources: list[int]) -> list[list[int]]:
    """Group nodes by distance to the NEAREST source (multi-source BFS, level by level)."""
    seen = set(sources)
    frontier = list(dict.fromkeys(sources))   # 1. every source starts at distance 0
    out: list[list[int]] = []
    while frontier:
        out.append(frontier)                  # 2. the whole frontier is one distance layer
        nxt: list[int] = []
        for u in frontier:
            for v in adj.get(u, []):
                if v not in seen:             # 3. first time reached = nearest source wins
                    seen.add(v)
                    nxt.append(v)
        frontier = nxt                        # 4. advance one ring outward
    return out


if __name__ == "__main__":
    # A path 0-1-2-3-4-5-6 with sources at both ends: they meet in the middle.
    path = {i: [j for j in (i - 1, i + 1) if 0 <= j <= 6] for i in range(7)}
    assert layers(path, [0, 6]) == [[0, 6], [1, 5], [2, 4], [3]]
    assert layers(path, [3]) == [[3], [2, 4], [1, 5], [0, 6]]
    assert layers({}, []) == []
    print("ok")

TypeScript

layers (multi-source).ts

import assert from "node:assert/strict";

/** Group nodes by distance to the NEAREST source (multi-source BFS, level by level). */
export function layers(adj: Map<number, number[]>, sources: number[]): number[][] {
  const seen = new Set(sources);
  let frontier = [...seen]; // 1. every source starts at distance 0
  const out: number[][] = [];
  while (frontier.length > 0) {
    out.push(frontier); // 2. the whole frontier is one distance layer
    const next: number[] = [];
    for (const u of frontier) {
      for (const v of adj.get(u) ?? []) {
        if (!seen.has(v)) { // 3. first time reached = nearest source wins
          seen.add(v);
          next.push(v);
        }
      }
    }
    frontier = next; // 4. advance one ring outward
  }
  return out;
}

// A path 0-1-2-3-4-5-6 with sources at both ends: they meet in the middle.
const path = new Map<number, number[]>();
for (let i = 0; i <= 6; i++) path.set(i, [i - 1, i + 1].filter((j) => j >= 0 && j <= 6));
assert.deepEqual(layers(path, [0, 6]), [[0, 6], [1, 5], [2, 4], [3]]);
assert.deepEqual(layers(path, [3]), [[3], [2, 4], [1, 5], [0, 6]]);
assert.deepEqual(layers(new Map(), []), []);
console.log("ok");

C#

layers (multi-source).cs

// A path 0-1-2-3-4-5-6 with sources at both ends: they meet in the middle.
var path = new Dictionary<int, List<int>>();
for (int i = 0; i <= 6; i++) path[i] = new[] { i - 1, i + 1 }.Where(j => j is >= 0 and <= 6).ToList();
string Show(List<List<int>> ls) => string.Join(" | ", ls.Select(l => string.Join(",", l)));
if (Show(Layers(path, [0, 6])) != "0,6 | 1,5 | 2,4 | 3") throw new Exception("two sources");
if (Show(Layers(path, [3])) != "3 | 2,4 | 1,5 | 0,6") throw new Exception("one source");
if (Layers([], []).Count != 0) throw new Exception("empty");
Console.WriteLine("ok");

// Group nodes by distance to the NEAREST source (multi-source BFS, level by level).
static List<List<int>> Layers(Dictionary<int, List<int>> adj, List<int> sources)
{
    var seen = new HashSet<int>(sources);
    var frontier = seen.ToList();                 // 1. every source starts at distance 0
    var output = new List<List<int>>();
    while (frontier.Count > 0)
    {
        output.Add(frontier);                     // 2. the whole frontier is one distance layer
        var next = new List<int>();
        foreach (var u in frontier)
            foreach (var v in adj.GetValueOrDefault(u, []))
                if (seen.Add(v)) next.Add(v);     // 3. first time reached = nearest source wins
        frontier = next;                          // 4. advance one ring outward
    }
    return output;
}

What it costs

	Time	Extra space
Adjacency list, V nodes, E edges	O(V + E): each node is dequeued once, each edge looked at once (twice if undirected)	O(V) for dist, parent, queue
Grid with R rows and C columns, 4-way moves	O(R·C): V = R·C and E ≤ 4·R·C	O(R·C)
Adjacency matrix	O(V²): scanning a row costs V even for few neighbours	O(V)
Multi-source with k sources	Still O(V + E), not k times that	O(V)

The queue can hold a whole layer at once. On a wide-open grid that’s about the length of the diamond’s edge, O(R + C). In a “star” graph it’s all V − 1 leaves. That memory peak is the main practical difference from DFS, whose stack is as deep as the longest path.

Variations you’ll meet

• Bidirectional BFS. Search from both ends and stop when the frontiers meet. With branching factor b and distance d, that’s about 2·b^(d/2) nodes instead of b^d. Useful for word-transformation style puzzles with huge implicit graphs.
• 0-1 BFS. Weights of 0 or 1 only: use a deque, push 0-edges to the front and 1-edges to the back. O(V + E). See shortest paths.
• BFS over states. When “where am I” isn’t enough (you also carry keys, a remaining budget, a direction), the node is a tuple. See search over states.
• Implicit graphs. You never build the adjacency list. Generate neighbours on the fly: the 4 grid moves, or every one-letter change of a word.
• Counting shortest paths. Keep ways[v]; when you reach v from u with dist[v] == dist[u] + 1, add ways[u].

Pitfalls

• list.pop(0) in Python or array.shift() in JS are O(n) each. Use collections.deque, or a head index in JS. .NET’s Queue<T> is fine.
• Marking too late (see the tip above): duplicates in the queue, sometimes TLE.
• Forgetting bounds or walls in grid neighbours. Check 0 <= r < R and 0 <= c < C before indexing.
• Mutating the input grid as your visited set is fast but surprising. Say so if you do it, or use a separate seen.
• Off-by-one in “minutes” or “rounds”. Is the start round 0 or 1? Does the answer count the last layer that changed anything? Decide out loud.
• Using BFS on weighted edges. It returns the fewest edges, not the lowest cost.

In the interview

• Ask: weighted or unweighted? 4-way or 8-way moves? Can the start equal the target? What if the target is unreachable: -1, None, an exception?
• Say the invariant: “The queue is sorted by distance, at most two values, so the first time I see a node is its shortest distance.”
• State complexity as O(V + E), and for a grid, O(R·C).
• Expected follow-ups: return the actual path (parent pointers), handle many sources, add weights (Dijkstra), add a constraint like “you may break k walls” (state-space BFS), or make the grid huge (bidirectional, or A* with a heuristic).

Check yourself

Check yourself

pick one

You run BFS on a grid but only mark a cell as seen when you pop it from the queue. What goes wrong?

ADistances can come out wrongBNothing is wrong, but a cell can be pushed several times, wasting time and memoryCBFS turns into DFSDIt no longer terminates

Check yourself

pick one

You need each cell's distance to its nearest exit, and there are k exits in an R×C grid. What's the cheapest correct approach?

ARun BFS from every cell: O((R·C)²)BRun BFS from every exit and take the minimum: O(k·R·C)COne BFS with all exits in the queue at distance 0: O(R·C)DDijkstra from every exit

Check yourself

pick one

Why does BFS give shortest paths only when all edges have equal weight?

ABecause the queue is processed in order of number of edges, not total costBBecause BFS cannot handle cyclesCBecause weighted graphs need recursion

Practice on your own

These are classic textbook exercises, not gym questions:

• Minimum knight moves from one square to another on an 8×8 board.
• Fill every empty cell with its distance to the nearest gate (walls and gates).
• Shortest path in a binary matrix with 8-directional moves.
• Check whether an undirected graph is bipartite by 2-colouring it layer by layer.
• Print a binary tree level by level, one line per level.

Go deeper

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), “Elementary Graph Algorithms”, section on breadth-first search: the proof that BFS distances are shortest.
• cp-algorithms: Breadth-first search, with applications like bipartite checks and shortest cycles.
• Sedgewick and Wayne, Algorithms 4.1: Undirected graphs, BreadthFirstPaths.
• Red Blob Games: Introduction to A*, an interactive walk from BFS to Dijkstra to A*.

Related

Depth-first searchThe stack-based sibling: reachability, components, cycles, ordering.

Shortest pathsDijkstra, Bellman-Ford and 0-1 BFS for weighted edges.

Search over statesBFS where a node is (cell, keys, budget…).

Matrices and gridsNeighbour loops, bounds checks and grid-as-graph.