Breadth-First Search

The Ripple Effect

Imagine dropping a stone into still water. Ripples expand outward in concentric circles, reaching every point at a certain distance before moving to the next ring. This is exactly how Breadth-First Search explores a graph.

BFS explores layer by layer. First, it visits all neighbors at distance 1 from the start. Then all nodes at distance 2. Then distance 3, and so on. This systematic expansion is why BFS is guaranteed to find the shortest path in an unweighted graph—it literally cannot find a farther node before a closer one.

Think of the search as a wave front propagating outward. Every cell the wave touches on its $n$-th expansion is exactly $n$ steps from the origin. No more, no less.

The Queue

The key to BFS is the queue data structure. A queue follows the FIFO principle: First In, First Out. Imagine a line at a coffee shop—the first person in line is the first to be served.

When BFS discovers a neighbor, it adds that neighbor to the back of the queue. When BFS needs to explore a cell, it takes the cell from the front of the queue. This simple rule creates the layer-by-layer behavior.

Consider what would happen if we used the opposite approach—adding to the back but taking from the back (a stack). We would explore one branch as deep as possible before backtracking. That is Depth-First Search, which we cover in the next chapter.

The queue is the heartbeat of BFS. It maintains the frontier of cells waiting to be explored, always in the order they were discovered.

Watch the yellow frontier cells: they always form a ring around the visited (blue) region. The queue shows the order cells will be processed—notice how cells discovered earlier appear at the front.

Why BFS Finds Shortest Paths

Here is the key insight: the first time BFS reaches a cell, it has taken the minimum number of steps to get there.

Why? Because BFS processes cells in order of when they were discovered. If cell A was discovered before cell B, then A will be processed before B. And if A was discovered before B, that means there exists a path to A that is at most as short as any path to B discovered so far.

We can think of it as a proof by contradiction. Suppose BFS reaches cell $C$ for the first time via a path of length $k$. Could there be a shorter path of length $j < k$? If such a path existed, BFS would have discovered $C$ during round $j$ of its expansion, not round $k$. But we said BFS is discovering $C$ for the first time in round $k$, so no shorter path exists.

This guarantee only holds for unweighted graphs—graphs where every edge has the same cost. When edges have different weights, we need Dijkstra's algorithm, which we explore later.

Drag the start (S) and end (E) points to different positions. Add walls by clicking and dragging on empty cells. Watch how BFS always finds the shortest path—the path with the fewest steps.

The Algorithm

Here is BFS in pseudocode:

BFS(graph, start, goal):
    queue ← empty queue
    visited ← empty set
    parent ← empty map
    
    enqueue start to queue
    add start to visited
    parent[start] ← null
    
    while queue is not empty:
        current ← dequeue from queue
        
        if current = goal:
            return reconstruct_path(parent, goal)
        
        for each neighbor of current:
            if neighbor not in visited:
                add neighbor to visited
                parent[neighbor] ← current
                enqueue neighbor to queue
    
    return "no path found"

Let us break this down step by step:

1. Initialize: Create an empty queue to hold cells waiting to be explored. Create a set to track which cells we have already visited. Create a map to remember how we reached each cell (for path reconstruction).

2. Start: Add the starting cell to the queue and mark it as visited.

3. Main loop: While there are cells in the queue, take the front cell (the one discovered earliest). If it is the goal, we are done—trace back through the parent pointers to build the path.

4. Expand: For each neighbor of the current cell, if we have not visited it yet, mark it visited, record that we came from the current cell, and add it to the queue.

5. Termination: If the queue empties and we never found the goal, there is no path.

The algorithm runs in $O(V + E)$ time, where $V$ is the number of vertices (cells) and $E$ is the number of edges (connections between adjacent cells). Each cell is visited at most once, and each edge is examined at most twice (once from each endpoint).

Key Takeaways

• BFS explores in order of distance from the start—all cells at distance 1, then distance 2, and so on
• The queue (FIFO) ensures cells are processed in the order they were discovered
• BFS guarantees the shortest path in unweighted graphs because the first time it reaches any cell is via a minimum-length path
• Every cell is visited at most once, giving BFS linear time complexity