BFS Explained Visually: Why It Finds the Shortest Path

"Use BFS for shortest paths" is one of those rules that gets repeated until nobody remembers why it is true. It is true for a specific reason, the reason is one sentence long, and an interviewer who asks "why does that give the shortest path?" is asking for exactly that sentence.

The problem it solves

You have a graph — nodes and edges, no weights — and you want the fewest edges from one node to another. Fewest moves on a board. Fewest clicks between pages. Fewest word changes between two words.

Trying every path is exponential and pointless, because the vast majority of paths revisit nodes. What you want is to reach each node once, and to reach it the cheapest way the first time.

The intuition

BFS explores in rings. Visit the start. Then everything one edge away. Then everything two edges away. Then three.

Here is the guarantee, and it is the whole answer to "why shortest":

A node is first reached on the ring whose distance it belongs to, and that first arrival is the shortest one.

Why? Because the queue is processed in arrival order and each node adds its neighbours to the back. Everything at distance d is dequeued before anything at distance d+1 is dequeued, so the first time a node is discovered, it was discovered from a node at the smallest possible distance. There is no shorter route left to find, which is why marking a node as visited on discovery can never throw away a better path.

Swap the queue for a stack and the property vanishes. Depth-first search plunges down one branch to the end, so the first time it reaches a node may well be by a long way round. DFS answers "is there a path"; BFS answers "what is the shortest path".

Watch it run

Watch the frontier spread outward from the start — one complete ring at a time. Coral is the node being processed; the nodes turning violet are the ones whose distance is now settled.

The shape to remember is the ripple. Everything at the current distance is dealt with before anything further out is touched, and that ordering is the proof.

The code

from collections import deque

def shortest_path(graph, start, goal):
    """Fewest-edges path as a list of nodes, or [] if unreachable."""
    if start == goal:
        return [start]

    parent = {start: None}              # doubles as the visited set
    queue = deque([start])

    while queue:
        node = queue.popleft()          # popleft, not pop: FIFO is the point
        for neighbour in graph[node]:
            if neighbour in parent:     # already discovered, and never worse
                continue
            parent[neighbour] = node
            if neighbour == goal:
                path = [goal]           # walk the parents back to the start
                while parent[path[-1]] is not None:
                    path.append(parent[path[-1]])
                return path[::-1]
            queue.append(neighbour)
    return []

graph = {
    "a": ["b", "c"],
    "b": ["a", "d"],
    "c": ["a", "d", "e"],
    "d": ["b", "c", "f"],
    "e": ["c", "f"],
    "f": ["d", "e"],
}

print(shortest_path(graph, "a", "f"))   # ['a', 'b', 'd', 'f']
print(shortest_path(graph, "a", "a"))   # ['a']

Two details carry the weight. popleft() is what makes this BFS at all — pop() would turn the same function into DFS and silently break the shortest-path claim. And parent is doing double duty: it records how each node was reached and serves as the visited set, so there is no second dictionary to keep in sync.

Where it goes wrong

• Marking visited on dequeue instead of on discovery. A node with several neighbours gets pushed onto the queue many times before it is first processed. The answer stays correct, but the queue can blow up to O(V·E) entries. Mark it when you push it.
• Using a list as the queue. list.pop(0) shifts every remaining element, turning each dequeue into O(n) and the whole search into O(V²). collections.deque pops from the left in constant time.
• Claiming shortest paths on a weighted graph. BFS counts edges, not cost. Once edges have different weights, fewest-edges and cheapest are different questions and you need Dijkstra. Say which one the graph is.
• Forgetting the start-equals-goal case. Without the early return, the loop looks for a way back to the start and may return a full cycle instead of a zero-length path.
• Assuming the path is unique. BFS returns a shortest path. In the graph above, a → c → d → f and a → c → e → f are also three edges. Which one you get depends on neighbour order, so never assert a specific route in a test — assert its length.

The complexity

Time: O(V + E). Every node is enqueued at most once and every edge is examined at most once from each end.

Space: O(V). The queue plus the visited/parent map. The queue's peak size is the widest ring in the graph, which on a broad, shallow graph is close to V — worth mentioning, because it is the case where BFS costs more memory than DFS.

How to say it in an interview

Do not start with the queue. Start with the guarantee:

"BFS visits nodes in order of distance from the source, because a FIFO queue drains everything at distance d before anything at d+1. So the first time I discover a node, I have discovered it by a shortest route — which is why marking it visited immediately is safe. That gives O(V + E) time and O(V) space. I keep a parent pointer per node so I can rebuild the path rather than just its length. This is for unweighted edges; with weights the equivalent is Dijkstra, because fewest edges stops meaning cheapest."

Then write it, and say "popleft" out loud when you type it. That one word is the difference between this algorithm and a different one.