BFS has one line people get wrong: where you mark a node visited

Breadth-first search is usually the second graph algorithm anyone learns, and it looks almost too simple: a queue, a loop, a visited set. Most BFS bugs I see come down to one decision in that loop: when you mark a node as visited.

The idea, without code

Drop a stone in a pond. The first ripple reaches everything one step away, the second ripple everything two steps away, and so on. BFS explores a graph the same way. It visits every neighbour of the start node, then every neighbour of those, one layer at a time.

The queue is what keeps the layers in order. It is first-in, first-out, so every node from layer 1 is processed before any node from layer 2 is even looked at. That ordering is also why BFS finds the shortest path in an unweighted graph: the first time it reaches a node is along the fewest possible edges.

The standard version

from collections import deque

def bfs(graph, start):
    visited = {start}          # mark the start as soon as it is queued
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)   # mark on ENQUEUE
                queue.append(neighbour)
    return order

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['B', 'C'],
}
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E']

The bug: marking on dequeue

Here is the version that looks equivalent:

def bfs_buggy(graph, start):
    visited = set()
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        if node in visited:
            continue
        visited.add(node)            # mark on DEQUEUE
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                queue.append(neighbour)
    return order

It returns the same order, so tests pass. Now trace the queue on the graph above.

• A is dequeued. B and C are enqueued. Queue: B, C
• B is dequeued. D and E are enqueued. Queue: C, D, E
• C is dequeued. E isn't visited yet, because it's still waiting in the queue, so it's enqueued again. Queue: D, E, E

E is now in the queue twice. On this graph that costs one wasted loop. On a dense graph a node can be queued once for every edge leading into it. The queue grows toward O(E) instead of O(V), and on a large grid problem that's the difference between passing and a memory or time-limit failure.

The fix is the first version: mark a node visited the moment you put it in the queue, not when you take it out. At that point you've already committed to visiting it, and nothing else should queue it again.

Shortest path is the same loop with a distance map

Once the visited set is right, shortest path in an unweighted graph is a small change. Store each node's distance when you first enqueue it:

def shortest_path_length(graph, start, target):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == target:
            return dist[node]
        for neighbour in graph[node]:
            if neighbour not in dist:        # dist doubles as the visited set
                dist[neighbour] = dist[node] + 1
                queue.append(neighbour)
    return -1

Because the first time BFS reaches a node is along the fewest edges, that distance is final the moment it's written.

When BFS is the wrong tool

• Weighted edges. "Fewest edges" is no longer "cheapest path". Use Dijkstra's algorithm.
• Very wide graphs. BFS holds an entire layer in memory. If a layer can be enormous and you only need to know whether a path exists, depth-first search uses less memory.

The quick recognition rule for interviews: if a problem asks for the shortest path, the fewest steps or the nearest something, and every step costs the same, it's almost always BFS.

Watching it run

The buggy version is easier to see than to read. I built a free step-by-step BFS visualizer. You advance one queue operation at a time, and the matching code line is highlighted in Python, Java, C++, JavaScript, TypeScript or C. Try predicting the queue contents before each step, especially where two nodes share a neighbour.

Disclosure: FaangPrep is my site. The BFS lesson and the other introductory lessons open with no account; the other visualizers are free with an account, and the pattern courses are paid. This post was drafted with AI assistance and reviewed before publishing.