Graph representations

What this chapter covers

A graph is the most general structure in the book: vertices connected by edges, with no root, no parent rule, and cycles allowed. Roads, social networks, dependencies, the web, circuit diagrams — anything that's a bunch of things with connections between them is a graph. But before you can run a single graph algorithm, you have to decide how to store the thing, and that choice colors everything after it. This chapter builds the two classic representations — the adjacency list and the adjacency matrix — and shows why the list is the default for the sparse graphs that make up almost all of reality, while the matrix wins only in the dense corner cases.

A bit of history

Graph theory is nearly three centuries old, and it began with a walk. In 1736 Leonhard Euler settled the Seven Bridges of Königsberg — could you cross all seven bridges of the city exactly once? — by abstracting the landmasses to points and the bridges to connections, and proving no such route existed. That abstraction, throwing away the map and keeping only "what connects to what," founded graph theory and gave us the vocabulary of vertices and edges. Two centuries later, when computers needed to store these abstract graphs, the two representations in this chapter emerged as the natural encodings: a matrix of connections, in the spirit of the incidence tables mathematicians already used, and the more economical list of neighbors. The choice between them has been a first lesson in practical graph programming ever since, because it's the first place the gap between a graph's mathematical simplicity and its computational cost shows up.

The intuition

A graph is defined by which vertices connect to which. The adjacency list stores that directly: for each vertex, a list of the vertices it's connected to. Vertex 3's list might be [1, 7, 9], meaning 3 connects to 1, 7, and 9. To find a vertex's neighbors, you read its list — you touch only its actual neighbors, nothing else. The total storage is one entry per vertex plus one (or two) per edge: O(V + E).

The adjacency matrix stores the same information as a grid: a V×V table where cell (u, v) is 1 if there's an edge from u to v and 0 otherwise. To check whether a specific edge exists, you read one cell — O(1), instantly. But the grid has a cell for every possible pair of vertices, connected or not, so it always uses O(V²) space, and to find a vertex's neighbors you must scan its entire row of V cells, most of which are 0 in a sparse graph.

That's the trade in one sentence: the list stores only what exists and pays a small scan to test an edge; the matrix stores every possible connection and tests an edge instantly. Which wins depends on density — how many of the possible edges actually exist. Real graphs are almost always sparse: a person has a few hundred friends, not a few billion; a web page links to dozens of pages, not the whole internet; a road intersection meets a handful of roads. When E is close to V rather than V², the list's O(V+E) crushes the matrix's O(V²), which is why the list is the default.

Complexity: how it scales

The two representations have mirror-image cost profiles, laid out in the at-a-glance table: the list is $O(V+E)$ space with $O(\text{degree})$ edge tests and neighbor iteration; the matrix is $O(V^2)$ space with $O(1)$ edge tests and $O(V)$ neighbor iteration. For the sparse graphs that matter, the space difference is enormous. The chart plots memory for a sparse graph (average degree 6) as the vertex count grows:

At 4000 vertices, the sparse graph took about 437 KB as an adjacency list against 125 MB as a matrix — 286 times more memory, for the identical graph, because the matrix reserves a cell for all 16 million possible pairs when only 24000 edges exist. And that memory isn't just storage: because a traversal must read the whole matrix to find all edges, the matrix also makes every graph algorithm O(V²), where the list makes it O(V+E). The representation isn't a detail — it sets the complexity of everything downstream.

What it's good at, what it isn't

The adjacency list is the right default for essentially every real graph, because real graphs are sparse and the list's O(V+E) space and traversal are what make the algorithms of the next ten chapters efficient. BFS, DFS, Dijkstra, and the rest are all O(V+E) because they run on adjacency lists; on a matrix they'd be O(V²). If you're not sure which to use, use the list.

The matrix earns its O(V²) only in two situations. First, dense graphs, where E really is close to V² — then the matrix isn't wasteful, and its cache-friendly contiguous layout can be faster. Second, workloads dominated by "is there an edge between exactly u and v?" queries rather than neighbor iteration, where the matrix's O(1) test beats the list's scan. Some algorithms (Floyd-Warshall, a later chapter) are naturally matrix algorithms. But outside those cases the matrix's quadratic memory is a liability that grows fast — 286× here and worse as graphs get bigger — so it's the specialist, not the default.

The data, or the inputs

The memory chart models sparse graphs (average degree 6) at growing vertex counts, isolating the O(V+E)-vs-O(V²) space gap. The animation builds a small six-vertex graph one edge at a time, so you can watch the structure — vertices and their connections — take shape.

Build it, one function at a time

For the adjacency list, adding an edge appends to the neighbor lists:

def add_edge(self, u, v):
    """O(1): append v to u's neighbor list (and u to v's, if undirected)."""
    self._adj[u].append(v)
    if not self.directed:
        self._adj[v].append(u)

And getting neighbors is just reading a list — you touch only the actual neighbors:

def neighbors(self, u):
    """O(1) to get the list; iterating it is O(degree(u)) — you touch only u's actual
    neighbors, never the vertices it doesn't connect to. This is why traversals over a
    sparse graph are O(V+E) with a list."""
    return self._adj[u]

The matrix is the grid version — O(1) to test an edge, O(V) to find neighbors:

def add_edge(self, u, v):
    """O(1): set the cell (and its mirror, if undirected)."""
    self._m[u][v] = 1
    if not self.directed:
        self._m[v][u] = 1

def has_edge(self, u, v):
    """O(1): one array lookup — the matrix's whole advantage."""
    return self._m[u][v] == 1

def neighbors(self, u):
    """O(V): scan the entire row, even the zeros — the matrix's whole disadvantage on
    a sparse graph, where almost every cell is 0."""
    return [v for v in range(self.n) if self._m[u][v]]

Watch it work

Here's a six-vertex graph being built one edge at a time. The vertices sit in fixed positions; each frame adds an edge (highlighted orange) and lights up its two endpoints. Step through it and watch the network emerge — this is exactly what add_edge does to the adjacency list, each edge appending the two endpoints to each other's neighbor lists. By the end you have a small connected graph, the kind the traversal algorithms of the next chapters will explore:

The complete code

Both versions in one place — flip between them. The from-scratch tab has both representations. The library tab is the memory model that quantifies their difference, standing in for the real library, networkx, whose Graph is a dict-of-dicts — an adjacency list in spirit — because Python has no built-in graph type; you build one from lists or dicts exactly as here.

"""Graph representations — how you store a graph in the first place, which decides what
every graph algorithm after this costs.

A graph is a set of vertices and edges: any vertex can connect to any other, forming
networks — roads, social links, dependencies, the web. Unlike a tree, there's no root,
no parent rule, and cycles are allowed. Before you can search or find paths, you have to
choose a representation, and the choice is a real trade-off between two options:

  - an ADJACENCY LIST — each vertex keeps a list of its neighbors — O(V+E) space,
    perfect for the sparse graphs that dominate the real world;
  - an ADJACENCY MATRIX — a V×V grid of 0/1 — O(V²) space, but O(1) to test whether a
    specific edge exists.

Most real graphs are sparse (each vertex touches only a few others), so the adjacency
list is the default; the matrix wins only for dense graphs or when you constantly ask
"is there an edge between exactly these two?"
"""


class Graph:
    """Adjacency-list graph: O(V+E) space, O(degree) neighbor iteration."""

    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self._adj = [[] for _ in range(n)]

    # region: add_edge
    def add_edge(self, u, v):
        """O(1): append v to u's neighbor list (and u to v's, if undirected)."""
        self._adj[u].append(v)
        if not self.directed:
            self._adj[v].append(u)
    # endregion

    # region: neighbors
    def neighbors(self, u):
        """O(1) to get the list; iterating it is O(degree(u)) — you touch only u's actual
        neighbors, never the vertices it doesn't connect to. This is why traversals over a
        sparse graph are O(V+E) with a list."""
        return self._adj[u]
    # endregion

    def has_edge(self, u, v):
        """O(degree(u)): scan u's neighbors. The list's weak spot — the matrix does this
        in O(1)."""
        return v in self._adj[u]

    def edge_count(self):
        total = sum(len(a) for a in self._adj)
        return total if self.directed else total // 2


class MatrixGraph:
    """Adjacency-matrix graph: O(V²) space, O(1) edge test, O(V) neighbor iteration."""

    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self._m = [[0] * n for _ in range(n)]

    # region: matrix
    def add_edge(self, u, v):
        """O(1): set the cell (and its mirror, if undirected)."""
        self._m[u][v] = 1
        if not self.directed:
            self._m[v][u] = 1

    def has_edge(self, u, v):
        """O(1): one array lookup — the matrix's whole advantage."""
        return self._m[u][v] == 1

    def neighbors(self, u):
        """O(V): scan the entire row, even the zeros — the matrix's whole disadvantage on
        a sparse graph, where almost every cell is 0."""
        return [v for v in range(self.n) if self._m[u][v]]
    # endregion

"""The graph library everyone uses in Python is the third-party `networkx` — a `nx.Graph`
is an adjacency structure (a dict of dicts) with hundreds of algorithms built on top. In
the standard library there's no graph type; you build one from dicts or lists, exactly as
here. So the counterpart for this chapter is the two representations against each other,
measured on the thing that separates them — memory on a sparse graph, and edge-lookup
speed — with `networkx`'s dict-of-dicts being essentially the adjacency-list approach.
"""
import sys


# region: memory
def list_memory(graph):
    """Rough memory of an adjacency-list graph: proportional to V + E (the neighbor
    entries)."""
    total = sys.getsizeof(graph._adj)
    for row in graph._adj:
        total += sys.getsizeof(row) + sum(sys.getsizeof(x) for x in row[:0])  # container overhead
        total += 8 * len(row)                          # ~8 bytes per neighbor reference
    return total


def matrix_memory(graph):
    """Rough memory of an adjacency-matrix graph: proportional to V² regardless of how
    many edges actually exist."""
    return graph.n * graph.n * 8                        # ~8 bytes per cell
# endregion

Scratch vs library

There's no head-to-head timing here, because the representations aren't competing implementations of one thing — they're two different data structures with mirror-image costs, and the "winner" depends entirely on your graph. The memory chart is the decisive comparison: 286× at 4000 sparse vertices, growing quadratically. The practical takeaway is a rule you'll apply for the next ten chapters: default to the adjacency list, because real graphs are sparse and the list keeps their algorithms at O(V+E); reach for the matrix only when the graph is genuinely dense or when constant-time edge tests dominate your workload. Every graph algorithm ahead assumes an adjacency list unless it specifically wants a matrix — and knowing why is knowing that the representation, chosen before any algorithm runs, is what sets the algorithm's cost.

Where you'll actually meet it

You meet these representations under every graph you touch. Social networks store the follow/ friend graph as adjacency lists (a matrix of billions of users squared is unthinkable). Web crawlers and PageRank operate on the link graph as sparse adjacency structures. Compilers build dependency and control-flow graphs as adjacency lists. Routing protocols represent networks as weighted graphs. GPS and maps store road networks as adjacency lists with distances as weights. And when performance really matters, a compressed variant called CSR (compressed sparse row) packs an adjacency list into flat arrays for cache-friendly traversal — the representation behind high-performance graph processing and sparse linear algebra. The matrix, meanwhile, shows up wherever graphs are small and dense or algorithms are matrix-shaped, like all-pairs shortest paths.

Takeaways

A graph is vertices and edges, and the first decision is how to store it: an adjacency list (O(V+E) space, O(degree) operations) or an adjacency matrix (O(V²) space, O(1) edge test). Because real graphs are sparse, the list is the default — it keeps memory linear and, crucially, keeps every traversal O(V+E) where a matrix would force O(V²). The matrix is the specialist for dense graphs and edge-test-heavy workloads. Layer directed/undirected and weighted on top, and the weighted directed adjacency list is what most of this tier runs on.

With a graph in hand, the rest of the tier is about asking questions of it. The first and most fundamental is reachability: starting somewhere, what can you get to, and in what order? The next two chapters answer that with the two great graph traversals — breadth-first search, which uses the queue from the linear-structures tier to explore nearest-first, and depth-first search, which uses the stack (or recursion) to plunge deep. Every graph algorithm after them is one of these two traversals with something extra bolted on.