vault

Breadth-First Search

12 min read

Breadth-First Search

Breadth-first search (BFS) is a graph traversal algorithm that explores all nodes at distance d from the source before exploring nodes at distance d+1. It uses a queue (FIFO) instead of recursion, runs in O(V + E) time, and uses O(V) auxiliary space. BFS is the canonical algorithm for shortest path in an unweighted graph (or any graph with uniform edge weights), and it underlies the level-order tree traversal, connected-component finding, bipartite checking, and a swarm of interview problems involving “shortest steps to reach X.”

1. Intuition — The Friend-of-a-Friend Search

Imagine you’re trying to find the shortest chain of friends connecting you to a celebrity:

  • Layer 0: you (distance 0).
  • Layer 1: all your direct friends (distance 1).
  • Layer 2: all their direct friends, minus anyone already known (distance 2).
  • Layer 3: friends of layer-2 (distance 3).
  • …

You stop the moment you find the celebrity. The layer they appeared in is the shortest distance — guaranteed, because you exhausted all closer layers before moving outward.

That’s BFS exactly. The “queue” is the to-do list of people whose friends we haven’t asked yet; we always ask the oldest remaining person on the to-do list (FIFO), guaranteeing layer-by-layer expansion.

2. Tiny Worked Example

Find shortest path from A to F in this unweighted graph:

   A — B — C
   |   |   |
   D — E — F

Adjacency:

A: [B, D]
B: [A, C, E]
C: [B, F]
D: [A, E]
E: [B, D, F]
F: [C, E]

Run BFS from A:

StepQueue (front → back)VisitedJust visited
Start[A]{A}—
1[B, D]{A, B, D}A
2[D, C, E]{A, B, D, C, E}B
3[C, E]{A, B, D, C, E}D (no new neighbors)
4[E, F]{A, B, D, C, E, F}C — F discovered, distance 2

Or continuing: shortest path from A to F is 2 (A → C → F or A → E → F or A → B → C → F is 3 — wait, A to C is also 2 not 1. Let me re-check: A → B → C is 2 edges; A → C is not direct because there’s no direct edge. So A→B→C→F is 3 edges, A→D→E→F is 3 edges, A→B→E→F is 3 edges. Hmm — let me reconsider the graph.)

Actually, with the layout I drew, A is not directly connected to F — the shortest path is 3 (e.g., A → B → C → F). Let me redo the trace cleanly:

StepQueueVisitedDistance map
0[(A, 0)]{A}A:0
1[(B, 1), (D, 1)]{A, B, D}A:0, B:1, D:1
2[(D, 1), (C, 2), (E, 2)]{A, B, C, D, E}+ C:2, E:2
3[(C, 2), (E, 2)]same(D had no new neighbors)
4[(E, 2), (F, 3)]+ F+ F:3 — found!

Shortest distance A→F is 3. BFS guarantees this is the minimum because we explored everything at distance 1 before anything at distance 2, etc.

3. Pseudocode

bfs(graph, source):
    distance := empty map
    distance[source] := 0
    queue := empty FIFO queue
    enqueue source onto queue
    while queue is not empty:
        u := dequeue
        for each neighbor v of u:
            if v not in distance:
                distance[v] := distance[u] + 1
                enqueue v onto queue
    return distance

That’s it. Eight lines. The only state is the queue and the visited/distance map.

4. Python — Idiomatic

from collections import deque
 
def bfs(graph, source):
    """graph: dict mapping node -> list of neighbors. Returns dist map."""
    dist = {source: 0}
    q = deque([source])
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:                # haven't visited
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

Use collections.deque, not list

Python’s list has O(n) pop(0). Using a list as a queue makes BFS quietly O(V²) instead of O(V+E). collections.deque has O(1) popleft().

Reconstructing the path (not just the distance)

def bfs_path(graph, source, target):
    parent = {source: None}
    q = deque([source])
    while q:
        u = q.popleft()
        if u == target:
            # walk back from target to source via parent pointers
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1]
        for v in graph[u]:
            if v not in parent:
                parent[v] = u
                q.append(v)
    return None                              # unreachable

The parent map serves dual duty: it’s both the visited-marker and the path-reconstruction info.

5. The Critical Detail: Mark Visited at Enqueue, Not Dequeue

# WRONG (exponential blowup possible)
while q:
    u = q.popleft()
    if u in visited: continue                 # late marking
    visited.add(u)                             # <-- bug source
    for v in graph[u]:
        q.append(v)                            # might enqueue v many times
 
# CORRECT
visited = {source}
while q:
    u = q.popleft()
    for v in graph[u]:
        if v not in visited:
            visited.add(v)                     # <-- mark at enqueue
            q.append(v)

If you mark visited only at dequeue, the same node can be enqueued multiple times before it’s dequeued. For dense graphs this can blow the queue size to O(VE). Always mark at enqueue.

This is the #1 BFS bug in interviews and in real production code.

6. Complexity

For a graph with V vertices and E edges:

  • Time: O(V + E). Each vertex is enqueued and dequeued once → O(V). Each edge is examined exactly once (or twice for undirected: from each endpoint) → O(E).
  • Space: O(V). The queue can hold up to V elements (e.g., when the graph is one big star); the visited set holds up to V.

For a tree (special case where E = V - 1), this becomes O(V).

Why both V and E matter: for a sparse graph (E ≈ V), this is essentially O(V). For a dense graph (E ≈ V²), this is essentially O(V²). The two terms are independent; don’t simplify O(V + E) to O(V) or O(E).

7. Why BFS = Shortest Path (Unweighted)

Claim: BFS from s computes dist[v] = shortest-path distance from s to v for every reachable v.

Proof sketch. By induction on distance. Base case: dist[s] = 0, correct. Inductive step: assume all nodes at distance ≤ k are correctly labeled. The first time we examine a node v at true-distance k+1, it must be from some neighbor u at true-distance k. Because BFS dequeues in FIFO order and all distance-k nodes were enqueued before distance-(k+1) ones, u is dequeued before any distance-(k+1) node — so when we reach v from u, no shorter path has been (or will be) found.

The crux: FIFO order on the queue corresponds to non-decreasing distance order. This is the layer property. It only works because edge weights are uniform — for variable weights, you need Dijkstra’s Algorithm (which uses a priority queue instead of a FIFO).

8. Important Variants

8.1 Multi-Source BFS

Sometimes you start from multiple sources simultaneously and want the distance from “the nearest source” to each vertex. Trick: initialize the queue with all source nodes at once.

def multi_source_bfs(graph, sources):
    dist = {s: 0 for s in sources}
    q = deque(sources)
    while q:
        u = q.popleft()
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

Canonical use case: “Rotting Oranges” (LC 994). A grid where some cells are rotten oranges; each minute, rot spreads to adjacent cells. How many minutes until all are rotten? Multi-source BFS from all initially-rotten cells, return max distance. This pattern appears in many grid problems (“walls and gates,” “shortest distance from any building,” etc.).

8.2 0-1 BFS (Deque-Based)

If edge weights are only 0 or 1, you can compute shortest paths in O(V + E) using a deque instead of a queue:

  • Push edges with weight 0 to the front of the deque.
  • Push edges with weight 1 to the back.

This preserves the BFS layer property (since “weight 0” doesn’t increase distance, those nodes belong in the same “layer” as their neighbor).

def zero_one_bfs(graph, source):
    """graph: dict node -> list of (neighbor, weight in {0,1})."""
    dist = {source: 0}
    q = deque([source])
    while q:
        u = q.popleft()
        for v, w in graph[u]:
            nd = dist[u] + w
            if v not in dist or nd < dist[v]:
                dist[v] = nd
                if w == 0: q.appendleft(v)
                else:      q.append(v)
    return dist

Useful for grid problems where some moves are “free” (e.g., portals) and others cost 1.

8.3 Bidirectional BFS

For finding shortest path from s to t in a very large graph: run BFS from both s and t simultaneously, alternating one step from each side. Stop when the two frontiers meet. The work is O(b^(d/2)) where b is branching factor and d is distance — much better than BFS’s O(b^d) for large d.

Used in word-ladder problems, social-network distance queries, and game-state search.

def bidirectional_bfs(graph, s, t):
    if s == t: return 0
    front_s, front_t = {s}, {t}
    visited_s, visited_t = {s}, {t}
    dist = 0
    while front_s and front_t:
        # always expand the smaller frontier (heuristic for speed)
        if len(front_s) > len(front_t):
            front_s, front_t = front_t, front_s
            visited_s, visited_t = visited_t, visited_s
        dist += 1
        next_front = set()
        for u in front_s:
            for v in graph[u]:
                if v in visited_t: return dist
                if v not in visited_s:
                    visited_s.add(v); next_front.add(v)
        front_s = next_front
    return -1                                  # unreachable

8.4 BFS on Implicit Graphs

The graph isn’t always given explicitly — sometimes you compute neighbors on the fly. “Find the minimum number of steps to transform word A into word B by changing one letter at a time, only valid English words allowed” — the graph is implicit (each word is a node; neighbors are words differing by one letter). BFS still applies.

This is the most common interview application: the “graph” is a state space, and BFS finds the minimum number of state transitions.

Examples:

  • Sliding puzzle (8-puzzle, 15-puzzle): each board state is a node.
  • Word ladder.
  • Open-the-lock combinations.
  • Knight’s shortest path on a chessboard.
  • Minimum genetic mutations.

9. BFS for Other Problems

9.1 Connected Components

For each unvisited node, run BFS; that BFS visits exactly one component. Count = number of components.

9.2 Bipartite Check

A graph is bipartite iff it can be 2-colored such that no edge connects same-colored nodes. BFS, alternating colors level by level. If you ever find an edge to an already-colored same-color node, it’s not bipartite.

def is_bipartite(graph):
    color = {}
    for s in graph:
        if s in color: continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if v not in color:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    return True

9.3 Tree Level-Order Traversal

A tree is a graph; level-order traversal is BFS where the source is the root. See Tree Traversals §5.4.

9.4 Topological Sort (Kahn’s Algorithm)

Repeatedly enqueue nodes with in-degree 0; when dequeued, decrement in-degree of all neighbors, enqueue any newly-zero ones. The dequeue order is a topological order. See Topological Sort.

10. Pitfalls

10.1 List instead of deque

Python list.pop(0) is O(n) because it shifts all remaining elements. Always use collections.deque. Same for arr.insert(0, x) — O(n).

10.2 Marking Visited at Dequeue

Covered in §5. Causes duplicate enqueues, blows up time/space.

10.3 BFS for Weighted Graphs

BFS computes shortest distance in number of edges. If edge weights vary, you need Dijkstra’s Algorithm (or 0-1 BFS for the {0,1} special case). A common interview trap: the problem looks unweighted but secretly has different “step costs.”

10.4 Forgetting to Initialize Source as Visited

q = deque([source])     # missing: visited.add(source)
while q:
    u = q.popleft()
    for v in graph[u]:
        if v not in visited:
            visited.add(v); q.append(v)

If source has an edge back to itself (or a 2-cycle to a neighbor and back), you’ll re-enqueue source. Always initialize visited = {source} before the loop.

10.5 Modifying the Graph During BFS

Adding/removing edges while BFS is running causes undefined behavior. If you need to track multiple states (e.g., visited with a key picked up), the trick is to make the state (node, items-picked-up) the BFS node — never modify the graph itself.

10.6 Returning Distance to Source

dist[source] = 0. If your “found target” check returns the distance to source instead of zero or to target, you’ve got a bug. Always trace by hand on a 2-node example.

10.7 Disconnected Graphs

A single BFS only reaches one connected component. If your problem requires processing all nodes, wrap in for s in graph: if s not in visited: bfs(s).

11. Diagram — Layer-By-Layer Expansion

flowchart TD
  S[Source<br/>distance=0] --> L1A[Layer 1<br/>distance=1]
  S --> L1B[Layer 1<br/>distance=1]
  S --> L1C[Layer 1<br/>distance=1]
  L1A --> L2A[Layer 2<br/>distance=2]
  L1B --> L2B[Layer 2<br/>distance=2]
  L1C --> L2C[Layer 2<br/>distance=2]
  L2A --> L3[Layer 3<br/>distance=3]
  L2B --> L3
  L2C --> L3

What this diagram shows. BFS visits the source first, then all of layer 1, then all of layer 2, etc. The FIFO queue enforces this: layer-k nodes are enqueued before layer-(k+1), and dequeued in the same order. Distance to any node = layer in which it appears.

12. BFS vs DFS — When to Use Which

Use BFSUse DFS
Shortest path (unweighted)All-paths exploration
Level-order processingTopological sort, SCC
Minimum-step state-space searchCycle detection in directed graph
Bipartite checkRecursion-friendly tree traversal
When recursion would blow the stackWhen you need pre/in/post structure
Branch-and-bound where shallow solutions existPath-tracking with backtrack

When in doubt for graph problems: BFS for shortest, DFS for everything else.

13. Common Interview Problems

ProblemPattern
LC 200 — Number of IslandsBFS/DFS connected components on grid
LC 207 — Course ScheduleTopological sort (BFS variant: Kahn’s)
LC 994 — Rotting OrangesMulti-source BFS
LC 127 — Word LadderBFS on implicit graph
LC 752 — Open the LockBFS on state space
LC 286 — Walls and GatesMulti-source BFS
LC 542 — 01 MatrixMulti-source BFS
LC 785 — Is Graph BipartiteBFS with 2-coloring
LC 102 — Binary Tree Level OrderTree BFS with level grouping
LC 199 — Binary Tree Right Side ViewLevel BFS, take last per level

14. Open Questions

  • When does bidirectional BFS not help? When b ≈ d (small graph, deep target) — overhead exceeds savings.
  • For huge graphs, is there a memory-efficient BFS? Yes — IDA* or iterative deepening DFS, trading time for memory.

15. See Also

Graph View

Backlinks