Depth-First Search & Listener Circles
Tunebox's Circles tab groups friends who are linked to each other — directly, or through a chain of friends — so each circle can share a blend playlist. Finding a circle means following friendships until you run out, which is the natural shape of depth-first search (DFS): go as deep as possible down one path, back up, try the next. The same walk finds loops and puts tasks in a safe order.
Go deep first
Recursion is the most natural way to write DFS: visit a listener, then — before looking at anyone else — visit their first friend, and that friend's first friend, and so on. The call stack remembers where to come back to.
The indentation shows the shape: from Ana down to Ben, down to Dia, dead end, back up to Ana, then across to Cal.
graph = {"ana": ["ben", "cal"], "ben": ["dia"], "cal": [], "dia": []}
order = []
def dfs(name):
order.append(name)
for nxt in graph[name]:
dfs(nxt)
dfs("ana")
print(order)That snippet has no visited set, and it got away with it only because this graph has no loops. Friendships always loop — Ana lists Ben and Ben lists Ana:
graph = {"ana": ["ben"], "ben": ["ana"]}
def dfs(name):
for nxt in graph[name]:
dfs(nxt)
dfs("ana")
print("done")The same walk with an explicit stack
Recursion uses Python's call stack. You can hold that stack yourself — a list you
append to and pop from — and the walk no longer depends on the recursion limit.
Two details make it visit in exactly the recursive order:
- Push neighbours in reverse, so the first-listed one is on top and popped next.
- Check
seenwhen you pop, because a listener may be pushed more than once before its turn comes.
❓ Cross-question — "If the iterative version is safer, why learn recursion?" The recursive version says what DFS is in six lines, and some jobs — like the topological sort below — need work after all of a vertex's neighbours finish, which recursion gives you for free. Switch to a stack when a chain could run thousands deep.
Coming from Java/JS: deep recursion ends in
StackOverflowErrorin Java andRangeError: Maximum call stack size exceededin JS. Python's default limit is much lower — about 1000 frames — and raisesRecursionError.
Connected components
One DFS finds everyone reachable from one listener: that listener's connected component, or circle. To find every circle, loop over all listeners and start a new DFS from each one nobody has visited yet. Step through it:
Order inside a circle doesn't matter here, so this stack marks listeners as it pushes them — each is pushed once, and the reverse-and-check-on-pop details aren't needed. Every listener is visited exactly once across all the searches, so the whole thing is still O(V + E). Cal, with no friends, is a circle of one.
Cycle detection
In an undirected graph, a friendship back to the listener you just came from isn't a loop — every edge is stored both ways. A loop is reaching an already-visited listener by any other edge.
In a directed graph — playlists that include other playlists — it's subtler: reaching a visited node may just mean two routes lead there, like a diamond. This version can't tell the difference:
This diamond has no loop, so it should print False — but it prints True. Fix the check so only a playlist still on the current path counts as a cycle.
The fix is three states — often called colours: white (not visited), grey (on the current path) and black (finished). Meeting a grey node means an edge points back up the path you're on: a cycle. Meeting a black node is harmless.
Topological sort
Tunebox's upload pipeline has steps that depend on others: you can't fingerprint a track before it's transcoded, and nothing is published until it's fingerprinted and has artwork. A graph with no cycles (a DAG) of "must happen before" edges can be put in a topological order — every step after everything it depends on.
DFS gives it almost for free: a step finishes only after everything it leads to has finished. Record each step as it finishes, then reverse the list.
If the graph has a cycle there is no valid order at all — combine this with the grey/black check to report it.
What DFS costs
| Operation | Cost |
|---|---|
| DFS from one vertex | O(V + E) |
| All connected components | O(V + E) — each vertex visited once overall |
| Cycle detection (three colours) | O(V + E) |
| Topological sort | O(V + E) |
| Memory | O(V) — the visited set plus the stack (or call stack) |
Idioms & real-world patterns
A nested function sees its enclosing variables
Defining visit inside the function that uses it lets it mutate seen and
order without passing them down. Rebinding a name (count += 1) needs
nonlocal count first:
graphlib — topological sort in the standard library
graphlib.TopologicalSorter (Python 3.9+) orders a graph given each node's
predecessors, and raises CycleError on a loop:
⚡ Advanced — Kahn's algorithm
A second classic topological sort uses no DFS at all. Count each step's unmet prerequisites (its in-degree); everything at zero is ready. Take one, and lower the count of everything it unlocks — anything reaching zero becomes ready too. Run out of ready steps before placing them all, and the leftovers sit on a cycle. Because you choose which ready step goes next, Kahn's algorithm is the one to reach for when the order has to follow a rule.
🎯 Your turn
Write listener_circles(graph) — the connected groups in Tunebox's undirected
friendship graph (each friendship is listed from both sides, and every listener is a
key). Sort each circle alphabetically, order the circles by their first name, and
give a listener with no friends a circle of their own:
listener_circles({"ana": ["ben"], "ben": ["ana"], "cal": []})→[["ana", "ben"], ["cal"]]listener_circles({})→[]
Hint — loop over the listeners in sorted order; each unvisited one starts a new DFS that collects their whole circle.
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. ✅