Ripples in a pond

Breadth-First Search

The analogy

🧸 ELI5⚙ Tech

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

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

🎯 Predict modespeed1×

📖 In depth — the full reference

🐍 PythonJS JavaScript

BFS — everything worth knowing

fact	value	note
time / space	O(V + E) / O(V)	each node enqueued once, each edge looked at once (twice if undirected)
data structure	QUEUE — non-negotiable	swap in a stack and it silently becomes DFS
guarantee	first arrival = fewest EDGES	shortest path in unweighted graphs — its defining superpower
mark seen on ENQUEUE	not on dequeue	else a node enters the queue twice via two neighbours — subtle classic bug
path recovery	store parent[child] = node when enqueueing	walk parents backward from the goal
weighted graphs	BFS is NOT enough	fewest edges ≠ cheapest path — Dijkstra (Module 6) fixes this
level tracking	process the queue one ring at a time	for level = len(queue) snapshots — "minimum moves" problems

Python: the canonical BFS

from collections import deque

def bfs(adj, start):
    order = []
    seen = {start}                 # mark on enqueue!
    q = deque([start])
    while q:
        node = q.popleft()          # O(1) — the deque lesson pays off
        order.append(node)
        for nb in adj[node]:
            if nb not in seen:
                seen.add(nb)
                q.append(nb)
    return order
# list.pop(0) here would make BFS itself O(V^2). deque or bust.

PythonJavaScriptHow devs thinkWhere it's used

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?

Practice — write it yourself

🐍 PythonJS JavaScript

bfs_order(adj, start): ripples with a QUEUE (pop from the front, append to the back). Mark seen on enqueue. Return the visit order.

Python 3 · runs in your browser · your draft is saved locally

📝 My notessaved in this browser