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(\mathrm{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.