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 branches downward. The graph drops the skeleton entirely. It keeps only the barest idea of structure — a set of nodes and a set of edges between them. That minimalism is exactly why it fits so much: maps, friendships, web links, git history, and the tasks a build must run in order aren't 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, name its nodes and edges, and pick one of two storage layouts — the move that separates fluent from lost, because it decides whether the graph fits in RAM at all.

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 (connections between pairs of things). That's the whole contract. Because the definition says nothing about what the things are, anything can be a node: a city, a person, a web page, a commit, a chemical, a state of a game. Here's 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 (Ada ⇄ Bex: if she's your friend, you're hers). A directed edge points one way (page A → page B; "socks before shoes" is not "shoes before socks"). An edge may also carry a weight — a number on the connection: minutes of drive, cost of a flight, strength of a bond. Four words — node, edge, direction, weight — and you can describe a road atlas, a social network, and a compiler's build order. The vocabulary was Vol 3's job. Here we ask the practical question it skipped: a machine can't store a drawing, it stores bytes. So how does a graph actually sit in RAM?

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 — 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 up: 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.

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). 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 is simple. 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, then row 1's V cells, laid end to end, with cell (i, j) living 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.

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. Flip the toggle and watch the memory story change: the list writes down only the edges that exist; the matrix reserves all V² boxes the instant you create it.

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; E halves the endpoint count because each friendship is one shared edge. cells is V² — a trillion boxes. slots is V+2E — eleven million. The ratio is 90,909×. And cells // 8 is the kindest possible matrix — one bit per cell — still 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 — 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 (every pair connected) — the one regime where the matrix's fixed price is finally fair.

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, because 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 — 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, 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, and 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 — 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.

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, and the two fundamental walks were Vol 3's subject, so 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.

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, your package manager installing libraries before the things that need them, and a spreadsheet recalculating cells in the right sequence.

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.

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. →