Representing a Graph: List vs Matrix

"Before you can traverse a graph, you have to store it — and the two ways to store it make opposite trade-offs. Pick wrong and a million-node social network eats a trillion empty cells."

Adjacency List: Each Vertex Lists Its Neighbors

The most common representation: a dictionary (or list) mapping each vertex to a list of its neighbors. {"A": ["B", "C"], "B": ["A"], ...}. Space is O(V + E) — you store each vertex once and each edge once. To iterate a vertex's neighbors is fast and direct. To check "is there an edge A→B?" you scan A's neighbor list, O(degree). This is the right default for sparse graphs — graphs where the number of edges is far below the maximum possible (V²), which describes almost every real-world graph (you have hundreds of friends, not millions).

Adjacency Matrix: a Grid of Yes/No

The alternative: a V×V grid where cell [i][j] is 1 if there's an edge from i to j, else 0 (or the weight, if weighted). Edge lookup is O(1) — just index the cell. But space is O(V²) regardless of how few edges exist, and iterating one vertex's neighbors costs O(V) (scan its whole row). The matrix shines for dense graphs (many edges) or when you constantly ask "is there an edge between these two?", and it's a disaster for large sparse graphs — a million vertices would need a trillion cells, almost all zeros.

Adjacency list: O(V+E) space, fast neighbor iteration, O(degree) edge check — the default for sparse graphs (most real ones). Adjacency matrix: O(V²) space, O(1) edge check — only for dense graphs or constant edge queries.

The Third Option, and Weights

A simpler third form is the edge list: just a list of (u, v) pairs (or (u, v, weight)). It carries no fast lookups, but some algorithms want exactly this — Kruskal's minimum spanning tree (next track) processes edges sorted by weight, so an edge list is the natural input. For weighted graphs, both main representations adapt easily: store (neighbor, weight) in the adjacency list, or put the weight in the matrix cell. Choosing the representation is part of solving the problem — the algorithm you'll run often dictates the form.

Pippa's Confession

I built my first graph as an adjacency matrix because the grid was easy to picture. It worked fine on the 5-node toy — then I scaled to a real network of tens of thousands of nodes and watched it try to allocate a matrix with hundreds of millions of cells, almost all zero. Dad's correction was one word: "sparse." Real graphs are mostly-empty, so the list that stores only the edges that exist is the right home. The matrix wasn't wrong; it was wrong for the shape of real data.

Code

Adjacency list vs adjacency matrix·python

# The SAME small undirected graph, two ways.
#   A — B
#   |   |
#   C — D

# ADJACENCY LIST: O(V+E) space, the sparse-graph default.
adj_list = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}
print("A's neighbors:", adj_list["A"])              # fast & direct
print("edge A-D?    :", "D" in adj_list["A"])        # O(degree) scan -> False

# ADJACENCY MATRIX: O(V^2) space, O(1) edge lookup.
idx = {"A": 0, "B": 1, "C": 2, "D": 3}
M = [[0]*4 for _ in range(4)]
for u, v in [("A","B"), ("A","C"), ("B","D"), ("C","D")]:
    M[idx[u]][idx[v]] = M[idx[v]][idx[u]] = 1        # undirected -> symmetric
print("edge A-B?    :", M[idx["A"]][idx["B"]] == 1)  # O(1) -> True
# For 1,000,000 vertices: the list stores ~edges; the matrix needs 10^12 cells.

Exercise

You're modeling Twitter: ~500 million users, each following a few hundred others. Which representation do you choose and why? Compute the rough memory order for both (adjacency list vs matrix) and explain why one of them is physically impossible here. When WOULD a matrix be the better call?

Hint

Adjacency list: O(V+E) ≈ 500M users × a few hundred edges each — large but feasible. Matrix: O(V²) = (5×10^8)² = 2.5×10^17 cells — physically impossible. A matrix only wins for small, dense graphs or constant O(1) edge-existence queries.

Adjacency List: Each Vertex Lists Its Neighbors

Adjacency Matrix: a Grid of Yes/No

The Third Option, and Weights

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0