Graphs & the Follow Graph
Tunebox listeners follow each other. Ana follows Ben, Ben follows Cal, and Cal follows Ana right back — that last follow closes a loop. A list can't hold that, and neither can a tree, because trees never loop back. What you need is a graph: the most general structure there is, and the shape behind every "people you may know", every route planner and every package manager.
Vertices and edges
A graph is two things. Vertices (also called nodes) are the things — here, listeners. Edges are the connections between them — here, follows. The rawest way to write a graph down is exactly how Tunebox receives it: one row per follow.
That's an edge list. It's compact and cheap to append to — but to answer "who does Ben follow?" you have to scan every row. Hold that thought.
Directed or undirected
A follow has a direction: Ana following Ben says nothing about Ben following Ana. That makes the follow graph directed — every edge is an arrow.
Some relationships have no direction. "These two songs sound alike" works both ways, so that graph is undirected. You store an undirected edge by recording it from both ends:
similar = {}
for a, b in [["glow", "drift"], ["drift", "aura"]]:
similar.setdefault(a, []).append(b)
similar.setdefault(b, []).append(a)
print(len(similar["drift"]))Weighted edges
Sometimes an edge carries a number — a distance, a price, a strength. Smooth radio
scores each crossfade by how jarring it sounds, so its edges are weighted:
["glow", "drift", 4] means that transition costs 4. It's the same edge list with
one more column.
You'll lean on weights in the Dijkstra lesson. For now, notice that nothing about the vertices changed — only what an edge knows.
Three ways to store a graph
The edge list is one. The other two are built for answering questions fast.
An adjacency matrix is a V × V grid: row i, column j holds 1 if listener
i follows listener j.
Notice [[0] * n for _ in names] — not the shorter-looking alternative:
matrix = [[0] * 3] * 3
matrix[0][1] = 1
print(matrix[2][1])An adjacency list gives every vertex its own list of neighbours. In Python that's a dict of lists — the shape this whole section uses:
Here's what each choice costs, for V vertices and E edges:
| Operation | Edge list | Adjacency matrix | Adjacency list |
|---|---|---|---|
| Memory | O(E) | O(V²) | O(V + E) |
| Does a follow b? | O(E) | O(1) | O(out-degree of a) |
| Everyone a follows | O(E) | O(V) | O(out-degree of a) |
| Add a follow | O(1) | O(1) | O(1) |
❓ Cross-question — "The matrix answers 'does a follow b?' in O(1). Why not always use it?" Because of the O(V²). Tunebox with a million listeners would need a trillion cells, almost all zero — people follow hundreds of accounts, not millions. Real networks are sparse (E is far below V²), and an adjacency list only pays for edges that exist. Reach for a matrix when the graph is small or genuinely dense.
Coming from Java/JS: an adjacency list is a
Map<String, List<String>>in Java and aMap(or plain object) of arrays in JS. Python's dict of lists is the same idea with less ceremony.
Degree and in-degree
A vertex's degree is how many edges touch it. In a directed graph it splits in two: out-degree (how many you follow) and in-degree (how many follow you).
Out-degree is free in an adjacency list — it's len(graph[name]). In-degree isn't
stored anywhere: the arrows pointing at Cal live in other people's lists. So you
count them with one pass over every list. Step through it:
That's O(V + E): every key once, every edge once. (In an undirected graph, where every edge is stored from both ends, out-degree and in-degree are the same number.)
Building an adjacency list from an edge list
Follows arrive as rows; features want a dict. This conversion is the most common graph code you'll write, and it has one trap. This version looks right:
KeyErrorCal follows nobody, so this should print []. Instead it crashes with a KeyError. Fix build so every listener in the graph has a key.
Every vertex needs a key, even one with no outgoing edges. Otherwise the first algorithm that walks to Cal and asks for his neighbours falls over.
Idioms & real-world patterns
defaultdict(list) — no setdefault needed
collections.defaultdict creates the missing value for you on first access:
It has a sharp edge, though — reading a missing key creates it too:
from collections import defaultdict
graph = defaultdict(list)
graph["ana"].append("ben")
if graph["zoe"]:
print("zoe follows someone")
print(len(graph))Sets while building, sorted lists at the end
Duplicate rows happen — a double-tap, a replayed event. Collect neighbours in a
set so a repeated follow counts once, then convert to sorted lists so the output
is deterministic. (Sets also aren't JSON, so they can't leave the function.)
⚡ Advanced — implicit graphs
Not every graph is stored. A grid, a board game, or "every playlist one edit away" is a graph whose neighbours you compute on demand:
Every algorithm in this section works unchanged on a graph like this — all it ever needs is a way to ask "what's next to this?".
⚡ Advanced — density decides the representation
A directed graph without self-loops has at most V × (V − 1) edges. Density is E divided by that maximum. Social graphs sit very close to 0, which is why they live in adjacency lists. A matrix only earns its memory as density climbs — "how similar is every song to every other song" is a full grid, and there every cell holds a real number.
🎯 Your turn
Write build_follow_graph(follows) — turn Tunebox's follow rows into an adjacency
dict. Every listener on either side of a row is a key; their list is who they
follow, sorted, with a repeated follow counted once:
build_follow_graph([["ana", "ben"], ["ana", "cal"], ["ben", "cal"]])→{"ana": ["ben", "cal"], "ben": ["cal"], "cal": []}build_follow_graph([])→{}
Hint — collect into sets with setdefault, make sure the followed listener gets
a key too, then sort each set on the way out.
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. ✅