Graph Representations

The 10-second versionCopy Anchor Link

A graph is nothing more than a set of vertices (the things) and edges (the connections between them). To make a computer work with one, you pick how to store those connections: either keep, for every vertex, a list of its neighbours — the adjacency list — or keep a grid of yes/no cells saying which pairs are connected — the adjacency matrix. Same graph, two very different memories. One is cheap and slow to test edges; the other is fast to test edges and wasteful of space. The whole art of this page is knowing which one your problem wants.

Why this existedCopy Anchor Link

It's 1736 in Königsberg, a Prussian city built on both banks of a river with two islands in the middle, all joined by seven bridges. The townsfolk have a puzzle they can't solve: can you walk through the city crossing every bridge exactly once? People try for years and always get stuck.

A young Leonhard Euler — already a famous mathematician — hears about it and does something that had never quite been done. He throws away the map.

• 1736 — Euler publishes his solution, and in doing so invents the whole idea of a graph. He stops caring about bridges and riverbanks as places and treats them as pure connections: landmasses become dots, bridges become lines between dots. The geography is gone; only the structure remains.
• 1847 — Gustav Kirchhoff analyzes electrical networks as graphs and proves a beautiful theorem about spanning trees. Graphs leap from puzzles into engineering.
• 1852 — the four-colour question (can every map be coloured with four colours?) puts graphs at the centre of pure mathematics for the next century.
• 1959–1961 — Moore and Lee turn graphs into algorithms (search, routing), and suddenly the data structure matters as much as the theory.

Why did it matter then? Because Euler showed that a messy real-world question could be answered by looking at connections only, ignoring distance, direction and shape. Strip a problem to its graph and the answer often falls out. Every routing app, friend suggestion and build system since is standing on that one move.

Inside the inventor's headCopy Anchor Link

Euler starts, as anyone would, by trying to walk it. Pick a starting bank, cross a bridge, cross another, and watch the trap close: after five or six bridges he always ends up stranded, with bridges behind him he can't reuse and bridges ahead he can't reach. He restarts from a different bank. Different order, same wall.

Then the pivot — the move that founds a branch of mathematics. Euler notices that all of his distance and direction fiddling was noise. The only thing the puzzle ever asks is which landmass touches which bridge. So he deletes the geography: each landmass becomes a dot, each bridge a line. Now the puzzle is purely about dots and lines — and a dot's degree, the number of lines touching it, is everything.

His argument is a gem of clarity. Walk across a landmass and you enter by one bridge and leave by another — so every landmass you merely pass through uses bridges in pairs. Only the landmass you start on and the one you end on can be odd, because you're inside each of them an odd number of times. Count the degrees in Königsberg:

Four odd landmasses. The puzzle is impossible, and Euler proves it without ever drawing the city again.

But notice what he had to build to say that: a representation. In his head, the map became a list of "which dot connects to which". That's a storage decision, and it's the decision this page is about. The naive version of it — just keep every bridge as a pair of dots — works, but asking "what touches this landmass?" forces you to read every bridge:

// Naive: keep every edge as a flat pair. To find vertex 2's neighbours, scan them all.const edges = [[0, 1], [0, 2], [1, 2], [2, 3], [3, 4]];const naive = [];                          // O(E) scan, every single timefor (const [a, b] of edges) {  if (a === 2) naive.push(b);  else if (b === 2) naive.push(a);}console.log(naive);                        // [1, 0, 3]// Better: give every vertex its own array of neighbours — O(deg(2)), not O(E).const adj = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3]];console.log(adj[2]);                       // [0, 1, 3]

That single change — from "one list of edges" to "one list of neighbours per vertex" — is the adjacency list, and it's what makes every search algorithm on the next few pages fast.

The final approachCopy Anchor Link

The graph we'll useCopy Anchor Link

Five vertices, five undirected edges, drawn once and then stored two ways:

Two ways to store itCopy Anchor Link

The adjacency list for our graph — vertex v maps to the list of vertices it touches:

The adjacency matrix — cell (i, j) is 1 when there's an edge, 0 otherwise:

For an undirected graph the matrix is symmetric across its diagonal — M[i][j] always equals M[j][i], because "i touches j" and "j touches i" are the same fact. For a directed graph (an arrow, not a line) the matrix can be lopsided: an edge i → j sets M[i][j] but leaves M[j][i] alone. And for a weighted graph you store the weight in the cell instead of a plain 1, with some sentinel like 0 or infinity for "no edge".

The invariants that make it correctCopy Anchor Link

1. The handshake lemma. The degrees sum to exactly twice the number of edges. Our degrees 2 + 2 + 3 + 2 + 1 = 10, and there are 5 undirected edges — 2 × 5 = 10. This is the exact tool Euler used to kill the Königsberg walk.
2. Matrix symmetry. In an undirected graph, M[i][j] == M[j][i] for every pair. Fill one triangle and you've filled both.
3. List–matrix agreement. j appears in adj[i] if and only if M[i][j] says an edge exists. The two representations are two views of one truth.
4. Edges are counted once or twice, deliberately. An adjacency list stores each undirected edge twice (once in each endpoint's list) — that's why its size is V + 2E, written O(V + E).

It in codeCopy Anchor Link

Building an adjacency list from a bare edge list is the first thing you do with any graph, in any language:

const V = 5;const edges = [[0, 1], [0, 2], [1, 2], [2, 3], [3, 4]];// An array of arrays: adj[v] is the neighbour list of v.const adj = Array.from({ length: V }, () => []);for (const [u, v] of edges) {  adj[u].push(v);  adj[v].push(u);                           // undirected: add both directions}console.log(adj[2]);                        // [0, 1, 3]

Cost tableCopy Anchor Link

The trade is crisp. A list is small and fast at walking a vertex's neighbourhood — crucial for search, where you spend your whole life iterating neighbours. A matrix is big but answers "are these two connected?" in one memory read, and it lets you do linear-algebra tricks. Real graphs are almost always sparse — a person has hundreds of friends, not billions — so the list wins by default, and the matrix shows up only when edges are genuinely dense.

A worked traceCopy Anchor Link

Only one thing actually differs between the two, and it's the neighbour walk. From vertex 2, the list gives its three neighbours in O(deg(2)) = O(3); the matrix hands you all five candidates and you inspect the row:

For this graph the difference is trivial. Scale to a million vertices with three connections each and the matrix reads a million cells to find three neighbours while the list reads three. That gap is the whole reason graphs get their own data-structure page.

Where you meet it todayCopy Anchor Link

• Social networks. "Friends of friends" runs on an adjacency list — everyone is connected to a handful of people, so the graph is wildly sparse.
• Maps and routing. A road network is a weighted adjacency list: each vertex stores its neighbours and the road length to each. GPS navigation lives here.
• Web graphs. Pages link to a few others; a crawler and a PageRank pass both walk an adjacency list (or its compressed cousin).
• Dense problems. When the graph really is dense — some scheduling and flow problems, most textbook matrix algorithms — the adjacency matrix's O(1) edge test and matrix powers win.

Here's a very real use: a matrix power counts paths. M squared has (M²)[i][j] equal to the number of 2-hop routes from i to j, which is exactly how "people you may know" works under the hood:

const V = 5;const M = [  [0, 1, 1, 0, 0], [1, 0, 1, 0, 0], [1, 1, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0],];let pairs = 0;for (let i = 0; i < V; i++)  for (let j = 0; j < V; j++) {    let hops = 0;    for (let k = 0; k < V; k++) hops += M[i][k] * M[k][j]; // (M²)[i][j]    if (i !== j && hops > 0) pairs++;                      // j reachable from i in 2 hops  }console.log(pairs);

RecapCopy Anchor Link

• A graph is vertices plus edges; Euler's Königsberg paper (1736) invented the abstraction by throwing away geography and keeping only connections.
• Adjacency list: O(V + E) space, O(deg) neighbour walk — the default for real, sparse graphs.
• Adjacency matrix: O(V²) space, O(1) edge test — for dense graphs and algebra tricks.
• Directed, undirected and weighted are all the same skeleton with a rule about how edges are stored (one direction, both, or a number).
• The handshake lemma — degrees sum to twice the edge count — is your first sanity check on any graph.

Next up: Breadth-First Search — the first algorithm that actually walks the graph we just learned to store.