ZERO / HERO
Ripples in a pond

Breadth-First Search

The analogy

Drop a stone in a pond. The ripple reaches everything one step away, then everything two steps away, then three. BFS explores a map the same way — all your friends first, then all their friends — which is why the first time it reaches a place, it got there by the shortest route.

Visualizer

Ripples across the map

step 1 / 14
ABCDEFGH

Start at A. A queue holds who to visit next — first in, first out.Queue: A

from collections import deque

def bfs(adj, start):
    seen = {start}
    q = deque([start])
    order = []
    while q:
        v = q.popleft()          # FIFO
        order.append(v)
        for w in adj[v]:
            if w not in seen:
                seen.add(w)
                q.append(w)
    return order
Check yourself

BFS uses which structure?