BFS — Exploring Level by Level

What is it? #

Breadth-first search explores everything one step away, then everything two steps away, and so on. It moves outwards in rings.

It uses a queue. Take a node, add its unvisited neighbours to the back, repeat. Because the queue is first-in-first-out, closer nodes are always handled before farther ones.

That ordering gives you something valuable: the first time BFS reaches a node, it has done so by the fewest possible edges. In an unweighted graph, that is the shortest path.

The cost is memory. BFS holds an entire level in the queue at once, which on a wide graph can be a lot of nodes.

Think of it like this #

A rumour spreading through an office. First everyone you speak to directly hears it. Then everyone they speak to. Then the next ring.

If you want to know the minimum number of people the rumour passed through to reach someone, this ring-by-ring order gives you exactly that.

Simple example #

In a social network, find the degrees of separation between two people. In a grid, find the shortest route from one cell to another avoiding walls. Both are the same algorithm.

Code #

from collections import deque

graph = {
    "ravi":  ["anita", "kiran"],
    "anita": ["ravi", "sam"],
    "kiran": ["ravi"],
    "sam":   ["anita", "priya"],
    "priya": ["sam"],
}


def bfs_order(graph, start):
    seen, queue, order = {start}, deque([start]), []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)          # mark on enqueue, not on dequeue
                queue.append(neighbour)
    return order

print(bfs_order(graph, "ravi"))
# ['ravi', 'anita', 'kiran', 'sam', 'priya']


def shortest_path(graph, start, goal):
    if start == goal:
        return [start]
    seen = {start}
    queue = deque([(start, [start])])        # node plus the path taken to it
    while queue:
        node, path = queue.popleft()
        for neighbour in graph[node]:
            if neighbour in seen:
                continue
            if neighbour == goal:
                return path + [neighbour]    # first arrival is the shortest
            seen.add(neighbour)
            queue.append((neighbour, path + [neighbour]))
    return None

print(shortest_path(graph, "ravi", "priya"))     # ['ravi', 'anita', 'sam', 'priya']


# BFS on a grid — the classic maze problem
def shortest_grid_path(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start, 0)])
    seen = {start}
    while queue:
        (r, c), steps = queue.popleft()
        if (r, c) == goal:
            return steps
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append(((nr, nc), steps + 1))
    return -1


maze = [
    [".", ".", "#"],
    ["#", ".", "."],
    [".", ".", "."],
]
print(shortest_grid_path(maze, (0, 0), (2, 2)))   # 4

BFS from "ravi"

level 0:  ravi
level 1:  anita, kiran
level 2:  sam
level 3:  priya

How it works #

The queue holds nodes waiting to be explored. popleft takes the oldest, which is always the closest unexplored node.

Marking nodes as seen when you enqueue them — not when you dequeue them — matters. Otherwise the same node can be added several times before it is processed, wasting work and potentially producing wrong distances.

shortest_path carries the path alongside each node. Because BFS reaches every node by the fewest edges, the first time you encounter the goal you already have the shortest route. There is no need to keep searching.

For memory efficiency, real implementations store a parent map instead of a full path per node, then reconstruct the path backwards at the end.

The grid version treats each cell as a node with up to four neighbours. Walls are simply cells you do not enqueue. This is the standard solution for maze problems, flood fill, and shortest routes on tiles.

The complexity is O(V + E): each node is enqueued once and each edge examined once. Memory is O(V) in the worst case, since a level can contain most of the graph.

BFS gives shortest paths only when every edge costs the same. With weights, a shorter route may use more edges, and you need Dijkstra's algorithm instead.

Real-world use #

LinkedIn-style "2nd degree connection" labels are BFS. So is finding the smallest number of hops between two servers, or the shortest route on a metro map where every stop counts equally.

Web crawlers use BFS to explore a site level by level, which keeps the crawl broad rather than diving deep into one branch.

In games and simulations, BFS on a grid handles pathfinding, area-of-effect and flood fill. Image processing uses the same idea to find connected regions of similar pixels.

Peer-to-peer and network discovery protocols use bounded BFS: explore outwards but stop after N hops, which is exactly the "time to live" field in a network packet.

Common mistakes #

• Using a list with pop(0) instead of a deque, making the queue O(n) per operation.
• Marking nodes visited on dequeue instead of enqueue, causing duplicates.
• Using BFS on a weighted graph and expecting shortest paths — use Dijkstra.
• Storing a full path per queued node on a large graph, exhausting memory.
• Forgetting boundary checks in grid BFS and reading outside the grid.

Practice #

Write a function that returns everyone within two connections of a given person in the friends graph. Then modify the grid BFS to return the actual route as a list of cells, not just the number of steps, using a parent map.