How Graphs Are Stored
Easy+80 XPA graph is dots and lines — but a computer stores it as numbers. See the picture, the matrix, and the list as the same graph.
No visualization loaded.
Watch
—
Press Run to begin.
A graph is just dots (nodes) joined by lines (edges) — cities linked by roads, people linked by friendships. But a computer can't store a 'picture'; it stores numbers. There are two classic ways to write a graph down. The adjacency MATRIX is a grid where row A, column B holds a 1 if there's an edge A–B (and a 0 if not). The adjacency LIST instead keeps, for each node, a little list of its neighbours. Both describe the EXACT same graph — this lesson draws all three side by side so you can watch one edge light up the picture, the matrix cell, and the list entry all at once.
▸What's an adjacency matrix?
A square grid with one row and one column per node. The cell at row A, column B is 1 if there's an edge from A to B, and 0 if there isn't. To check 'are A and B connected?' you just look at one cell — instant. The catch: even if a graph has almost no edges, you still store a full N×N grid of mostly-0s, so it uses O(N²) memory.
▸What's an adjacency list?
For each node, you keep a short list of just its neighbours. A → [B, E], B → [A, C], and so on. You only store edges that actually exist, so a graph with N nodes and E edges takes O(N+E) memory. The trade-off: to check 'are A and B connected?' you have to scan A's list instead of reading one cell.
▸When should I use which?
Use the MATRIX when the graph is DENSE (lots of edges) or when you constantly ask 'is X connected to Y?' — that check is O(1). Use the LIST when the graph is SPARSE (few edges, which is most real-world graphs) and you mostly want to walk a node's neighbours — it saves a ton of memory and is what BFS/DFS use.
▸What does 'sparse vs dense' mean?
It's about how many edges a graph has compared to the most it COULD have. With N nodes the maximum is about N² edges. 'Dense' means it has close to that many — most pairs are connected. 'Sparse' means it has far fewer, often only a handful per node (think road maps or friend networks). Sparse graphs waste most of a matrix on 0s, which is exactly when the list wins.
▸Why does direction matter?
An UNDIRECTED edge A–B goes both ways (a two-way street), so you set matrix[A][B] AND matrix[B][A] to 1, and you add B to A's list AND A to B's list — the matrix comes out symmetric. A DIRECTED edge A→B goes one way (a one-way street or a 'follows' on social media), so you set only matrix[A][B] and only add B to A's list. Same storage shapes, but you fill in one side or both.
How the work grows
O(1) — matrix edge-lookup is instant — doesn't grow at all. An adjacency matrix answers 'is A connected to B?' by reading a single cell — O(1) — but it pays for that with O(N²) memory, storing a 0 for every non-edge. An adjacency list flips the trade: it uses only O(N+E) memory (great when the graph is sparse), but checking a specific edge means scanning a node's neighbour list. Same graph, two storage choices, opposite strengths.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.