Graph Representations, Explained

Before writing a single line of graph algorithm, you have to decide how the graph itself is stored, and that choice quietly sets the speed limit for everything downstream. A supply chain of 50 firms and a correlation network of 5,000 tickers are both "graphs," but storing them the same way is a mistake in one direction or the other.

Three representations, three trade-offs

An adjacency matrix is an $n \times n$ grid where cell (i, j) holds the edge weight between node $i$ and $j$ (or 0/infinity for "no edge"). Checking whether an edge exists is $O(1)$ — just index in. But it costs $O(n^2)$ memory regardless of how sparse the graph is, and enumerating the neighbours of a single node costs $O(n)$ even if that node has one edge.

An adjacency list stores, for each node, only the list of its actual neighbours. Memory is $O(V + E)$ — proportional to what's actually there. Enumerating a node's neighbours costs time proportional to its degree, which is what every traversal algorithm (BFS, DFS, Dijkstra) actually wants. The cost: checking whether a specific edge (i, j) exists means scanning node $i$ 's list, $O(\deg(i))$ instead of $O(1)$ .

An edge list is just a flat list of (u, v, weight) triples. It is the cheapest to build and the natural format for algorithms that process edges in a fixed order regardless of structure — Kruskal's minimum spanning tree sorts the edge list once and never needs neighbour lookups at all.

Same graph, two storage strategies. The matrix wastes space on the zeros; the list stores only real edges but can't answer "is A-C connected?" in O(1).

Worked example: which one for which task

A correlation network over 5,000 tickers where most pairs are weakly related (say, only the top 20 correlations per name are kept) has $V = 5{,}000$ and $E \approx 100{,}000$ . An adjacency matrix costs $5{,}000^2 = 25{,}000{,}000$ cells; an adjacency list costs roughly $V + E = 105{,}000$ entries — over 200x smaller. Running a shortest-path search from one ticker touches only its stored neighbours in a list, versus scanning all 5,000 columns of its matrix row every step. For this graph, the list wins decisively. A dense graph — say, a fully-priced options chain where every strike-tenor pair has a quoted edge to every other — is the rare case where the matrix's $O(1)$ edge lookup earns back its memory cost.

# adjacency list, the default choice for sparse graphs
graph = {"A": [("B", 1), ("D", 1)],
         "B": [("A", 1), ("C", 1)],
         "C": [("B", 1), ("D", 1)],
         "D": [("A", 1), ("C", 1)]}

Adjacency list for sparse graphs (most real-world ones), adjacency matrix only when the graph is dense or you need $O(1)$ "does this edge exist" checks, edge list when you process all edges once regardless of node structure (Kruskal, cycle detection by sorting weights).

Picking a matrix by default is the single most common reason a graph algorithm that should run in milliseconds times out — a matrix forces every neighbour scan to $O(V)$ even when the true degree is 3. Default to a list unless you have a specific reason for $O(1)$ edge lookups.

Where it shows up

Interviewers rarely test this in isolation, but every graph problem starts with "how do I represent the input," and choosing a matrix for a sparse graph is a red flag they notice immediately. On a desk it matters concretely: a counterparty exposure network, a supply-chain graph, or an order-routing venue graph are all sparse, and storing them densely wastes memory and CPU that compounds every time an algorithm touches the graph.

Graph Representations

Three representations, three trade-offs

Worked example: which one for which task

Where it shows up

Related concepts

Practice in interviews

Further reading