BFS — Algorithm & Apps - Learning Module

Loading content...

0/276

BFS Algorithm — The Mechanics of Level-Order Exploration

The Art of Systematic Exploration

Imagine you're standing at the entrance of a vast, interconnected labyrinth. How do you explore it systematically to understand its complete structure? Do you plunge deep down one corridor until you hit a dead end, then backtrack? Or do you first examine all the rooms immediately adjacent to you, then all the rooms adjacent to those, expanding outward in concentric circles like ripples from a stone dropped in still water?

Breadth-First Search (BFS) embodies the second approach—a methodical, level-by-level exploration that guarantees you visit every reachable vertex exactly once, always discovering vertices in order of their distance from your starting point. This seemingly simple idea—"explore all neighbors before going deeper"—forms the foundation for some of the most powerful algorithms in computer science.

BFS is not merely an academic exercise. It's the algorithm your GPS uses to find the shortest route when all roads take equal time. It's how web crawlers systematically discover every page on the internet. It's the mechanism behind finding the minimum number of moves to solve a Rubik's cube. Understanding BFS deeply means understanding a fundamental paradigm of computational exploration.

What You Will Learn

By the end of this page, you will understand the BFS algorithm at a deep, intuitive level. You'll know exactly how the queue orchestrates exploration, why BFS naturally discovers shortest paths in unweighted graphs, and how to implement BFS correctly for any graph representation. This foundation prepares you to wield BFS as a powerful tool across dozens of problem domains.

The Fundamental Insight: Why Breadth, Not Depth?

Before examining BFS mechanically, let's understand why breadth-first exploration is a distinct and valuable approach.

The problem BFS solves:

Given a graph G = (V, E) and a source vertex s, we want to:

Discover every vertex reachable from s
Compute the minimum number of edges needed to reach each vertex from s
Produce a breadth-first tree rooted at s that encodes shortest paths

The key constraint that makes BFS special is the notion of distance. In an unweighted graph, the distance between two vertices is the minimum number of edges on any path connecting them. BFS computes these distances naturally as a byproduct of its exploration order.

The "wavefront" mental model:

Think of BFS as dropping a pebble into a still pond. The ripples expand outward uniformly—first reaching points at distance 1 from impact, then distance 2, then distance 3, and so on. No point at distance 3 gets wet before all points at distance 2 are reached.

Similarly, BFS explores vertices in "waves" based on their distance from the source:

Wave 0: The source vertex itself (distance 0)
Wave 1: All vertices directly connected to source (distance 1)
Wave 2: All undiscovered vertices connected to Wave 1 vertices (distance 2)
Wave k: All undiscovered vertices connected to Wave (k-1) vertices

This layered structure is what distinguishes BFS from Depth-First Search (DFS), which explores as deeply as possible before backtracking.

The Core Guarantee

BFS guarantees that when you first discover a vertex, you've discovered it via a shortest path from the source. This property makes BFS the algorithm of choice for unweighted shortest path problems—a guarantee DFS cannot provide.

Why depth-first fails for shortest paths:

Consider a simple graph: A—B—C where A is also directly connected to C (A—C). If we use DFS starting from A and happen to explore B first, we might discover C via A→B→C (distance 2) before exploring the direct edge A→C (distance 1). DFS doesn't track distances—it simply explores as far as possible along each branch.

BFS, by contrast, processes vertices in distance order. From A, we first consider all immediate neighbors (B and C at distance 1). Only after all distance-1 vertices are processed do we move to distance-2 vertices. The direct edge A→C is always discovered before any 2-hop path to C.

This "level-by-level" processing is the essence of BFS and requires careful orchestration—which brings us to the queue.

The BFS Algorithm: Complete Specification

Let's specify BFS with precision. Given a graph G = (V, E) and source vertex s, BFS maintains several data structures:

State tracking for each vertex u ∈ V:

color[u]: Tracks discovery state
- WHITE: Undiscovered (never seen)
- GRAY: Discovered but not fully processed (in the queue)
- BLACK: Fully processed (all neighbors examined)
distance[u]: The computed distance from s to u (∞ initially)
parent[u]: The predecessor of u on the shortest path from s (null initially)

The queue Q:

A FIFO (First-In-First-Out) data structure
Stores vertices that are discovered (GRAY) but not yet fully processed

Why these states matter:

The three colors encode the exploration frontier:

WHITE vertices are unexplored territory—we haven't reached them yet
GRAY vertices form the current "wavefront"—discovered but still yielding new discoveries
BLACK vertices are behind the wavefront—all their neighbors have been considered

This classification ensures each vertex and edge is processed exactly once.

bfs-algorithm.pseudo

Pseudocode

BFS(G, s):
    // Initialize all vertices
    for each vertex u in V[G]:
        color[u] = WHITE
        distance[u] = ∞
        parent[u] = NULL
    
    // Initialize source vertex
    color[s] = GRAY
    distance[s] = 0
    parent[s] = NULL
    
    // Create empty queue and enqueue source
    Q = empty queue
    ENQUEUE(Q, s)
    
    // Main BFS loop
    while Q is not empty:
        u = DEQUEUE(Q)
        
        // Examine all neighbors of u
        for each vertex v in Adj[u]:
            if color[v] == WHITE:      // v is undiscovered
                color[v] = GRAY        // Mark as discovered
                distance[v] = distance[u] + 1
                parent[v] = u
                ENQUEUE(Q, v)
        
        color[u] = BLACK              // u is fully processed
    
    return (distance, parent)

Line-by-line analysis:

Lines 2-5 (Initialization): Every vertex starts WHITE (undiscovered), with infinite distance and no parent. This O(V) initialization sets up our clean slate.

Lines 7-9 (Source setup): The source is our starting point—distance 0, discovered (GRAY), but with no parent since it's the root of our exploration tree.

Lines 11-12 (Queue creation): We create our FIFO queue and seed it with the source. The queue is the heart of BFS—it enforces the level-by-level exploration order.

Line 15 (Main loop): We continue while there are discovered-but-not-processed vertices. When the queue empties, we've explored everything reachable.

Line 16 (Dequeue): We extract the front vertex. FIFO order ensures we always process vertices in distance order—all distance-k vertices before any distance-(k+1) vertices.

Lines 18-23 (Neighbor examination): For each edge (u, v), if v is undiscovered (WHITE), we:

Discover it (mark GRAY)
Set its distance as parent's distance + 1
Record u as its parent (for path reconstruction)
Enqueue it for future processing

Line 25 (Mark complete): After examining all of u's neighbors, u is BLACK—we'll never visit it again.

The Distance Invariant

The queue always contains vertices in at most two consecutive "levels". If the front of the queue has distance d, all other queue elements have distance d or d+1. This invariant is maintained because we only add distance-(d+1) vertices when processing distance-d vertices. This is why the simple formula distance[v] = distance[u] + 1 correctly computes shortest paths.

Queue-Based Exploration: The Engine of BFS

The queue is not an arbitrary choice—it's the only data structure that produces breadth-first exploration. Understanding why requires understanding how different data structures affect exploration order.

Why FIFO enforces level-order:

Consider what happens with a queue:

We start with just source s (distance 0) in the queue
We dequeue s, examine its neighbors (all at distance 1), and enqueue them
Now the queue contains only distance-1 vertices
We dequeue the first distance-1 vertex, enqueue its undiscovered neighbors (distance 2)
These distance-2 vertices go to the back of the queue
We continue processing distance-1 vertices (at the front) before reaching distance-2 vertices

The key insight: new discoveries (distance d+1) go behind existing discoveries (distance d). FIFO ensures we process all distance-d vertices before any distance-(d+1) vertices.

What if we used a stack (LIFO)?

If we replaced the queue with a stack, new discoveries would go to the front, and we'd process them before finishing the current level. This produces depth-first exploration—going as deep as possible before backtracking. The change from FIFO to LIFO completely changes the exploration pattern!

What if we used a priority queue?

If we used a priority queue ordered by some weight, we'd get Dijkstra's algorithm—a generalization of BFS for weighted graphs. BFS is actually a special case of Dijkstra where all edges have weight 1.

Data Structure vs. Exploration Pattern
Data Structure	Order	Exploration Pattern	Resulting Algorithm
Queue (FIFO)	First-In-First-Out	Level-by-level (breadth-first)	BFS
Stack (LIFO)	Last-In-First-Out	Deep before wide (depth-first)	DFS (iterative)
Priority Queue	By edge weight	Lowest total cost first	Dijkstra's Algorithm
Priority Queue	By heuristic	Estimated best path first	A* Search

Visualizing the queue's state:

Let's trace through a concrete example. Consider a simple graph where A connects to B and C, B connects to D, and C connects to D and E.

        A
       / \
      B   C
      |   |\
      D---+ E

Initial state:

Queue: [A]
Distance: A=0, all others=∞

After processing A:

Dequeue A, examine neighbors B and C
Queue: [B, C]
Distance: A=0, B=1, C=1

After processing B:

Dequeue B, examine neighbor D (C already discovered)
Queue: [C, D]
Distance: A=0, B=1, C=1, D=2

After processing C:

Dequeue C, examine neighbors D (already discovered) and E (new!)
Queue: [D, E]
Distance: A=0, B=1, C=1, D=2, E=2

After processing D:

Dequeue D, no new neighbors
Queue: [E]
All neighbors already discovered

After processing E:

Dequeue E, no neighbors
Queue: []
BFS complete!

Notice how all distance-1 vertices (B, C) were fully processed before any distance-2 vertices (D, E). This is the queue's magic.

Common Implementation Mistake

A frequent bug is checking for discovery when dequeuing rather than when enqueuing. If you mark vertices as discovered only when you dequeue them (instead of when you enqueue them), the same vertex might be enqueued multiple times by different neighbors. This wastes memory and time, and can produce incorrect results if not handled carefully. Always mark as discovered (GRAY) immediately upon enqueueing.

Implementation Patterns: From Theory to Code

The pseudocode above is mathematically precise but includes more state than practical implementations typically need. Let's examine real implementations that balance clarity and efficiency.

Simplification: Replacing colors with visited set

In practice, we rarely need three colors. A simple "visited" boolean or set suffices:

Not in visited = WHITE (undiscovered)
In visited = GRAY or BLACK (discovered, don't re-process)

The distinction between GRAY and BLACK matters for some applications (like edge classification) but not for basic BFS.

bfs-implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
from collections import deque
from typing import List, Dict, Set, Optional
 
def bfs(graph: Dict[int, List[int]], source: int) -> tuple[Dict[int, int], Dict[int, Optional[int]]]:
    """
    Perform BFS from source vertex.
    
    Args:
        graph: Adjacency list representation {vertex: [neighbors]}
        source: Starting vertex
    
    Returns:
        distance: Dict mapping each vertex to its distance from source
        parent: Dict mapping each vertex to its parent in BFS tree
    """
    # Initialize data structures
    visited: Set[int] = set()
    distance: Dict[int, int] = {}
    parent: Dict[int, Optional[int]] = {}
    queue: deque = deque()
    
    # Initialize source
    visited.add(source)
    distance[source] = 0
    parent[source] = None
    queue.append(source)
    
    # BFS main loop
    while queue:
        u = queue.popleft()  # Dequeue from front (FIFO)
        
        for v in graph.get(u, []):
            if v not in visited:
                visited.add(v)
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
    
    return distance, parent
 
 
def reconstruct_path(parent: Dict[int, Optional[int]], target: int) -> List[int]:
    """
    Reconstruct the shortest path from source to target.
    
    Args:
        parent: Parent dictionary from BFS
        target: Destination vertex
    
    Returns:
        List of vertices on the path from source to target
        Empty list if target is unreachable
    """
    if target not in parent:
        return []  # Target was never discovered
    
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = parent[current]
    
    return path[::-1]  # Reverse to get source-to-target order
 
 
# Example usage
if __name__ == "__main__":
    # Graph: 0 -- 1 -- 2
    #        |    |
    #        3 -- 4
    graph = {
        0: [1, 3],
        1: [0, 2, 4],
        2: [1],
        3: [0, 4],
        4: [1, 3]
    }
    
    dist, parent = bfs(graph, 0)
    print(f"Distances from 0: {dist}")
    print(f"Path to 2: {reconstruct_path(parent, 2)}")

Implementation notes:

Queue choice matters for performance
- Python: Use collections.deque (O(1) popleft), not list.pop(0) (O(n)!)
- TypeScript: shift() is O(n)—for large graphs, use a proper queue implementation
- Java: LinkedList with poll() provides O(1) dequeue
Graph representation
- Adjacency list is ideal for BFS—we iterate through neighbors frequently
- Adjacency matrix works but wastes time checking non-edges
Visited check timing
- Always check and mark visited before enqueueing, not when dequeuing
- This prevents duplicate entries and reduces queue size

Correctness: Why BFS Finds Shortest Paths

It's tempting to accept that BFS finds shortest paths because "it explores level by level." But let's prove this rigorously—understanding the proof deepens your intuition and helps you verify whether BFS is applicable to new problems.

Theorem: For any vertex v reachable from source s, BFS computes distance[v] = δ(s, v), where δ(s, v) is the true shortest path distance.

Proof sketch:

We prove by induction on the true distance δ(s, v).

Base case: δ(s, s) = 0, and BFS sets distance[s] = 0 during initialization. ✓

Inductive step: Assume the claim holds for all vertices u with δ(s, u) < k. Consider a vertex v with δ(s, v) = k.

Let p = s → ... → u → v be a shortest path from s to v. Then:

δ(s, u) = k - 1 (u is one edge before v on a shortest path)
By inductive hypothesis, distance[u] = k - 1
Therefore u is discovered and enqueued when some vertex at distance k-2 is processed

When u is dequeued and processed:

v is examined as a neighbor of u
If v is still undiscovered, distance[v] is set to distance[u] + 1 = k ✓
If v was already discovered, it was discovered via another shortest path (since all paths that discover v have length ≤ k), so distance[v] = k ✓

Key insight: BFS's shortest path guarantee relies on:

All edges having the same "weight" (cost of 1)
FIFO processing order ensuring distance-d vertices are processed before distance-(d+1) vertices

When BFS Fails for Shortest Paths

BFS does NOT find shortest paths in weighted graphs where edges have different costs. If edge (A, B) has cost 1 and edge (A, C) has cost 10, BFS might claim both B and C are "distance 1" from A. For weighted graphs, you need Dijkstra's algorithm (non-negative weights) or Bellman-Ford (any weights). The unweighted case where BFS works is a special case where Dijkstra degenerates to BFS.

The BFS Tree:

BFS produces more than just distances—it produces a tree:

The parent pointers (parent[v] = u means v was discovered from u) form a BFS tree rooted at the source. This tree has important properties:

Shortest path encoding: The path from s to any vertex v in the BFS tree is a shortest path in the original graph
Unique distances: The tree depth of any vertex equals its distance from s
Tree edges vs. cross edges: In the BFS tree:
- Tree edges connect vertices at consecutive levels (distance d to distance d+1)
- Non-tree edges connect vertices at the same level or consecutive levels (never skip levels)

The third property is subtle but important: in BFS, you'll never find an edge connecting a distance-2 vertex directly to a distance-5 vertex. If such an edge existed, the distance-5 vertex would have been discovered as a distance-3 vertex instead!

Summary: The BFS Algorithm

We've established a deep understanding of the BFS algorithm's mechanics. Let's consolidate the key insights:

Key Takeaways

•BFS explores level-by-level — Vertices are discovered and processed in order of their distance from the source, like ripples expanding outward.
•The queue is essential — FIFO ordering ensures all distance-d vertices are processed before any distance-(d+1) vertices. Replace the queue with a stack, and you get DFS instead.
•BFS computes shortest paths — In unweighted graphs, BFS naturally discovers shortest paths because it visits vertices in distance order.
•Mark visited upon enqueueing — To avoid duplicate processing and correctness issues, mark vertices as discovered immediately when adding to the queue.
•The BFS tree encodes paths — Parent pointers form a tree where every root-to-vertex path is a shortest path in the original graph.
•Only works for unweighted graphs — BFS assumes all edges have equal cost. For weighted graphs, use Dijkstra's or Bellman-Ford algorithm.

What's next:

Now that we understand the BFS algorithm mechanically, the next page explores Queue-Based Exploration in greater depth—examining the queue invariants, memory behavior, and optimization techniques that make BFS practical for large-scale graphs.

Page Complete

You now have a deep understanding of the BFS algorithm's mechanics. You understand how the queue orchestrates level-by-level exploration, why this naturally produces shortest paths in unweighted graphs, and how to implement BFS correctly. Next, we'll explore queue-based exploration in greater depth.