Graph Representation: Matrices and Lists

Core Idea

Graphs can be represented computationally in multiple ways. An adjacency matrix is an n×n matrix where entry (i,j) is 1 if there is an edge from vertex i to vertex j, and 0 otherwise. An adjacency list stores, for each vertex, the list of its neighbors. Adjacency matrices support O(1) edge lookup but use O(n²) space; adjacency lists use space proportional to vertices plus edges and are preferred for sparse graphs. Powers of the adjacency matrix count the number of walks of a given length between vertices.

How It's Best Learned

Practice converting between graph drawings and both matrix and list representations for the same graph. Compare storage trade-offs for dense versus sparse graphs with concrete examples. Compute A² for a small graph and verify it counts 2-step walks.

Common Misconceptions

• Assuming adjacency matrices are always symmetric — this is only true for undirected graphs.
• Ignoring space-versus-time trade-offs when choosing a representation for a given application.

Explainer

When you first learned about graphs, the representation was visual: vertices as dots, edges as lines. To compute with graphs — to run algorithms, store them in memory, or analyze their structure — you need a formal data structure. The two standard choices, adjacency matrices and adjacency lists, each make different operations fast and encode the same information differently.

An adjacency matrix is an n×n grid where entry A[i][j] = 1 if there is an edge from vertex i to vertex j, and 0 otherwise. For an undirected graph, it is symmetric. The key advantages: checking whether a specific edge exists is O(1) — just look up the entry. The key cost: it always uses n² space, regardless of how many edges exist. For a dense graph (many edges relative to n²) this is fine; for a sparse graph with only a handful of edges per vertex, most of the matrix is zeros and the space is wasted.

An adjacency list stores, for each vertex, only the list of its actual neighbors. Total storage is proportional to |V| + |E| — the number of vertices plus the number of edges. For sparse graphs (common in practice), this is dramatically smaller than n². The trade-off: checking whether a specific edge (i, j) exists requires scanning vertex i's neighbor list, which takes time proportional to i's degree rather than O(1). Many graph algorithms — BFS, DFS, shortest paths — naturally iterate over a vertex's neighbors rather than checking arbitrary edges, which is why they are typically implemented with adjacency lists.

The adjacency matrix also supports a striking algebraic property: the entry (A^m)[i][j] counts the number of walks of length m from vertex i to vertex j. This follows from matrix multiplication: (A²)[i][j] = Σ_k A[i][k] · A[k][j] sums over all intermediate vertices k, counting those where both legs of a 2-step walk exist. This property connects graph theory to linear algebra and enables techniques like computing reachability or counting paths using matrix exponentiation.

Choosing a representation is an engineering decision, not a mathematical one. The right answer depends on the graph's density, the operations your algorithm needs most frequently, and memory constraints. Understanding both representations — and being able to convert between them fluently — is the foundation for analyzing and implementing graph algorithms.