Breadth-First Search

Graphs: lesson 3 of 8

Sweep outward one ring at a time, using a queue.

Lesson 3 of 8 · 6 min

Step 1 of 17

hops0

queue

sub

seen

sub

Start at the live substation. Put it in the queue and mark it seen — hop count 0.

The Idea

Breadth-first search visits everything one hop away, then everything two hops away, and so on. A queue enforces that order: you always take the oldest waiting node. Mark a node the moment you enqueue it, or a shared neighbour gets queued twice.

Real-World Example

Bringing a blacked-out power grid back up. Crews energise the feeders directly attached to the live substation, confirm them, and only then push to whatever those feeders touch. The restored area grows as a widening ring, and no line is ever energised from two directions at once.

The Code

from collections import deque
grid = {"sub": ["a", "b"], "a": ["sub", "c"], "b": ["sub", "c"], "c": ["a", "b", "d"], "d": ["c"]}

def bfs(start):
    seen, order = {start}, [start]
    q = deque([start])
    while q:
        for nb in grid[q.popleft()]:     # oldest node first
            if nb not in seen:
                seen.add(nb)             # mark on enqueue
                order.append(nb)
                q.append(nb)
    return order

print(bfs("sub"))   # ['sub', 'a', 'b', 'c', 'd']

Your turn

Put the steps in the right order.

Dequeue the oldest node and look at its neighbours
Put the start node in the queue and mark it seen
Stop once the queue runs empty
Enqueue each unseen neighbour, marking it seen right away

Mini quiz

1 / 3

Breadth-First Search