BFS — Shortest Path in Unweighted Graphs

When every edge costs the same — a maze where each step is one move, a social network where each connection is one “hop” — the shortest path is simply the one with the fewest edges. Breadth-first search (BFS) finds it, and it’s the mental model everything else extends.

The core idea

Explore the graph in layers, like ripples spreading from a stone dropped in water. First visit the start node, then everything one step away, then everything two steps away, and so on. The moment you reach the target, you’ve reached it by the fewest possible steps — because you exhausted every shorter distance first.

The engine: a FIFO queue

The one data structure that makes this work is a queue (first-in, first-out). You add newly discovered nodes to the back and always process from the front — which guarantees you finish all of layer $k$ before touching layer $k+1$.

BFS(graph, start, target):
    queue   ← [start]
    visited ← {start}
    parent  ← {start: none}

    while queue is not empty:
        u ← queue.pop_front()
        if u == target:
            return reconstruct_path(parent, target)
        for each neighbor v of u:
            if v not in visited:
                visited.add(v)
                parent[v] ← u          # remember how we got here
                queue.push_back(v)
    return "no path"

Two details do the real work:

• visited stops us from processing a node twice (and prevents infinite loops on cycles).
• parent records which node we came from. To recover the actual path, we walk parent pointers backward from the target to the start, then reverse.

Why it’s correct

BFS processes nodes in nondecreasing order of hop-distance. Because the queue is FIFO, a node at distance $d$ is always dequeued before any node at distance $d+1$. So the first time we reach the target, no shorter route exists — if one did, that route’s nodes would have been dequeued earlier. This “first time is the best time” property is exactly what breaks for weighted graphs, and why we need Dijkstra there.

Complexity

With an adjacency list, every node is enqueued once and every edge is examined once (or twice, in an undirected graph):

$$O(V + E) \text{ time}, \qquad O(V) \text{ space}$$

That’s optimal — you can’t find a path without at least looking at the nodes and edges involved.

Where BFS shows up

• Mazes and grids — each cell is a node, each open neighbor an edge.
• Word ladders — cat → cot → cog → dog, one letter at a time.
• Shortest social distance — degrees of separation.
• Bidirectional BFS — run BFS from both ends and meet in the middle; the same trick that powers bidirectional Dijkstra.

The catch

BFS assumes every edge is equal. The moment edges have different costs, the fewest-hops path may not be the cheapest — a 2-hop route of weight $100$ loses to a 5-hop route of weight $10$. For that, you need to process nodes in order of total cost, not hop count. That’s precisely what Dijkstra’s algorithm does — BFS with a priority queue.