Graph Representations: Adjacency Lists and Matrices

A graph $G = (V, E)$ consists of a vertex set $V$ and an edge set $E \subseteq V \times V$. Let $n = |V|$ and $m = |E|$. The graph may be directed, where an edge $(u, v)$ points from $u$ to $v$ only, or undirected, where an edge $\{u, v\}$ is symmetric. A representation is simply a concrete data layout that answers two canonical queries that essentially every graph algorithm needs: enumerate the neighbors of a given vertex, and test whether a specific edge exists. The adjacency matrix representation fixes an ordering $v_1, \dots, v_n$ of the vertices and builds an $n \times n$ boolean (or weighted) matrix $A$, where

For a weighted graph, $A[i][j]$ stores the edge weight instead of $1$, with a sentinel (such as $\infty$ or a special "no edge" flag) in place of $0$. For an undirected graph the matrix is symmetric, $A[i][j] = A[j][i]$, so only the upper triangle carries independent information, though implementations usually still store the full square for uniform indexing. The adjacency list representation instead keeps, for each vertex $v$, an explicit list $\text{Adj}[v]$ containing only the vertices $u$ such that $(v, u) \in E$. This can be implemented as an array of linked lists, an array of dynamic arrays, or — in performance-critical systems — a single flattened array with an index array marking where each vertex's neighbor block starts (the CSR, compressed sparse row, layout used in graph-analytics engines). The key structural fact is that an adjacency list only ever stores real edges: a vertex with no neighbors costs a single empty list, not $n$ wasted matrix cells.

Both representations are built by the same conceptual procedure — read each edge once and record it in the appropriate structure — but they diverge in what gets written and how much space is reserved up front.

Building an adjacency matrix. Allocate the full $n \times n$ grid initialized to "no edge," then for each edge write into the matching cell(s). ``` BUILD-ADJ-MATRIX(V, E, directed) n = |V| allocate A[1..n][1..n], initialize every A[i][j] = 0 for each edge (u, v) in E A[u][v] = 1 // or weight(u, v) for weighted graphs if not directed A[v][u] = 1 // mirror the edge for symmetry return A ```

Building an adjacency list. Allocate $n$ empty lists, then append each endpoint to its partner's list. ``` BUILD-ADJ-LIST(V, E, directed) n = |V| allocate Adj[1..n], each an empty list for each edge (u, v) in E APPEND(Adj[u], v) if not directed APPEND(Adj[v], u) // undirected edge appears in both lists return Adj ```

Core queries, both representations. ``` HAS-EDGE-MATRIX(A, u, v) return A[u][v] != 0 // O(1) HAS-EDGE-LIST(Adj, u, v) for each w in Adj[u] // O(deg(u)) worst case if w == v return TRUE return FALSE NEIGHBORS-MATRIX(A, u, n) result = empty list for j = 1 to n // always scans n cells, even if no edges exist if A[u][j] != 0 APPEND(result, j) return result NEIGHBORS-LIST(Adj, u) return Adj[u] // O(deg(u)), no wasted work ``` The essential asymmetry is visible immediately: `NEIGHBORS-MATRIX` walks an entire row of length $n$ no matter how many real edges $u$ has, whereas `NEIGHBORS-LIST` touches exactly $\deg(u)$ cells and nothing more. That single difference is what makes traversal algorithms like Breadth-First Search and Depth-First Search run in $O(V + E)$ time on adjacency lists but $O(V^2)$ time on adjacency matrices.

Space. The adjacency matrix always allocates $n^2$ cells, giving $\Theta(V^2)$ space regardless of $m$. The adjacency list stores an array of $n$ list-heads plus one entry per directed edge — for an undirected graph, each edge contributes two entries (one in each endpoint's list) — giving $\Theta(V + E)$ space. When the graph is sparse, meaning $m = O(V)$ or more generally $m = o(V^2)$, the list is asymptotically smaller. When the graph is dense, with $m = \Theta(V^2)$ (a constant fraction of all possible edges present), the two become the same order, and the matrix's per-cell overhead is often lower in practice because it avoids pointer storage.

Time for the two canonical queries.

The reasoning behind each entry is direct from the pseudocode above, not incidental:

• Edge test on a matrix is $\Theta(1)$ because it is a single array dereference $A[u][v]$ — no search is involved by construction.
• Edge test on a list is $O(\deg(u))$ because in the worst case (edge absent, or it is the last entry) every neighbor of $u$ must be inspected before concluding.
• Neighbor enumeration on a matrix is always $\Theta(V)$, even for an isolated vertex with zero neighbors, because the algorithm must scan an entire row to know which cells are nonzero. This is the crucial asymmetry: the matrix pays for the absence of edges as much as their presence.
• Neighbor enumeration on a list is $\Theta(\deg(v))$ because the list contains nothing but real neighbors — no wasted scanning.

Correctness. Both structures are correct representations of $G$ in the following precise sense: for every ordered pair $(u, v) \in V \times V$, $(u,v) \in E \iff A[u][v] \neq 0 \iff v \in \text{Adj}[u]$. This equivalence is maintained as an invariant by the construction procedures: `BUILD-ADJ-MATRIX` and `BUILD-ADJ-LIST` both iterate over every edge in $E$ exactly once (twice for undirected graphs, once per endpoint) and record it in the corresponding structure, and neither structure is ever asked to record an edge not in $E$. Since the invariant holds after processing each edge and holds trivially before any edges are processed (empty matrix / empty lists correctly represent the empty edge set), it holds after all edges are processed — a simple loop invariant argument.

The honest tradeoff. There is no universally superior representation. A matrix wins when edge-existence queries dominate and the graph is dense (e.g., a complete-ish graph of pairwise similarities, or a small graph where $V^2$ comfortably fits in cache). A list wins when the graph is sparse and neighbor iteration dominates, which describes the overwhelming majority of real-world graphs — road networks, social graphs, web graphs, dependency graphs — where each vertex touches only a handful of others out of millions possible. A further practical note: for weighted graphs the matrix generalizes trivially (store weights instead of booleans), while the list must pair each neighbor with a weight, e.g. `Adj[u] = [(v1, w1), (v2, w2), ...]`, adding a constant-factor but not asymptotic cost.

Consider a small directed graph representing a course-prerequisite dependency: $V = \{$ CS101, CS102, CS201, CS301, MATH101 $\}$, with edges

Here $n = 5$, $m = 5$. Trace `BUILD-ADJ-LIST` and `BUILD-ADJ-MATRIX` edge by edge (order: CS101 < CS102 < CS201 < CS301 < MATH101 for matrix indexing).

Final adjacency list (only real edges stored, total entries = 5 = $m$): ``` Adj[CS101] = [CS102, CS201] Adj[CS102] = [CS201] Adj[CS201] = [CS301] Adj[CS301] = [] Adj[MATH101] = [CS201] ``` Final adjacency matrix (25 cells allocated, only 5 are 1 — 20 wasted zero-cells): ``` CS101 CS102 CS201 CS301 MATH101 CS101 [ 0 1 1 0 0 ] CS102 [ 0 0 1 0 0 ] CS201 [ 0 0 0 1 0 ] CS301 [ 0 0 0 0 0 ] MATH101 [ 0 0 1 0 0 ] ``` Now run the query "what must a student complete before taking CS201?" — i.e., enumerate the in-neighbors, or equivalently for outgoing-edge lists, check every vertex's list for CS201.

• With the list, if we also maintained a reverse adjacency list `RevAdj[CS201]`, the answer is a direct $\Theta(\deg^-(\text{CS201}))$ read: `[CS101, CS102, MATH101]`, 3 steps.
• With the matrix, scanning column CS201 costs $\Theta(n) = 5$ cell reads regardless of the true in-degree — here it happens to find 3 hits after touching 5 cells, but on a graph with $n = 10^6$ and the same in-degree of 3, the matrix would still touch all $10^6$ cells while the reverse list would touch exactly 3.

This is the concrete face of the asymptotic gap derived above: as $n$ grows with $m$ staying proportionally small (sparse graphs are the realistic case for dependency graphs, social networks, and road maps), the list's cost tracks the true answer size while the matrix's cost tracks the irrelevant universe size $n$.

The adjacency matrix traces its lineage to the birth of graph theory itself, where graphs were studied as combinatorial objects long before computers existed, and matrix representations of relations were standard tools in linear algebra and combinatorics. The adjacency list, by contrast, is fundamentally a computational idea — it only becomes the natural choice once one is reasoning about memory and running time on an actual machine, which places its systematic use squarely in the era of algorithm design as a formal discipline in the 1950s–70s.

Search engines and web crawlers store the link graph of the web — trillions of potential vertex pairs but only a sparse fraction realized as actual hyperlinks — using adjacency-list-style structures (often the CSR format) because an adjacency matrix would be astronomically larger than all the world's storage combined. Road-network routing systems (GPS navigation, ride-sharing dispatch) represent intersections and roads as sparse adjacency lists, since each intersection connects to only a handful of others regardless of how many total intersections exist in a country. Social networks represent friendships or follows as adjacency lists for the same reason — most users are connected to a tiny fraction of the whole user base. Compilers and build systems (Makefiles, package managers) represent dependency graphs between modules as adjacency lists to answer "what does this module depend on" without scanning irrelevant modules. Dense-graph cases do appear — small graphs in computational biology comparing all pairs of a few hundred proteins, or fully-connected similarity graphs in clustering — and there the adjacency matrix's constant-time lookups and cache-friendly row scans are genuinely the better engineering choice. This foundational representation choice is the substrate on which Breadth-First Search, Depth-First Search, and virtually every other graph algorithm is implemented, since their stated running times of $O(V + E)$ are only achievable when the underlying representation is an adjacency list.

Ask the tutor: How would the space and time tradeoffs change if the graph is stored using a hybrid structure, like a hash set of edges per vertex, instead of a plain list or matrix?