44Graphs — the universal model

In Chapter 43 we searched a line of data — binary search halving a sorted array, quickselect plucking the median from a billion numbers. But most of the world isn't a line; it's a web. Think of roads, friendships, web links, task lists, molecules, or the moves in a chess game. Draw a dot for each thing and a line for each connection, and every one of them turns into the same shape: a graph. Here's the plan. We build that shape from zero, look at the two ways a machine actually stores it in memory, then pick up the three tools that answer almost any question you can ask of it — BFS, the ripple; DFS, the plunge; and Dijkstra, the weighted route. All the way through, we keep coming back to the one question that quietly turns a hard problem easy — what are the nodes, and what are the edges? By the end you'll ask it on sight. You'll model a maze, a course catalogue, and a road map as the very same object, and watch half the difficulty disappear the moment you name it.

01Dots and lines — the most general structure there is

Let's start with the definition, because it's tiny. A graph is just two sets: a set of nodes (also called vertices) — the things — and a set of edges — the connections between pairs of things. That's all there is to it. And that emptiness is exactly where the power comes from. Because we said nothing about what the things are, anything can be a node.

See how far that reaches. Cities are nodes and roads are edges. People are nodes and friendships are edges. Web pages are nodes and hyperlinks are edges. Tasks are nodes and "must-happen-before" is an edge. Atoms are nodes and chemical bonds are edges. The valid states of a Rubik's cube are nodes and a single twist is an edge. Every one of these is literally a graph — not "like" a graph, not "modelled as" a graph. Same structure, same algorithms, one skill.

Edges come in two kinds, and the difference runs through the whole chapter. An undirected edge is a two-way street: if Ada is friends with Bex, Bex is friends with Ada. A directed edge points one way: page A links to page B, but B need not link back, and "socks before shoes" does not mean "shoes before socks". An edge can also carry a weight — a number attached to the connection, like the minutes to drive that road, the cost of that flight, or the strength of that bond. No weight means every edge counts the same. Weights are where Dijkstra will earn its keep.

We have the picture. But a machine cannot store a picture — it stores bytes. So the first real question is brutally practical: how do you write a graph down? →

02Two ways to write a graph down — and the tradeoff that decides everything

There are two honest ways to hand a graph to a computer. Choosing between them is the first engineering decision of every graph problem.

First, the adjacency list: for each node, store a list of its neighbours. Ada → [Bex, Cy]; Bex → [Ada, Dot, Eli]; and so on. In Python this is just a dictionary of lists — a hash table (Volume 1) whose values are dynamic arrays. To find Ada's neighbours you jump straight to her list. To store the whole graph you spend one slot per node plus one slot per edge-endpoint. Count it: V nodes and E edges cost V + 2E slots for an undirected graph, since each edge appears at both of its ends. That is O(V + E) space — you pay only for connections that actually exist.

Now the other way, the adjacency matrix: a V×V grid of 0s and 1s, where cell [i][j] = 1 means "there is an edge from i to j". Want to know if Ada and Fin are directly connected? Read one cell — O(1), instant, with no list to scan. But the grid has V² cells whether or not the edges exist, so it costs O(V²) space no matter how few edges there are. The matrix reserves a box for every possible connection in the universe. The list writes down only the ones that are real.

That difference is not academic. It is the difference between fitting in memory and not. Real graphs are sparse: a person has hundreds of friends, not millions, and a web page links to dozens of pages, not billions. Here is the gap, computed for a million users each with about ten friends:

V = 1_000_000        # a million users
avg_deg = 10         # ~10 friends each
E = V * avg_deg // 2 # undirected edges  -> 5,000,000

matrix_cells = V * V           # 1,000,000,000,000  (a trillion)
list_slots   = V + 2 * E       #        11,000,000  (eleven million)
print(matrix_cells // list_slots, "x bigger")   # -> 90909 x bigger

Line by line: V and avg_deg set the scale. E works out the edge count, halved because each friendship is one edge shared by two people. matrix_cells is V² — a trillion boxes. list_slots is V + 2E — eleven million. So the matrix is ~90,909× larger. Even packed down to a single bit per cell, that trillion-cell matrix is 125 GB just to record who-knows-whom, while the list fits in a few hundred megabytes. For a sparse graph, the matrix is a catastrophe you can measure.

Now the graph is in memory. The real magic starts: asking it questions. The first and most human question — "what's the shortest way from here to there?" — is answered by dropping a stone in a pond. →

03BFS — the ripple that finds the shortest path

Drop a stone in still water and a ring spreads outward. Every point the ring touches at the same instant is the same distance from the splash. Breadth-first search (BFS) is exactly that ring, run on a graph. Start at a node, visit all its neighbours (distance 1), then their unvisited neighbours (distance 2), then theirs (distance 3), rippling outward one layer at a time until the whole graph is soaked.

The engine that keeps the ripple a ring is a queue — the first-in-first-out line from Volume 1. You add newly-discovered nodes to the back and always take from the front. Because the front always holds the earliest-discovered (nearest) node, you finish an entire distance-layer before the next one begins. Here it is running on a tiny friendship network:

from collections import deque
def bfs(graph, start):
    dist = {start: 0}                 # how many hops from start
    q = deque([start])                # the ripple's frontier (a queue)
    while q:
        u = q.popleft()               # take the NEAREST unfinished node
        for v in graph[u]:            # look at each neighbour
            if v not in dist:         # first time we reach v...
                dist[v] = dist[u] + 1 # ...so this IS its shortest distance
                q.append(v)           # add it to the back of the line
    return dist

print(bfs(friends, "Ada"))
# -> {'Ada': 0, 'Bex': 1, 'Cy': 1, 'Dot': 2, 'Eli': 2, 'Fin': 3}

Line by line: dist does double duty as "have I seen this node?" and "how far is it?". q starts holding only the source. Each loop takes the front node u — guaranteed to be the nearest unfinished one — and scans its neighbours. The load-bearing line is if v not in dist. The first time BFS reaches a node is along the shortest possible route, because any shorter route would have arrived in an earlier ring. So dist[v] = dist[u] + 1 is not a guess. It is the final answer, set once and never revised. The run confirms it: Ada→Fin is 3 hops, and no path is shorter.

Now stop reading and run the ripple yourself. Below, BFS spreads across a grid with walls. Press Step and watch the wavefront fan out ring by ring, colouring each cell by its distance, until it reaches the goal — and the shortest path falls out. Then flip to DFS and watch the very same search drop the rings and plunge into one corridor instead.

You just watched BFS spread and DFS plunge on the same maze. That "plunge" is not a bug — it is a second superpower, and it happens to be one line of code away. →

04DFS — the plunge, and the one-line secret it shares with BFS

Depth-first search (DFS) picks a direction and commits. From a node it walks to a neighbour, then a neighbour of that, going as deep as it can before it hits a dead end and backs up to try the last unexplored turn. Where BFS fans out in careful rings, DFS dives to the bottom first. Its natural engine is the stack — last-in-first-out — which is also why DFS is usually written as a plain recursive function: the call stack from Volume 1 is the stack.

Here is the insight that makes graph search click, and it is one of the most satisfying in the whole volume. BFS and DFS are the same algorithm. The only difference is which end of the frontier you take the next node from. Take from the front (a queue) and you get rings — BFS. Take from the back (a stack) and you get a plunge — DFS. Just one line changes:

def traverse(graph, start, use_stack):
    seen = {start}; frontier = deque([start]); order = []
    while frontier:
        u = frontier.pop() if use_stack else frontier.popleft()   # <-- the ONLY difference
        order.append(u)
        for v in graph[u]:
            if v not in seen:
                seen.add(v); frontier.append(v)
    return order

print(traverse(friends, "Ada", False))  # queue -> ['Ada','Bex','Cy','Dot','Eli','Fin']
print(traverse(friends, "Ada", True))   # stack -> ['Ada','Cy','Eli','Fin','Dot','Bex']

Line by line: the setup is identical for both. The whole personality of the search lives in one expression — frontier.pop() (take from the back, LIFO, a stack) versus frontier.popleft() (take from the front, FIFO, a queue). Swap only that, and the same code produces two completely different explorations. The queue visits Ada's world layer by layer. The stack shoots straight down one chain to Fin before it ever finishes with Bex. That is the deep unity: search is just "keep a frontier and choose whom to expand next", so the data structure is the strategy.

The crown jewel of DFS is topological sort: given tasks with "must-come-before" dependencies (a directed graph), produce an order in which every task appears after everything it depends on. Course prerequisites, spreadsheet cell recalculation, and — most famously — build systems and package managers all live or die by it. Here it is on a course catalogue:

# prereqs: a course maps to the courses it requires first
print(toposort(prereqs))
# -> ['Intro', 'DataStruct', 'OS', 'Algorithms', 'Databases', 'Compilers']

prereqs["Intro"] = ["Compilers"]   # make Intro depend on Compilers -> a loop
print(toposort(prereqs))           # -> None   (no valid order exists)

The first call returns a legal study plan: Intro before everything, Compilers dead last because it needs both Algorithms and OS. The second call is the important one. Once we make Intro require Compilers — which requires Algorithms, which requires DataStruct, which requires Intro — there is a cycle, and no ordering can satisfy it. The algorithm returns None. That is not a failure. It is the exact error your build tool throws when two packages depend on each other, or your spreadsheet flags a circular reference. This ability to say "impossible, and here's why" is why topological sort sits at the heart of make, npm, pip, and every CI pipeline.

05Dijkstra — shortest paths when the edges have a price

The moment edges carry weights, BFS breaks. Its whole guarantee rested on "one hop = one unit", so the first arrival was the nearest. With weights, a path of three cheap edges can beat a path of one expensive edge. The ripple counts hops, so it walks right past the better route. We need a search that expands by total distance so far, not by hop count. That search is Dijkstra's algorithm.

The idea is greedy (chapter 39): keep a frontier of "reached but not yet finalised" nodes, each tagged with the cheapest total distance found to it so far, and always finalise the globally cheapest one next. Because all weights are positive, once a node is the cheapest on the frontier, nothing discovered later can undercut it, so its distance is locked. To keep pulling out the current minimum, Dijkstra leans on a priority queue, a.k.a. a min-heap. Treat it as a black box (its internals are a later volume) that hands back the smallest item in O(log n). Watch it route a commute where minutes, not turns, are the currency:

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]                 # min-heap of (distance_so_far, node)
    settled = {}
    while pq:
        d, u = heapq.heappop(pq)      # the globally CHEAPEST open node
        if u in settled: continue     # already finalised -> skip stale copy
        settled[u] = d                # lock it in: this is its shortest distance
        for v, w in graph[u]:         # relax each outgoing edge
            nd = d + w
            if v not in dist or nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return settled

print(dijkstra(roads, "Home"))
# -> {'Home': 0, 'B': 1, 'A': 3, 'C': 4, 'Work': 7}

Line by line: dist holds the best-known tentative distance to each node. pq is the min-heap frontier, seeded with the start at distance 0. Each loop pops the cheapest open node — heappop is the black-box min — and, if it hasn't already been finalised, settles it: its distance is now final and correct. Then it relaxes every outgoing edge, asking "could I reach v more cheaply by going through u?" If yes, it records the shorter distance and pushes v back onto the heap. The gem is in the output. The direct road Home→A costs 4, but Dijkstra reports A's distance as 3, because the detour Home→B→A is only 1+2. The greedy frontier found the sneaky cheaper route the eye would skip, and Work comes out at 7 (Home→B→A→C→Work).

How costly is all this? Count the work. Every node is settled once, and each settling relaxes its outgoing edges. So across the whole run we touch each edge once, doing an O(log V) heap operation per touch. That is O(E log V) for the edges, plus O(V log V) for the pops, giving Dijkstra's classic O((V + E) log V). On a continent-sized road graph that is the difference between a route in milliseconds and one that never returns.

BFS, DFS, Dijkstra — three questions, three tools, one structure. The last step is the one that changes you as an engineer: learning to see the graph that was hiding inside the problem all along. →

06The move that makes you dangerous — model it as a graph first

Step back and look at what just happened across this chapter. A friendship network, a maze, a course catalogue, and a road map look like four unrelated things. Yet we solved all four with the same three functions, unchanged, because underneath they were the same object: nodes and edges. That is the real lesson of this chapter, and it is worth more than any single algorithm.

The transferable move — the one the top 1% make almost reflexively — is this: when a new problem lands, before you write a line, ask "what are the nodes, and what are the edges?" The answer is often startling. States of a puzzle are nodes and legal moves are edges, so "solve the puzzle" becomes "find a path" — and BFS solves a sliding-tile puzzle for free. Words are nodes and "differ by one letter" is an edge, so word-ladder puzzles and spell-check suggestions become shortest paths. Jobs and machines are nodes and "can run on" is an edge, so scheduling becomes a matching problem. Half of algorithm design is not inventing a clever method. It is recognising the graph that was there the whole time, at which point a solved, off-the-shelf algorithm takes over.

One person made a piece of this feel inevitable. Edsger Dijkstra later recounted that he worked his shortest-path method out in about twenty minutes in 1956 — in his head, sitting at a café, with no paper and no computer. The lesson isn't the biography. It's the way of thinking it reveals. He didn't picture streets. He pictured the pure structure — nodes, edges, a growing frontier of "cheapest settled so far" — and reasoned about that. When you strip a problem down to its skeleton like that, the answer often stands up on its own. That stripping-down is the skill this whole chapter was really teaching.

We just found the shortest path through a graph in polynomial time — fast, reliable, done. So here is a question that sounds almost identical: instead of the shortest path from Home to Work, find the shortest tour that visits every city and returns — the Travelling Salesman. Change that one word, "path" to "tour", and every fast algorithm we own detonates: the cost curve leaps off the polynomial track and onto the red O(2ⁿ) explosion, where a few dozen cities would outlast the universe.

We found the shortest path in polynomial time — fast, reliable, done. The next chapter switches tools entirely: strings & number theory, the crypto-and-quant layer. How Ctrl-F, git diff and DNA aligners find a pattern without re-reading what they already know — and the one impossibly one-sided calculation that hides behind every padlock icon in your browser. →