Common Queue Patterns - Learning Module

Loading content...

0/279

BFS Intuition (Without Full Graph Context)

Exploration Through Expanding Waves

Imagine you're searching for a friend in a crowded stadium. You wouldn't randomly teleport to different sections hoping to find them. Instead, you'd start where you are and systematically check nearby seats first, then slightly farther seats, then farther still—expanding outward like ripples on a pond.

This is the essence of Breadth-First Search (BFS): an exploration strategy that checks all positions at distance 1 before checking any at distance 2, all at distance 2 before any at distance 3, and so on. The result? When you find your target, you've found the shortest path to it—guaranteed.

BFS is fundamentally powered by the queue. The same FIFO principle that gave us level-order tree traversal now unlocks something even more powerful: the ability to explore any interconnected structure and find optimal paths. While a complete treatment of BFS requires graph theory (coming in a later chapter), the core intuition is queue-based and can be understood right now.

What You Will Master

By the end of this page, you will understand BFS as a conceptual strategy—how queues enable systematic exploration, why BFS guarantees shortest paths in unweighted scenarios, and how to recognize BFS-appropriate problems. You'll build intuition that translates directly to graph algorithms later.

From Trees to General Exploration

In the previous page, we mastered level-order tree traversal. But trees are a very specific structure: no cycles, one path between any two nodes, clear parent-child relationships. The real world is messier.

Consider these scenarios:

Social networks: People connect to multiple friends, who connect to others, forming complex webs with no clear hierarchy
City street maps: Intersections connect to multiple roads, which connect to other intersections, often in loops
Web page links: Pages link to multiple other pages, which link back, creating circular reference patterns
Game states: From any game position, multiple moves are possible, some leading back to previous positions

These are graphs: structures where nodes (vertices) can have arbitrary connections (edges), potentially including cycles. Level-order traversal's naive approach would fail here—we'd revisit the same nodes infinitely!

The Infinite Loop Trap

When exploring structures with cycles, a careless approach leads to infinite loops. If A connects to B and B connects back to A, we'd ping-pong forever. BFS addresses this through visited tracking, which we'll cover shortly.

BFS adapts level-order thinking:

The genius of BFS is recognizing that the queue-based level-order pattern remains valid—we just need to:

Generalize "children" to "neighbors" — Instead of left/right children, we consider all connected nodes
Track visited nodes — Avoid re-processing nodes we've already seen
Measure "distance" instead of "level" — The concept of level becomes the concept of distance from the starting point

With these adaptations, the same FIFO principle that ordered tree levels now orders exploration by distance from origin.

The Wave Expansion Mental Model

BFS is best understood through the wave expansion mental model. Imagine dropping a stone into still water:

Wave 0: The initial point of impact (your starting position)
Wave 1: All points exactly 1 unit away from the start
Wave 2: All points exactly 2 units away from the start
Wave n: All points exactly n units away from the start

The waves expand uniformly. Wave 2 doesn't begin until wave 1 has fully expanded. This is exactly what the queue provides: FIFO ordering ensures we process all wave-1 nodes before any wave-2 nodes.

wave-visualization.ts
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
// Visualizing wave expansion in a grid
// Starting from center, explore outward
 
type Cell = { row: number; col: number };
 
function visualizeWaveExpansion(
    gridSize: number,
    startRow: number,
    startCol: number
): void {
    // Create grid where value = distance from start
    const distances: number[][] = Array(gridSize)
        .fill(null)
        .map(() => Array(gridSize).fill(-1));  // -1 = unvisited
    
    const queue: Cell[] = [];
    
    // Wave 0: the starting cell
    queue.push({ row: startRow, col: startCol });
    distances[startRow][startCol] = 0;
    
    // Directions: up, right, down, left
    const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    
    while (queue.length > 0) {
        const current = queue.shift()!;
        const currentDist = distances[current.row][current.col];
        
        // Explore all 4 neighbors
        for (const [dr, dc] of directions) {
            const newRow = current.row + dr;
            const newCol = current.col + dc;
            
            // Check bounds and if unvisited
            if (
                newRow >= 0 && newRow < gridSize &&
                newCol >= 0 && newCol < gridSize &&
                distances[newRow][newCol] === -1
            ) {
                // This neighbor is one step farther
                distances[newRow][newCol] = currentDist + 1;
                queue.push({ row: newRow, col: newCol });
            }
        }
    }
    
    // Print the grid showing distances
    console.log("Wave expansion from center:");
    for (const row of distances) {
        console.log(row.map(d => String(d).padStart(2)).join(' '));
    }
}
 
// For a 7x7 grid starting from center (3,3):
/*
Wave expansion from center:
 6  5  4  3  4  5  6
 5  4  3  2  3  4  5
 4  3  2  1  2  3  4
 3  2  1  0  1  2  3   <-- 0 is start
 4  3  2  1  2  3  4
 5  4  3  2  3  4  5
 6  5  4  3  4  5  6
 
Notice: Perfect concentric "squares" of increasing distance!
Each wave completes before the next begins.
*/

Why waves matter for shortest paths:

When BFS reaches a node for the first time, it's reached it via the shortest possible path from the start. Why? Because BFS explores all nodes at distance d before any node at distance d+1. If there were a shorter path to that node, we would have found it earlier (during an earlier wave).

This is the shortest path guarantee of BFS in unweighted graphs—one of its most powerful properties.

Unweighted = Equal Cost

BFS guarantees shortest paths when all edges have equal cost ("unweighted"). In the grid example, moving from any cell to a neighbor costs 1 step. When edge costs vary, we need more sophisticated algorithms like Dijkstra's—but the intuition remains rooted in BFS.

The BFS Algorithm Template

Let's formalize the BFS pattern. While we'll present it abstractly here (without graph-specific terminology), this template is the foundation for all BFS applications.

The BFS Template:

1. Initialize:
   - queue ← [starting_node]
   - visited ← {starting_node}
   - (optional) distance[starting_node] ← 0

2. While queue is not empty:
   a. current ← dequeue from front
   b. If current is the goal: FOUND! (return solution)
   c. For each neighbor of current:
      - If neighbor not in visited:
        - Add neighbor to visited
        - Enqueue neighbor
        - (optional) distance[neighbor] ← distance[current] + 1

3. If loop completes without finding goal: NOT REACHABLE

bfs-template.ts
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
82
83
84
85
86
87
88
89
// Generic BFS template
interface Node {
    id: string;
    // Other properties...
}
 
interface BFSResult {
    found: boolean;
    distance: number;
    path: string[];
}
 
function bfsTemplate(
    start: Node,
    isGoal: (node: Node) => boolean,
    getNeighbors: (node: Node) => Node[]
): BFSResult {
    // Track visited nodes to avoid revisiting
    const visited = new Set<string>();
    
    // Track distance from start (optional, for shortest path)
    const distance = new Map<string, number>();
    
    // Track parent for path reconstruction (optional)
    const parent = new Map<string, string | null>();
    
    // Initialize queue with starting node
    const queue: Node[] = [start];
    visited.add(start.id);
    distance.set(start.id, 0);
    parent.set(start.id, null);
    
    while (queue.length > 0) {
        const current = queue.shift()!;
        
        // Check if we've found the goal
        if (isGoal(current)) {
            // Reconstruct path by following parents backward
            const path: string[] = [];
            let nodeId: string | null | undefined = current.id;
            while (nodeId !== null && nodeId !== undefined) {
                path.unshift(nodeId);
                nodeId = parent.get(nodeId);
            }
            
            return {
                found: true,
                distance: distance.get(current.id)!,
                path
            };
        }
        
        // Explore all neighbors
        for (const neighbor of getNeighbors(current)) {
            if (!visited.has(neighbor.id)) {
                visited.add(neighbor.id);
                distance.set(neighbor.id, distance.get(current.id)! + 1);
                parent.set(neighbor.id, current.id);
                queue.push(neighbor);
            }
        }
    }
    
    // Goal not reachable
    return {
        found: false,
        distance: -1,
        path: []
    };
}
 
/*
Key components:
 
1. visited Set: Prevents infinite loops in cyclic structures
   - Add to visited WHEN enqueueing, not when processing
   - This prevents duplicate enqueuing of the same node
 
2. distance Map: Tracks shortest distance from start
   - Each neighbor is exactly 1 step farther than its parent
   - When node is first visited, this IS its shortest distance
 
3. parent Map: Enables path reconstruction
   - Store the node that led us here
   - Trace backward from goal to start for the path
 
4. FIFO Queue: Ensures distance ordering
   - Closer nodes always processed before farther nodes
*/

Mark Visited When Enqueueing

A subtle but critical detail: mark nodes as visited when you add them to the queue, not when you process them. If you wait until processing, multiple paths might enqueue the same node before any one processes it, leading to duplicate work and incorrect results.

Grid-Based BFS Problems

One of the most common BFS applications is grid-based pathfinding. Grids are implicit graphs where:

Each cell is a node
Adjacent cells (up, down, left, right) are connected by edges
Some cells might be obstacles (walls) blocking movement

These problems appear everywhere: robot navigation, game AI, maze solving, and image processing.

shortest-path-grid.ts
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
// Classic problem: Shortest path in a binary matrix
// 0 = open cell, 1 = obstacle
// Find shortest path from top-left to bottom-right
 
function shortestPath(grid: number[][]): number {
    const rows = grid.length;
    const cols = grid[0].length;
    
    // Early exit checks
    if (grid[0][0] === 1 || grid[rows-1][cols-1] === 1) {
        return -1;  // Start or end is blocked
    }
    
    // 8 directions: including diagonals
    // Use 4 directions if diagonal movement not allowed
    const directions = [
        [-1, -1], [-1, 0], [-1, 1],
        [0, -1],           [0, 1],
        [1, -1],  [1, 0],  [1, 1]
    ];
    
    // BFS initialization
    const queue: [number, number, number][] = [[0, 0, 1]]; // row, col, distance
    const visited = new Set<string>();
    visited.add("0,0");
    
    while (queue.length > 0) {
        const [row, col, dist] = queue.shift()!;
        
        // Check if destination reached
        if (row === rows - 1 && col === cols - 1) {
            return dist;  // This IS the shortest path!
        }
        
        // Explore neighbors
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            const key = `${newRow},${newCol}`;
            
            // Check bounds, not obstacle, not visited
            if (
                newRow >= 0 && newRow < rows &&
                newCol >= 0 && newCol < cols &&
                grid[newRow][newCol] === 0 &&
                !visited.has(key)
            ) {
                visited.add(key);
                queue.push([newRow, newCol, dist + 1]);
            }
        }
    }
    
    return -1;  // No path exists
}
 
/*
Example:
Grid:
[0, 0, 0]
[1, 1, 0]
[1, 1, 0]
 
Path: (0,0) → (0,1) → (0,2) → (1,2) → (2,2)
Length: 5
 
BFS guarantees this is the shortest path!
*/

Complexity Analysis:

Time Complexity: O(rows × cols) — Each cell is visited at most once
Space Complexity: O(rows × cols) — The visited set and queue can hold all cells in the worst case

This is optimal for finding the shortest path—we must potentially examine every cell.

State Space Search with BFS

BFS isn't limited to physical spaces like grids. It can explore abstract state spaces where "positions" are configurations and "moves" are transformations between configurations.

Examples of state space problems:

Word ladder: Transform "CAT" to "DOG" changing one letter at a time, each intermediate being a valid word
Puzzle solving: From one game state, reach the goal state through valid moves
Lock combinations: From 0000, reach 1234 by rotating one digit at a time, avoiding forbidden combinations

In all these cases, BFS finds the minimum number of transformations to reach the goal.

word-ladder-bfs.ts
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
// Word Ladder: Find shortest transformation sequence
// from beginWord to endWord using words from wordList
// Each transformation changes exactly one letter
 
function wordLadder(
    beginWord: string,
    endWord: string,
    wordList: string[]
): number {
    // Convert to Set for O(1) lookups
    const wordSet = new Set(wordList);
    
    // If endWord not in dictionary, impossible
    if (!wordSet.has(endWord)) {
        return 0;
    }
    
    // BFS setup
    const queue: [string, number][] = [[beginWord, 1]];
    const visited = new Set<string>();
    visited.add(beginWord);
    
    while (queue.length > 0) {
        const [currentWord, depth] = queue.shift()!;
        
        // Try changing each character position
        for (let i = 0; i < currentWord.length; i++) {
            // Try each letter a-z
            for (let c = 97; c <= 122; c++) {  // 'a' to 'z'
                const letter = String.fromCharCode(c);
                if (letter === currentWord[i]) continue;
                
                // Create new word with one letter changed
                const newWord = 
                    currentWord.slice(0, i) + 
                    letter + 
                    currentWord.slice(i + 1);
                
                // Check if it's the destination
                if (newWord === endWord) {
                    return depth + 1;  // Found shortest path!
                }
                
                // If valid word and not visited, explore it
                if (wordSet.has(newWord) && !visited.has(newWord)) {
                    visited.add(newWord);
                    queue.push([newWord, depth + 1]);
                }
            }
        }
    }
    
    return 0;  // No path exists
}
 
/*
Example:
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
 
Transformation sequence:
"hit" → "hot" → "dot" → "dog" → "cog"
 
Shortest length: 5
 
BFS explores:
Distance 1: "hot" (hit → hot)
Distance 2: "dot", "lot" (hot → dot, hot → lot)
Distance 3: "dog", "log" (dot → dog, lot → log)
Distance 4: "cog" (dog → cog) ← FOUND!
*/

States as Graph Nodes

The key insight is abstracting the problem as a graph: States are nodes. Transformations are edges. BFS finds the shortest sequence of transformations. This mental model applies to any problem where you need the minimum steps between configurations.

Multi-Source BFS

Sometimes we need to find distances from multiple starting points simultaneously. Naive approach: run BFS from each source. Better approach: multi-source BFS — start with all sources in the queue at once.

Common scenarios:

Find the distance from each land cell to the nearest water cell
Find the distance from each empty cell to the nearest guard in a building
Calculate how long until fire spreads to each room from multiple fire sources
Determine the build time for each vertex when multiple builders start simultaneously

multi-source-bfs.ts
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
// Multi-source BFS: Distance to nearest source for each cell
// Classic problem: "01 Matrix" - distance to nearest 0 for each cell
 
function updateMatrix(matrix: number[][]): number[][] {
    const rows = matrix.length;
    const cols = matrix[0].length;
    
    const result: number[][] = Array(rows)
        .fill(null)
        .map(() => Array(cols).fill(Infinity));
    
    const queue: [number, number][] = [];
    
    // Multi-source: enqueue ALL zeros as starting points
    // They are all at distance 0 from themselves
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (matrix[r][c] === 0) {
                result[r][c] = 0;
                queue.push([r, c]);
            }
        }
    }
    
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    // BFS from all sources simultaneously
    while (queue.length > 0) {
        const [row, col] = queue.shift()!;
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (
                newRow >= 0 && newRow < rows &&
                newCol >= 0 && newCol < cols &&
                result[newRow][newCol] > result[row][col] + 1
            ) {
                result[newRow][newCol] = result[row][col] + 1;
                queue.push([newRow, newCol]);
            }
        }
    }
    
    return result;
}
 
/*
Input:
[0, 0, 0]
[0, 1, 0]
[1, 1, 1]
 
Output:
[0, 0, 0]
[0, 1, 0]
[1, 2, 1]
 
The center cell (1,1) has value 1: one step to any adjacent 0
The bottom center (2,1) has value 2: two steps to nearest 0
 
All 0s start in queue at distance 0.
Wave 1 reaches all cells adjacent to any 0.
Wave 2 reaches cells two steps from any 0.
Brilliant!
*/

Why multi-source BFS works:

Instead of thinking "distance from each source," think of it as "time for a wave to reach each cell." If we start waves from all sources at time 0, they expand simultaneously. The first wave to reach a cell comes from the nearest source—exactly what we want!

Complexity advantage:

Naive (BFS from each source): O(k × n × m) where k is the number of sources
Multi-source BFS: O(n × m) — each cell visited exactly once

This can be the difference between a solution that times out and one that runs efficiently.

Bidirectional BFS Intuition

An advanced optimization technique is bidirectional BFS: instead of searching from the start until you reach the goal, search from both ends simultaneously and stop when the search frontiers meet.

Why is this faster?

BFS explores all nodes at each distance level before moving to the next. If the shortest path has length d, standard BFS might explore O(b^d) nodes (where b is the branching factor—average number of neighbors per node).

With bidirectional BFS, each search only needs to go d/2 steps. The total exploration becomes O(2 × b^(d/2)) = O(b^(d/2)), which is dramatically smaller for large d.

Bidirectional BFS Savings (Branching Factor = 10)
Path Length	Standard BFS Nodes	Bidirectional BFS Nodes	Speedup
4	10,000	200	50×
6	1,000,000	2,000	500×
8	100,000,000	20,000	5,000×
10	10,000,000,000	200,000	50,000×

bidirectional-bfs-concept.ts
TypeScript
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
// Bidirectional BFS Concept (Pseudocode-ish)
// For word ladder or similar problems
 
function bidirectionalBFS(start: string, end: string, isValid: (s: string) => boolean): number {
    // Two frontiers expanding toward each other
    let frontSet = new Set<string>([start]);
    let backSet = new Set<string>([end]);
    const visitedFront = new Set<string>([start]);
    const visitedBack = new Set<string>([end]);
    
    let steps = 0;
    
    while (frontSet.size > 0 && backSet.size > 0) {
        // Always expand the smaller frontier (optimization)
        if (frontSet.size > backSet.size) {
            [frontSet, backSet] = [backSet, frontSet];
            [visitedFront, visitedBack] = [visitedBack, visitedFront];
        }
        
        steps++;
        const nextFront = new Set<string>();
        
        for (const word of frontSet) {
            for (const neighbor of getNeighbors(word, isValid)) {
                // Check if we've met the other search!
                if (backSet.has(neighbor)) {
                    return steps;  // Found path of length 'steps'
                }
                
                if (!visitedFront.has(neighbor)) {
                    visitedFront.add(neighbor);
                    nextFront.add(neighbor);
                }
            }
        }
        
        frontSet = nextFront;
    }
    
    return -1;  // No path exists
}
 
function getNeighbors(word: string, isValid: (s: string) => boolean): string[] {
    const neighbors: string[] = [];
    // Generate all single-character mutations...
    // (implementation details omitted)
    return neighbors;
}
 
/*
Visualization:
 
Standard BFS:           Bidirectional BFS:
START ──→ ──→ ──→ END   START ──→    ←── END
    (explores ALL            ↓         ↓
     in between)           Meet in middle!
 
The magic: each direction only goes half the distance.
*/

When to Use Bidirectional BFS

Bidirectional BFS is most effective when: (1) you know both start and end states, (2) the branching factor is high, (3) the path is long, and (4) the graph is roughly symmetric. Not all problems benefit from it, but when applicable, the speedup can be enormous.

Summary: BFS Intuition Established

We've built a strong conceptual foundation for Breadth-First Search without requiring formal graph theory. Here's what we've established:

Key BFS Concepts

•BFS is wave expansion — It explores all positions at distance d before any at distance d+1, just like ripples in a pond.
•Queues enable BFS — The FIFO property ensures nodes are processed in order of their discovery, which corresponds to distance from the start.
•First visit = shortest path — When BFS reaches a node for the first time, it's via the shortest path. No need to search further.
•Visited tracking prevents cycles — By marking nodes when enqueued (not when processed), we avoid infinite loops and duplicate work.
•BFS works on abstract state spaces — "Nodes" can be configurations, words, or any state; "edges" are valid transformations.
•Multi-source BFS handles multiple origins — By starting all sources at once, we efficiently compute distances from the nearest source.
•Bidirectional BFS can dramatically speed up searches — Meeting in the middle reduces exploration exponentially.

Looking Forward:

This intuitive understanding prepares you for two important next steps:

Graph chapters ahead: When we formally study graphs, BFS will be one of the core algorithms. You'll already have the intuition; we'll just formalize the structures.
The next page: We'll see how queue-based processing applies to task scheduling simulation—managing work items that arrive over time and must be processed in order.

Page Complete

You now have deep intuition for BFS: wave-like expansion, the queue's role, shortest path guarantees, and applications from grids to state spaces. This conceptual foundation will prove invaluable when tackling graph algorithms in future chapters.