Adjacency Lists, Matrices, and the Cost of Asking Who Is Adjacent

Every graph algorithm is written against some representation of a graph, and the representation decides which operations are cheap. For a graph with n vertices and m edges, three encodings cover most uses: the adjacency matrix, the per-vertex list, and the compressed sparse row arrays used by nearly every high-performance graph library. They differ by orders of magnitude in memory, and they differ in the two operations that every traversal performs — enumerate the neighbours of a vertex, and test whether a specific pair is an edge.

Three encodings of the same set of pairs

An adjacency matrix stores one cell per ordered pair. For an unweighted graph a single bit per cell suffices, so the storage is n² bits, or n²/8 bytes; a byte per cell is common when a sentinel is wanted, and a 32-bit weight per cell when edges carry values. The matrix of an undirected graph is symmetric, so half the cells are redundant, and self-loops land on the diagonal.

An adjacency list stores, for each vertex, a growable array of its neighbours. Total storage is 2m entries for an undirected graph and m for a directed one stored only outwards, plus per-vertex bookkeeping. In C that bookkeeping is a pointer, a length, and a capacity per vertex — 24 bytes on a 64-bit machine before a single neighbour is stored. In a garbage-collected language each inner array is a separate object with its own header, and the allocator rounds every one of them up to a size class, so a vertex with two neighbours may occupy 32 or 64 bytes of heap.

Compressed sparse row removes the per-vertex objects. Two flat arrays encode everything: an offset array of n+1 integers, where the neighbours of vertex v occupy slots start[v] through start[v+1]-1, and a target array of m (or 2m) vertex identifiers. A third array holds weights when needed. Nothing is allocated per vertex, nothing points outside the arrays, and the structure is built by a counting sort over the edge list.

What a traversal actually asks for

Breadth-first search, depth-first search, and every variant of them do the same thing at each vertex: iterate over its neighbours. That is the operation the representation must make cheap, and the three encodings price it differently.

A matrix row is scanned in full. Visiting the neighbours of a vertex costs Θ(n) regardless of its degree, so a complete traversal costs Θ(n²) even when the graph holds ten edges. On a graph with n = 10⁶ and m = 10⁷ the matrix asks for 10¹² cell inspections while the graph contains 10⁷ edges. A compressed sparse row scan touches exactly deg(v) entries, and the whole traversal touches n + 2m.

The reverse trade appears in edge queries. Testing whether (u, v) is an edge is one array index into a matrix and a scan of deg(u) entries in a list. Algorithms that repeatedly test membership — incremental cycle checks, transitive-closure computations, duplicate suppression while building the graph — can prefer the matrix for that reason alone.

The asymptotic statement taught for BFS and DFS, O(n + m), is therefore a statement about the representation as much as about the algorithm. It holds for adjacency lists and for compressed sparse row. On a matrix the same algorithm is quadratic in the vertex count, and no amount of careful coding changes that.

Memory arithmetic at realistic sizes

Take a graph with a million vertices and ten million edges. As a bit matrix it needs 10¹² bits, about 125 GB. As a 32-bit weighted matrix, 4 TB. As compressed sparse row with 32-bit identifiers it needs 4(n+1) bytes of offsets and 4m bytes of targets — roughly 44 MB for the out-edges alone, about 84 MB once an undirected graph stores both directions — and it can be built in two passes over the edge list. The gap is more than three orders of magnitude, which is why dense-matrix code and sparse-graph code barely resemble each other even when they solve the same problem.

Density decides the crossover. A bit matrix uses n² bits; a compressed sparse row with 32-bit entries uses about 32(2m + n) bits for an undirected graph. Setting the two equal puts the crossover near m ≈ n²/64, but that arithmetic only compares storage. The matrix still pays Θ(n) work per vertex during traversal, so it earns its place when the graph is dense enough that most rows are nearly full, or when edge queries dominate everything else.

The other regime is small n. At n = 10⁴ a bit matrix is 12.5 MB, a plausible resident working set on a server, and its row scans are sequential word loads — 64 candidate neighbours examined per 64-bit load. That is the case in which the matrix is not merely tolerable but faster, because the scan is predictable and the branch that tests a bit is cheap.

Building CSR and what the build order preserves

def build_csr(n, edges):
    deg = [0] * n
    for u, _ in edges:
        deg[u] += 1
    start = [0] * (n + 1)
    for v in range(n):
        start[v + 1] = start[v] + deg[v]
    pos = start[:-1]                 # next free slot per vertex
    target = [0] * len(edges)
    for u, v in edges:
        target[pos[u]] = v
        pos[u] += 1
    return start, target

The two-pass construction is a counting sort: count degrees, prefix-sum them into offsets, then place each target at the next free slot for its source. It runs in O(n + m) and produces neighbours grouped by source, in the order the edges appeared in the input. That last detail is not incidental. Depth-first search and breadth-first search visit neighbours in stored order, so the traversal order, the shape of the resulting search tree, and the output of anything downstream depend on the input order of the edge list. Two runs over the same graph with differently ordered input can produce different trees while both remain correct.

Libraries that promise reproducibility either document neighbour order as unspecified or sort targets within each row. Sorting costs O(m log m) in the worst case, or O(m) with a counting sort over vertex identifiers when the identifier range is small.

A reverse index — the same structure built from the transposed edge set — costs another O(n + m) storage and one more pass. It is required by algorithms that walk incoming edges, including the two-pass approach to strongly connected components and the pull direction of large-scale breadth-first search.

Mutation and the cost the static layout hides

A matrix accepts an edge insertion or deletion in constant time: set or clear one cell. An adjacency list appends in amortized constant time; deletion costs a scan of the row unless the implementation swaps the last element into the hole, which destroys order, or marks entries as dead and compacts later. Both are O(deg(u)).

Compressed sparse row is immutable in the strict sense. Inserting an edge shifts every target after its position, or forces a rebuild of both arrays at O(n + m). Systems that need frequent updates either keep a small overflow list beside each vertex’s block, rebuild periodically, or choose a different layout entirely — blocked adjacency lists that store neighbours in fixed-size chunks so a row can grow without relocating its neighbours.

The rebuild is not the only cost. Between rebuilds the overflow lists make iteration branchy: the neighbour loop checks the main block, then the overflow, then falls back to an auxiliary structure, and the fast sequential path that motivated the layout is lost for exactly the vertices that change most often.

Where the layouts break

Multigraphs expose the matrix’s central weakness. Two parallel edges collapse into one cell, so degree counts, edge counts, and any algorithm that distinguishes multiplicity silently lose information. Self-loops occupy one cell in a matrix, appear once in a directed adjacency list, and appear twice in an undirected one if the builder inserts both directions without special-casing, which double-counts the degree.

Vertex identifiers that are not dense integers force a remapping step. Either the graph is relabelled into 0..n-1, costing a hash-table pass and O(n) memory, or the matrix becomes a hash map keyed by pairs with worse constants than either layout. Implicit graphs — grids, state spaces, graphs defined by a neighbour function — should not be materialized at all: the neighbour function computes identifiers arithmetically, and the only structure needed is a visited set.

Finally, 32-bit offsets break once m passes roughly 2.1 billion. Libraries that support such graphs store 64-bit offsets and targets, doubling the array sizes, and the choice is usually made at compile time or through a separate type rather than a runtime flag.

The representation chosen at construction propagates into everything later. A search that is linear on compressed sparse row is quadratic on a matrix, and a component-labelling pass that needs incoming edges needs the transpose built in advance. Both facts show up directly in the BFS layer argument and in the edge classification that DFS timestamps support, where the linear bound is assumed without comment.