Breadth-first search

A rumor starts with one person. In the first hour, everyone that person talks to hears it. In the second hour, everyone they talk to hears it, and so on. The hour in which you first hear it is the number of links in the shortest chain of people from the first person to you. Breadth-first search (BFS) works out that number for every vertex of a graph in which each edge counts as one step: it finds the vertices one edge from the start, then the ones two edges away, then three.

It's the level-order walk of the module on trees, with one change. A tree has only one way down to each node, so level order never meets a node twice. A graph can lead back to a vertex along another edge or around a cycle, so BFS must remember which vertices it has found and never queue one again. In Python, that memory is a dict, dist, from each vertex found so far to its number of steps: w not in dist asks "is w new?" in O(1) on average, and dist[w] is w's distance.

The search puts the start vertex, at distance 0, in a queue, a collections.deque. Then, until the queue is empty, it takes the vertex at the front, and each neighbor of it that is new gets that vertex's distance plus 1 and joins the back of the queue.

from collections import deque


def bfs(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in dist:
                dist[w] = dist[v] + 1
                queue.append(w)
    return dist


graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C", "F"],
    "E": ["C", "F"],
    "F": ["D", "E"],
    "G": [],
}
print(bfs(graph, "A"))
print(bfs(graph, "G"))

{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
{'G': 0}

G has no edges, so the search from A never gets there: G is unreachable from A, and has no distance. The search from G finds only G itself.

Why the first visit is the shortest

The queue holds the vertices in rings around the start: the ones at distance 1, then the ones at distance 2, and so on. All the vertices at distance d leave the queue before any at distance d + 1, and the neighbors they add get d + 1, at the back. So vertices leave in order of distance. When BFS first reaches w from v, every vertex nearer the start than v has already left the queue, and none of them had an edge to w, or w would have been found sooner. So there is no shorter way to w, and its distance never needs to change. D is found from B, at 2. C finds it again, also at 2, but D is already in dist and is skipped.

Why it needs the visited check

Without the if w not in dist check, a vertex joins the queue again every time it's reached. In a triangle, each vertex sends the other two back into the queue, forever:

from collections import deque

graph = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}
queue = deque(["A"])
taken = []
for _ in range(10):
    v = queue.popleft()
    taken.append(v)
    for w in graph[v]:
        queue.append(w)
print(taken)
print(len(queue), "waiting")

['A', 'B', 'C', 'A', 'C', 'A', 'B', 'B', 'C', 'A']
11 waiting

This loop stops only because it was told to stop after 10 rounds. As while queue:, it would never end: each round takes one vertex out and puts two in. Mark a vertex when it joins the queue, as dist[w] = ... does, rather than when it leaves: then each vertex joins once, however many edges lead to it.

On a grid

A maze on a grid is a graph without an adjacency list. Each open cell (r, c) is a vertex, and its neighbors are the open cells above, below, left and right of it, worked out when needed. Cells outside the grid and walls (#) are skipped:

from collections import deque


def steps(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    dist = {start: 0}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if (r, c) == goal:
            return dist[(r, c)]
        for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                queue.append((nr, nc))
    return -1


maze = [
    "...#....",
    ".#.#.##.",
    ".#...#..",
    ".####.##",
    "......#.",
]
print(steps(maze, (0, 0), (0, 7)))
print(steps(maze, (0, 0), (4, 5)))
print(steps(maze, (0, 0), (4, 7)))

11
9
-1

The search stops as soon as the goal leaves the queue. The bottom right corner is walled in, so the queue runs empty first, and -1 says the goal can't be reached.

What it costs

Each vertex joins the queue at most once and leaves it once, O(1) each with a deque, and each edge is looked at once (from both of its ends, if it's undirected): O(V + E) time, and O(V) memory for dist and the queue. A grid of R rows and C columns has R·C cells with at most 4 neighbors each: O(R·C).

Two Python mistakes keep the answers right and ruin the cost:

• A list of visited vertices. (r, c) not in visited on a list compares with every cell found so far: O(V) for each check, O(V²) in all. A maze with 45,000 open cells then takes billions of comparisons. Use a set or a dict.
• A list as the queue. queue.pop(0) moves every item behind the first one: O(n) for each pop. deque.popleft() is O(1).

The path, not just its length

To get the path itself, remember where each vertex was found from, in a dict came_from: came_from[w] = v when w joins the queue, and came_from[start] = None. At the goal, follow came_from back, one vertex at a time, until you reach the start, collecting the vertices on the way. Then reverse the list. Each vertex was found from a vertex one step nearer the start, so the path is a shortest one.