60The graph — the structure that models everything

In Chapter 59 we built the trie — a tree whose very shape is the letters of a word. Every structure in this volume so far has had a fixed skeleton. A line, a grid, a tree that only ever branches downward. The graph throws that skeleton away. It keeps the barest idea of structure: a set of nodes and a set of edges between them. That minimalism is exactly why it swallows everything. Maps, friendships, web links, git history, the tasks a build must run in order are not like graphs, they are graphs. Vol 3 already walked one, running BFS and DFS on it. Here we build the thing itself, from memory up. We chase the question those walks quietly assumed an answer to — how does a web of relationships actually sit inside a machine whose memory is one flat line of bytes? By the end we'll take a real problem and name its nodes and edges. Then we pick one of two storage layouts, the move that separates fluent from lost, and it decides whether the thing fits in RAM at all.

Before the definition, look at something you touched today. Your phone's map app found a route because intersections are nodes and roads are edges. Your group chat is people as nodes and "can message" as edges. When pip installs a package, it reads a graph of "needs this first" and works out a safe order. None of these were designed to look alike. But the machine stores and walks them with one structure and one set of algorithms, and that shared machinery is the payoff we're chasing.

01Two sets — and suddenly everything is one shape

Let's start with the definition, because it's almost insultingly small. A graph is a set of nodes — also called vertices, the things — and a set of edges, the connections between pairs of things. That's the whole contract. The definition says nothing about what the things are, so anything can be a node. A city, a person, a web page, a commit, a chemical, a state of a game. Watch what that buys you. Cities-and-roads, people-and-friendships, pages-and-links, tasks-and-"must-come-before" are not like graphs, they are graphs: same structure, same code.

Edges come in two flavours you'll keep meeting. An undirected edge is a two-way street, like Ada ⇄ Bex: if she's your friend, then you're hers too. A directed edge points only one way, so page A → page B, and "socks before shoes" is never "shoes before socks." An edge may also carry a weight, a number on the connection: minutes of drive, cost of a flight, or strength of a bond. Four words — node, edge, direction, weight — let you describe a road atlas, a social network, and a compiler's build order in one breath. The vocabulary was Vol 3's job, and here we ask the brutally practical question it skipped past. A machine can't store a drawing; it can only store bytes. So how does a graph actually sit in RAM?

So picture a tiny road map: Oslo, Bergen, and Trondheim, with roads Oslo–Bergen and Oslo–Trondheim. The machine doesn't care where you drew the dots or how long you made the lines. All it needs to answer later is one question: who is connected to whom. That is adjacency — the list of each node's direct neighbours — and it's the only thing worth storing. Throw the drawing away and keep the neighbours, and you've turned a picture into something a flat line of bytes can hold.

There are exactly two honest ways to write adjacency down, and they sit at opposite ends of a memory tradeoff. The first spends nothing on connections that don't exist. →

02The adjacency list — pay only for the edges that exist

Let's build the thrifty one first. The adjacency list is the layout in the figure above: for each node, keep a list of its neighbours. In Python that's a dict-of-lists. It's a hash table (the dict, from Vol 1) whose values are dynamic arrays (the array we built earlier this volume). To find node 2's neighbours you hash the key 2, land on its slot, and read the list. The neighbours are right there. To store the whole graph you spend one dict entry per node, plus one reference slot for every edge-endpoint. Count it: V nodes and E undirected edges cost V + 2E slots, because each edge is written at both of its ends. That's O(V + E) space — you pay only for connections that are real.

Let's make V + 2E concrete with four friends: Ada, Bex, Cy, and Dot. Say the friendships are Ada–Bex, Ada–Cy, Bex–Cy, and Cy–Dot, so V = 4 and E = 4. Now write each neighbour list: Ada → [Bex, Cy], Bex → [Ada, Cy], Cy → [Ada, Bex, Dot], Dot → [Cy]. Count the references: 2 + 2 + 3 + 1 = 8, which is exactly 2E. Add the four dict entries and the graph costs 12 slots, and every one of them stands for a friendship that really exists.

One honest footnote to V + 2E: that's the undirected bill. A directed edge is written at only one end — its source — so it costs a single slot, not two. Turn those same four friendships into one-way "follows" and the endpoint count drops to V + E, which is 4 + 4 = 8 slots instead of 12. The rule of thumb is simple: undirected doubles, directed doesn't. The layout itself doesn't care which — it just stores whatever neighbours you hand it.

import sys
graph = {                    # a hash table (Vol1) whose values are dynamic arrays
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2],
}
sys.getsizeof(graph)         # -> 224   the dict itself: 4 keys in a hash table
sys.getsizeof(graph[2])      # -> 88    node 2's list: 56-B header + 8 B per ref slot

Line by line: graph is the entire structure, a dict whose four keys are the nodes and whose four values are neighbour lists. getsizeof(graph) returns 224 bytes. That's the hash table's own machinery for four keys (Vol 1's sparse-table overhead), and crucially it does not include the lists. getsizeof measures one object, not what it points at. getsizeof(graph[2]) is 88 bytes: a list's ~56-byte header plus 8 bytes for each neighbour reference. A real run measured a marginal 47 B per undirected edge once list over-allocation is amortised in. The headline: nothing here scales with V². It scales with the edges you actually have.

So the list is thrifty. Why would anyone ever choose the other layout — the one that reserves a box for every possible connection in the universe? Because it buys something the list can't. →

03The adjacency matrix — a box for every possible edge

Now the other layout, the extravagant one. The adjacency matrix is a V×V grid of 0s and 1s, where cell [i][j] = 1 means "there's an edge from i to j." Memory is one-dimensional (Vol 1), so this grid is flattened row-major, exactly like the matrix chapter earlier this volume. Row 0's V cells come first, then row 1's V cells, laid end to end. Cell (i, j) lives at base + (i·V + j)·slot. That flat formula is the whole point. To ask "is i linked to j?" the machine does one multiply-add and reads one cell — O(1), no list to scan. The adjacency list makes you walk a neighbour list to answer that (O(degree)). The matrix answers it in a single indexed jump.

A quick word on degree, since it's what that cost is measured in: a node's degree is just how many neighbours it has. In our four-friend graph Cy has degree 3 and Dot has degree 1. Scanning a neighbour list is O(degree) because you touch each of those neighbours exactly once. The matrix skips the scan entirely — it jumps straight to cell (i, j) and reads the answer in one step.

Let's plug a real coordinate into base + (i·V + j)·slot. Take our six-node graph and ask "is node 2 linked to node 4?" Here i = 2, j = 4, and V = 6, so the offset is 2·6 + 4 = 16 cells past the start. You can check that by hand: row 0 fills cells 0–5, row 1 fills 6–11, row 2 fills 12–17, so cell (2, 4) sits at 12 + 4 = 16. One multiply, one add, one read — that's the O(1) the matrix is buying you.

The catch is the flip side of the same coin. The grid has V² cells whether or not the edges exist, so it costs O(V²) space always, sparse or not. And in pure Python a "cell" isn't a bit. A list-of-lists stores an 8-byte reference per cell (measured: 8.06 B/cell). A true packed matrix (NumPy uint8, or a stdlib bytearray) drops that to 1 byte, and a bit-packed one to 0.125 B/cell. But even at one bit, V² grows quadratically and swallows the list long before your data does.

Here are the two layouts of the same six-node graph, side by side, so flip the toggle and watch the memory story change as you do. The list writes down only the edges that exist, growing one honest step at a time as connections appear. The matrix reserves all V² boxes the instant you create it, whether or not a single one of those edges is ever filled in.

For six nodes the gap is 20 versus 36 — a shrug. But watch what happens to that gap as the graph grows and stays sparse, the way every real graph does. →

04Sparse or dense — the choice that decides whether it fits in RAM

This isn't an academic preference; it's the difference between fitting in memory and not. Real graphs are overwhelmingly sparse: a person has hundreds of friends, not millions; a web page links to dozens of pages, not billions; a road touches a handful of intersections. For sparse graphs, V+2E and V² live in different universes. Take a million users, each with about ten friends, and just count the storage:

V, deg = 1_000_000, 10
E = V * deg // 2            # 5,000,000 undirected edges

cells = V * V              # 1,000,000,000,000   (a trillion)
slots = V + 2 * E          #        11,000,000   (eleven million)
cells // slots             # -> 90909   the matrix is ~90,909x bigger
cells // 8                 # -> 125,000,000,000 bytes = 125 GB  at 1 bit/cell

Line by line: V and deg fix the scale, and E halves the endpoint count because each friendship is one shared edge. So cells is V², a trillion boxes, while slots is only V+2E, or eleven million. That puts the ratio at 90,909×. And cells // 8 is the kindest possible matrix, one bit per cell, yet it still needs 125 GB (≈116 GiB) just to record who-knows-whom. The adjacency list of the same graph is about 88 MB at 8 bytes a slot, or 44 MB packed. One representation needs a data-centre, the other fits in a laptop. Same graph.

Slide the edge count on a fixed 16-node graph and watch the two costs pull apart. The matrix line never moves, because it reserved V² up front. The list rises one honest step per edge. They only meet at the far right, where the graph is complete and every pair is connected. That's the one regime where the matrix's fixed price is finally fair.

How many edges does "complete" actually mean? Every node connects to every other, so a V-node graph tops out at V(V−1)/2 undirected edges. For our 16-node graph that's 16·15/2 = 120 edges — the far-right end of the slider, and no further. A graph is dense when its real edge count sits near that ceiling, and sparse when it hugs the floor of a handful per node. That one ratio — edges over the V² the matrix reserves — is the whole basis for the choice coming next.

INPUTimport sys
from collections import defaultdict

edges = [(0, 1), (0, 2), (1, 2), (2, 3), (2, 4)]   # 5 nodes, 5 undirected edges

# 1 - the literal: you already know the whole graph
literal = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3, 4], 3: [2], 4: [2]}

# 2 - from an edge list: the form data actually arrives in
g = defaultdict(list)
for u, v in edges:
    g[u].append(v)
    g[v].append(u)                      # BOTH ends - undirected
built = {k: g[k] for k in sorted(g)}

# 3 - the matrix alternative: a box for every possible pair
V = 5
M = [[0] * V for _ in range(V)]         # NOT [[0]*V]*V - see the tripwires
for u, v in edges:
    M[u][v] = M[v][u] = 1

print("literal == built from edges?", literal == built)
print("neighbours of 2 :", built[2], " (list: walk it, O(degree))")
print("is 2 linked to 4?", M[2][4], "   (matrix: one multiply-add, O(1))")
print("is 0 linked to 4?", M[0][4], "   (a miss costs exactly the same)")
print("degrees         :", {n: len(built[n]) for n in built})

def total(dct):                                    # the dict AND what it points at
    return sys.getsizeof(dct) + sum(sys.getsizeof(v) for v in dct.values())

def matbytes(m):
    return sys.getsizeof(m) + sum(sys.getsizeof(row) for row in m)

print("\n5-node graph, measured:")
print("  adjacency dict :", total(built), "bytes")
print("  matrix (lists) :", matbytes(M), "bytes")

# now the real question: 1000 nodes, 3000 edges - a sparse graph, like every real one
import random
random.seed(7)
N, E = 1000, 3000
big = defaultdict(list)
seen = set()
while len(seen) < E:
    a, b = random.randrange(N), random.randrange(N)
    if a != b and (a, b) not in seen and (b, a) not in seen:
        seen.add((a, b))
        big[a].append(b)
        big[b].append(a)
for i in range(N):
    big[i]                                  # touch every node so isolated ones exist
big = dict(big)

BM = [[0] * N for _ in range(N)]
for a, b in seen:
    BM[a][b] = BM[b][a] = 1

ad, mb = total(big), matbytes(BM)
print("\n1000 nodes / 3000 edges:")
print("  adjacency dict : %10d bytes" % ad)
print("  matrix (lists) : %10d bytes" % mb)
print("  matrix / dict  : %10.1fx" % (mb / ad))
print("  endpoints stored:", sum(len(v) for v in big.values()), "= 2E")
print("  matrix cells    :", N * N, "of which", 2 * E, "are 1 -> %.2f%% used" % (100 * 2 * E / (N * N)))

OUTPUTliteral == built from edges? True
neighbours of 2 : [0, 1, 3, 4]  (list: walk it, O(degree))
is 2 linked to 4? 1    (matrix: one multiply-add, O(1))
is 0 linked to 4? 0    (a miss costs exactly the same)
degrees         : {0: 2, 1: 2, 2: 4, 3: 1, 4: 1}

5-node graph, measured:
  adjacency dict : 664 bytes
  matrix (lists) : 600 bytes

1000 nodes / 3000 edges:
  adjacency dict :     157688 bytes
  matrix (lists) :    8064856 bytes
  matrix / dict  :       51.1x
  endpoints stored: 6000 = 2E
  matrix cells    : 1000000 of which 6000 are 1 -> 0.60% used

You now know which to store. But there's a second, quieter reason the list usually wins that has nothing to do with byte counts — and one clever repacking that makes it win even harder. This is where the metal speaks. →

05How the metal feels a graph — pointer-chasing, and the CSR trick

Two structures with the same Big-O can run at wildly different real speeds. The reason is that the CPU reads memory in cache lines, not bytes (Vol 3). A contiguous scan streams: the prefetcher sees the pattern and pulls the next line before you ask. A jump to an unrelated address stalls, and the core waits ~100 cycles for RAM. Look back at Fig 1. Our dict-of-lists puts every neighbour list at a scattered heap address. Walking node u's neighbours means following a reference off the dict to wherever that list happens to live — a cache miss. And if the neighbour data itself is objects, that's another miss per element. It's the pointer-chasing of the linked list wearing a graph's clothes: correct O(V+E), but stall-prone.

Here's the human insight that fixes it, the same "a tree can live in a flat array" move you saw the heap make earlier this volume. Take the adjacency lists and concatenate them all into one flat array, indices. Then keep a second small array, indptr, whose entry i says where node i's neighbours begin. Node i's neighbours are then the contiguous slice indices[indptr[i] : indptr[i+1]]. No dict, no scattered lists, just two straight runs of memory. This is CSR (compressed sparse row), and it's how NetworkX-scale libraries, SciPy, and GPU graph engines actually store graphs.

There's an honest cost to CSR, and it's worth naming out loud. Because every node's neighbours live in one packed run, inserting an edge means shifting everything after it along — CSR is built to be read, not edited. So the usual move is to build the graph in the mutable dict-of-lists, then freeze it into CSR once for the fast traversals. That read-many, write-once bet is exactly why static graph engines love CSR and interactive, edge-adding ones reach for the dict.

Run our four friends through CSR to see the two arrays fall out. Number them Ada = 0, Bex = 1, Cy = 2, Dot = 3, and lay every neighbour list end to end: indices = [1, 2, 0, 2, 0, 1, 3, 2]. Now indptr just marks where each node's run starts: [0, 2, 4, 7, 8]. To read Cy's neighbours you slice indices[indptr[2] : indptr[3]], which is indices[4:7] = [0, 1, 3] — Ada, Bex, Dot, exactly right. Two flat arrays, no pointer-chasing, and the neighbours of any node are one contiguous slice away.

from array import array                 # packed 4-byte ints, not boxed objects
indptr  = array('i', [0])               # where each node's neighbours begin
indices = array('i')                    # every neighbour, concatenated
for u in range(V):
    for nb in adjlist[u]:
        indices.append(nb)
    indptr.append(len(indices))         # ...node u's slice ends here

# node u's neighbours, no dict, no scattered list:
indices[indptr[u] : indptr[u+1]]        # a contiguous slice

Line by line: indptr and indices are array('i'), packed 4-byte integers laid contiguously (the array again), not Python objects with 28-byte headers. The loop walks the dict-of-lists once, appending each neighbour to the flat indices and recording the running boundary in indptr. The last line is the payoff: to iterate node u's neighbours you take one contiguous slice. For the 1000-node graph this whole structure measured 28,816 bytes against the dict-of-lists' 308,888, about 11× smaller. And it streams through cache instead of chasing pointers.

Layout settled, the metal appeased — now the reason any of this exists: asking the graph questions. And it turns out you've been living inside the answers all day. →

06Asking the graph questions — and where you already live inside one

Once the graph is in memory, every question is a walk over it. The two fundamental walks were Vol 3's subject, so here's a sentence each. BFS — breadth-first — spreads like a ripple in a pond using a queue. It visits everything one hop away, then two, then three, so its first arrival at a node is the shortest unweighted path. DFS — depth-first — plunges down one path to the end using a stack, often the call stack via recursion, backing up only at dead ends. It's the tool for cycles, connectivity, and ordering. Both are O(V + E), precisely because the adjacency list lets each of them "scan every node's neighbour list once." The structure and the traversal cost are the same fact seen twice. Add weights and BFS's equal-hop assumption breaks. Dijkstra (Vol 3) patches it with a heap.

Why does the queue guarantee the shortest path? Picture starting a rumour at Ada. On round one you tell her direct friends — everyone one hop away. Only when that whole round is done do you move on to their friends, two hops out. Because the queue empties in arrival order, you always finish the closer people before touching any farther one. So the first time the rumour reaches Cy, it arrived by the fewest possible hops. That shortest unweighted path isn't a bonus you compute — it falls straight out of the order the queue enforces.

A graph whose directed edges never loop back is a DAG, a directed acyclic graph, and it's quietly one of the most useful shapes in computing. "Must-happen-before" relations are DAGs, and a DFS over one yields a topological order: a linear sequence respecting every dependency. That single idea is your build system deciding compile order. It's your package manager installing libraries before the things that need them. And it's a spreadsheet recalculating cells in the right sequence.

Why must the graph be acyclic for this to work at all? Suppose it weren't — say A must come before B, B before C, and C before A. No ordering on earth satisfies all three, because whichever task you place first is already waiting on another one. A cycle is just a set of tasks each waiting on the next, forever. That's precisely the circular import or dependency deadlock your build tools shout about — the same impossibility, seen from the graph's side.

Make that topological order concrete with breakfast. To eat toast you must slice the bread before you toast it, and toast it before you butter it — three tasks with two "before" edges. Run a DFS and it hands back the order slice → toast → butter, every arrow pointing forward. Swap in "compile utils.c before main.c before linking" and it's the exact same graph. That's why one algorithm drives your build system, your installer, and your spreadsheet alike.

Which brings us to the 1% move. "Good at data structures" is not knowing graph trivia. It's the reflex, on a brand-new problem, to ask "what are the nodes, what are the edges?" and then "do I need every pairwise lookup (matrix) or just each node's neighbours (list)?" Answer those two and half the problem dissolves: the model tells you it's a graph, and the access pattern tells you how to lay it out. The graph is the most general container in this volume because it makes the fewest assumptions. And that generality is exactly why recognising one is the highest-leverage pattern-match you can train.

from itertools import combinations
from collections import defaultdict

# your four group chats, plus the one person who only ever DMs you
chats = {
    "flat 3B":    ["me", "Sam", "Bea"],
    "5-a-side":   ["me", "Sam", "Tom", "Ravi"],
    "cousins":    ["me", "Meera", "Ravi"],
    "book club":  ["Bea", "Meera", "Nell"],
}
dms = [("me", "Anna")]                    # Anna is in none of the chats

def build(chats, dms):
    """Everyone sharing a chat can relay to everyone else in it."""
    g = defaultdict(set)
    for roster in chats.values():
        for a, b in combinations(roster, 2):
            g[a].add(b)
            g[b].add(a)
    for a, b in dms:
        g[a].add(b)
        g[b].add(a)
    return {p: sorted(g[p]) for p in sorted(g)}

graph = build(chats, dms)
print("the address book - who can I reach in ONE hop:")
for person, nbrs in graph.items():
    print(f"  {person:6} -> {nbrs}")

print("\nendpoints stored:", sum(len(v) for v in graph.values()),
      "= 2E, so E =", sum(len(v) for v in graph.values()) // 2, "real relay links")
print("degrees         :", {p: len(n) for p, n in graph.items()})

def within_two(graph, me):
    """Read the answer straight off the dict - one hop, then their hops."""
    one = set(graph[me])
    two = set()
    for friend in one:
        two |= set(graph[friend])
    two -= one | {me}                     # already direct, or myself
    return sorted(one), sorted(two)

for who in ("me", "Anna", "Nell"):
    direct, second = within_two(graph, who)
    print(f"\n{who}:")
    print(f"  1 hop  ({len(direct)}): {direct}")
    print(f"  2 hops ({len(second)}): {second}")
    print(f"  unreachable in <=2: {sorted(set(graph) - set(direct) - set(second) - {who})}")

# ---------------- OUTPUT, verbatim (CPython 3.12.7) ----------------
# the address book - who can I reach in ONE hop:
#   Anna   -> ['me']
#   Bea    -> ['Meera', 'Nell', 'Sam', 'me']
#   Meera  -> ['Bea', 'Nell', 'Ravi', 'me']
#   Nell   -> ['Bea', 'Meera']
#   Ravi   -> ['Meera', 'Sam', 'Tom', 'me']
#   Sam    -> ['Bea', 'Ravi', 'Tom', 'me']
#   Tom    -> ['Ravi', 'Sam', 'me']
#   me     -> ['Anna', 'Bea', 'Meera', 'Ravi', 'Sam', 'Tom']
#
# endpoints stored: 28 = 2E, so E = 14 real relay links
# degrees         : {'Anna': 1, 'Bea': 4, 'Meera': 4, 'Nell': 2, 'Ravi': 4, 'Sam': 4, 'Tom': 3, 'me': 6}
#
# me:
#   1 hop  (6): ['Anna', 'Bea', 'Meera', 'Ravi', 'Sam', 'Tom']
#   2 hops (1): ['Nell']
#   unreachable in <=2: []
#
# Anna:
#   1 hop  (1): ['me']
#   2 hops (5): ['Bea', 'Meera', 'Ravi', 'Sam', 'Tom']
#   unreachable in <=2: ['Nell']
#
# Nell:
#   1 hop  (2): ['Bea', 'Meera']
#   2 hops (3): ['Ravi', 'Sam', 'me']
#   unreachable in <=2: ['Anna', 'Tom']

We can now store any web of relationships and walk it. But one specific question — "are these two nodes in the same connected blob?" — comes up so often, and can be answered so much faster than a fresh traversal each time, that it earned its own razor-sharp structure. Next: Union-Find, a forest of parent-pointers that answers "connected?" in almost constant time. →