Graph representations: lists vs matrices

Two ways to store a graph

A graph $G = (V, E)$ has a vertex set $V$ and an edge set $E$. Throughout graph analysis we abuse notation and write $V$ for $|V|$ and $E$ for $|E|$ inside asymptotic bounds. There are two standard representations, and choosing the right one is a recurring exam justification.

Adjacency list. An array (or dict) Adj of $|V|$ lists. Adj[u] holds every vertex $v$ with $(u, v) \in E$.

- Space: $\Theta(V + E)$ — one slot per vertex plus one list entry per edge. - Edge test $(u, v) \in E$? $O(\deg(u))$ — you must scan $u$'s list. - Best for sparse graphs ($|E| \ll |V|^2$), which is almost every real graph.

Adjacency matrix. A $|V| \times |V|$ matrix $A$ with $A[i][j] = 1$ iff $(i, j) \in E$.

- Space: $\Theta(V^2)$ regardless of edge count. - Edge test: $O(1)$ — one array lookup. - Best for dense graphs ($|E|$ near $|V|^2$) or when you need constant-time edge queries.

Why CLRS defaults to lists

Most graphs are sparse, and BFS, DFS, topological sort, and SCC all run in $\Theta(V + E)$ only with adjacency lists — the list lets each algorithm touch every vertex and every edge exactly once (aggregate analysis). On an adjacency matrix, "scan all neighbours of $u$" costs $\Theta(V)$ per vertex, dragging those same algorithms up to $\Theta(V^2)$ even on a sparse graph.

Worked example — the scale argument. A social network with $10^9$ users and $10^{10}$ friendships needs $\Theta(V + E) = \Theta(10^{10})$ list space but $\Theta(V^2) = \Theta(10^{18})$ matrix space — the matrix is physically impossible. For a complete graph the two converge: $|E| = \Theta(V^2)$, so a list costs $\Theta(V^2)$ too, and the matrix's $O(1)$ edge test wins.

How we model graphs in Python

We use a dict of lists: {u: [v1, v2, ...]}. A directed edge $(u, v)$ appends v to adj[u] only; an undirected edge appends both directions. The transpose $G^{\mathsf{T}}$ reverses every edge — needed later for strongly connected components.