Graph representation trade-offs

Before any graph algorithm runs, someone decided how the graph sits in memory — and that decision quietly priced every operation the algorithm will perform. “Enumerate my neighbours”, “does this edge exist?”, “give me all edges sorted” have wildly different costs under different representations, and picking the wrong one turns a linear algorithm quadratic without a single logic error. This page is the pricing sheet, plus the recognition skill the pricing depends on: noticing that the problem in front of you is a graph.

Adjacency list: the default, and why

One bucket per node, holding that node’s neighbours: A: [B, C], B: [A, D]… Storage is O(V + E) — you pay for edges that exist, nothing more — and “enumerate neighbours” costs exactly the neighbour count, which is the operation traversals live on. BFS, DFS, Dijkstra, and topological sort all owe their O(V + E) bounds to this: the sum over all nodes of “look at my neighbours” is the sum of all edge-ends, 2E. Run any of the graph visualizations on this site and the edges-inspected counter is counting exactly those bucket walks.

The costs it accepts: “does edge A–B exist?” means scanning A’s bucket — O(degree), not O(1). For sparse graphs (E close to V — road networks, social graphs, almost everything real) that trade is overwhelmingly right, which is why adjacency list is the default unless a specific operation says otherwise. Directed graphs store the edge in one bucket; undirected, in both — and forgetting the second insertion is the most common graph-construction bug in existence, producing traversals that mysteriously reach only half the graph.

Adjacency matrix: paying for O(1) edge tests

A V×V grid of booleans (or weights): m[a][b] answers “is there an edge?” in one array read. The price is brutal and fixed: O(V²) storage regardless of E — a million-node sparse graph wants a trillion cells to store a few million edges — and “enumerate neighbours” scans a whole row, O(V), so every traversal degrades to O(V²).

When it wins: dense graphs (E approaching V², where the storage is being used anyway), algorithms whose structure is inherently all-pairs (Floyd–Warshall is a triple loop over a matrix and doesn’t apologize), and edge-existence-heavy workloads on small V. The interview sentence that shows you own the trade: “matrix when dense or when I need O(1) edge tests and V is small — say, under a few thousand; list otherwise.”

Edge list: the humble third option

Just an array of (from, to, weight) triples. Useless for “neighbours of X” (scan everything), but two algorithms are shaped for it: Kruskal’s MST sorts all edges by weight and processes them in order — a sorted edge list is literally its input format, with union-find doing the cycle checks — and Bellman–Ford relaxes every edge V−1 times, needing nothing but “all edges, please”. Edge lists are also what data actually arrives as (a CSV of relationships), so “read edge list, build adjacency list” is the standard first act of most real graph code — O(E), one pass.

The disguises

The recognition skill outranks the pricing table, because interview graphs rarely announce themselves. A grid or maze is a graph: cells are nodes, the 4 (or 8) neighbouring cells are edges — and crucially, you never build an adjacency anything; neighbours are computed on demand from the row/column offsets, an implicit representation with zero storage. Number-of-islands, shortest-path-in-maze, rotting-oranges are all BFS/DFS on implicit grids. A word ladder is a graph whose nodes are words and whose edges are one-letter changes — again implicit: neighbours are generated, not stored. States of a puzzle with legal moves, courses with prerequisites, currency pairs with exchange rates — the question “what are my nodes, what are my edges, are they directed, are they weighted?” is the four-beat opening move for a huge class of problems, and answering it out loud is half the interview.

Those four beats also route you to the algorithm: unweighted + shortest → BFS; weighted non-negative + shortest → Dijkstra; “must come before” + directed → topological sort; connectivity arriving over time → union-find, which — worth noticing — uses no graph representation at all, just a parent array, because “same component?” never needs neighbour enumeration.

The pricing table, for the pocket

Operation	Adj. list	Adj. matrix	Edge list
Storage	V + E	V²	E
Neighbours of X	degree(X)	V	E
Edge exists?	degree(X)	1	E
All edges (for sorting)	V + E	V²	E
Best for	traversal, sparse	dense, edge tests	Kruskal, Bellman-Ford

One closing engineering note: inside the adjacency list, the bucket type matters more than people expect — arrays/vectors beat hash sets for iteration (cache), a Map<string, string[]> beats object-keyed lookups in JavaScript, and sorting each bucket (as this site’s graph inputs do) buys deterministic traversal order, which is what makes traces — and tests, and debugging sessions — reproducible. Determinism is a representation property too.