Breadth-First Search & Degrees of Separation
Ana opens Dia's profile and Tunebox says 2nd-degree connection — Ana follows someone who follows Dia. Working that out means exploring the follow graph outward from Ana: everyone one hop away, then everyone two hops away, until Dia turns up. That ripple is breadth-first search (BFS), the algorithm behind degrees of separation, "people you may know", web crawlers and maze solvers.
Exploring level by level
Picture a stone dropped in water. Ring 0 is Ana. Ring 1 is everyone she follows. Ring 2 is everyone they follow — minus anyone already in an earlier ring.
Three rings: ana, then ben cal, then dia eli. Eli follows Ana back, but Ana is
already seen, so the walk doesn't go round in circles.
The queue
Keeping explicit rings works, but classic BFS uses a single queue — first in, first out. Discoveries join the back; you explore from the front. Everything found earlier (closer) is explored before anything found later (further), so the rings fall out on their own.
from collections import deque
queue = deque(["ana"])
queue.append("ben")
queue.append("cal")
print(queue.popleft(), queue.pop())❓ Cross-question — "Why
deque? A list hasappendandpop(0)." It does, butlist.pop(0)shifts every remaining item one place left — O(n) per call — so BFS over a big graph quietly turns quadratic.deque.popleft()is O(1).
Coming from Java/JS:
dequeplays the role of Java'sArrayDequeused as aQueue(offer/poll). In JS,array.shift()has the same O(n) cost aspop(0); Python ships the fix in the standard library.
The visited set
Graphs have cycles and shared neighbours, so the same listener can be discovered more than once. A visited set makes sure each one is queued once — but when you mark them matters. This version marks listeners as they leave the queue:
Each listener should appear once, but Dia appears twice. Fix where the visited set is updated.
Mark on enqueue, not on dequeue. Then every vertex enters the queue exactly once.
Shortest paths in an unweighted graph
Here's BFS's superpower. Because it explores ring by ring, the first time it
reaches a listener is along a route with the fewest possible hops. So a dist dict
filled in at discovery holds shortest distances — and doubles as the visited set.
Step through it:
Dia is reachable two ways — directly, and the long way through Ben and Cal. BFS
records 1, because the direct follow is found in ring 1, before the long way round
can get there.
❓ Cross-question — "Why not depth-first search? It visits everything too." It does, but DFS charges down one branch first, so the first route it finds to Dia might be the long one. Only BFS's ring-by-ring order makes "found first" mean "fewest hops".
Reconstructing the path
A distance says how far. To show how — "Ana → Cal → Eli" — record a parent pointer for every discovery: who you were exploring when you found them.
Each listener points back one step toward Ana along a shortest route. Walking those pointers from the goal gives the route backwards, so reverse it at the end:
Unreachable listeners
Follows are one-way, so some listeners simply can't be reached. BFS needs no special code for that: the queue runs dry, and they never get a distance.
from collections import deque
graph = {"ana": ["ben"], "ben": ["ana"], "cal": ["ana"]}
dist = {"ana": 0}
queue = deque(["ana"])
while queue:
name = queue.popleft()
for nxt in graph[name]:
if nxt not in dist:
dist[nxt] = dist[name] + 1
queue.append(nxt)
print(dist["cal"])What BFS costs
| Operation | Cost |
|---|---|
| Full BFS from one listener | O(V + E) — each vertex queued once, each edge checked once |
| Memory (queue + visited) | O(V) |
deque.append / deque.popleft |
O(1) |
list.pop(0) — the slow way |
O(n) |
| Distance lookup afterwards | O(1) |
Idioms & real-world patterns
Stop as soon as you've found the goal
If you only care about one listener, return the moment you discover them — there's no need to explore the rest of Tunebox:
graph.get(name, []) is the other habit worth stealing: a listener with no key
simply follows nobody, instead of crashing the search.
One whole ring at a time
When you need to act per level — "everyone exactly two hops away" — drain the queue
in batches of len(queue). Items added during the batch wait for the next one:
⚡ Advanced — why BFS's distances are guaranteed shortest
At every moment the queue holds some listeners at distance d, followed only by listeners at distance d + 1 — never anything else. It starts true (just the start, at 0), and every pop of a d can only append d + 1s behind it. So listeners leave the queue in non-decreasing distance order, and the first discovery of anyone comes from the earliest possible ring. That invariant is exactly what breaks once edges carry different weights — which is the Dijkstra lesson's starting point.
⚡ Advanced — bidirectional BFS
On a huge graph, run two searches — one out from the start, one back from the goal — and stop when their frontiers meet. With every listener following about b others and the goal d hops away, one search touches roughly b^d listeners; two half-depth searches touch roughly 2·b^(d/2). For b = 200 and d = 4 that's 80,000 instead of 1.6 billion. (The backward search needs follows reversed: who follows whom.)
🎯 Your turn
Write degrees_between(graph, start, goal) — the fewest hops from start to goal
following the arrows of the follow graph, 0 if they're the same listener, and -1
if there's no route. A listener with no key follows nobody:
degrees_between({"ana": ["ben"], "ben": ["cal"], "cal": []}, "ana", "cal")→2degrees_between({"ana": ["ben"], "ben": [], "cal": []}, "ana", "cal")→-1
Hint — BFS with a deque, and a hops dict that records each listener's distance
the first time you see them — it's your visited set too.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of the app is built. ✅