1
The matrix is symmetric with a zero diagonal
For a simple undirected graph. Symmetry is the relation being symmetric; the zero diagonal is the absence of loops.
Lesson · Graphs and Trees · Basics
Graph Representations
The same graph stored two ways. The matrix answers "are these adjacent" instantly and costs n² space; the list is compact and iterates neighbours quickly. And Aᵏ counts walks.
adjacency matrix n × n, A[i][j] = 1 if i ~ j
adjacency list one neighbour list per vertex
matrix: O(1) adjacency test, O(n²) space
Aᵏ[i][j] = number of walks of length k from i to j
Two structures, one graph
Core ideas
What this lesson establishes
The choice is a trade between space and which operation is fast, and for sparse graphs it is not close.
2
Lists win for sparse graphs
Most real graphs have |E| far below n². A road network with a million junctions has a few million edges and a matrix would need 10¹² entries.
3
Matrix powers count walks
Aᵏ[i][j] is the number of walks of length exactly k, because matrix multiplication sums over the intermediate vertex.
The material
Storing a graph
Both structures, their costs, and the one theorem about powers.
Definition · Adjacency matrix
The n × n matrix A with A[i][j] = 1 when vertices i and j are adjacent and 0 otherwise. For a simple undirected graph it is symmetric with zero diagonal.
Definition · Adjacency list
For each vertex, the list of its neighbours. Total space Θ(n + |E|), since each edge appears in two lists.
operation matrix list
is u adjacent to v? O(1) O(deg u)
iterate the neighbours of v O(n) O(deg v)
space Θ(n²) Θ(n + |E|)
add an edge O(1) O(1)
iterate all edges O(n²) Θ(n + |E|)
The O and Θ in the table are the notation of “Divide-and-Conquer Recurrences”, in Induction and Recursion: Θ(n + |E|) means proportional to n + |E| up to a constant factor, and O(1) means bounded by a constant. “Big-O, Big-Omega and Big-Theta” in Algorithms and Complexity makes both precise; here they are read as "linear" and "constant".
The traversals of “Breadth-First and Depth-First Search” iterate neighbours constantly, so an adjacency list gives breadth-first search a running time of Θ(n + |E|) while a matrix gives Θ(n²). On a sparse graph that is the difference between linear and quadratic.
The matrix wins when the graph is dense, when adjacency tests dominate, or when the linear algebra of the next theorem is wanted.
Theorem · Matrix powers count walks
For a graph with adjacency matrix A, the entry Aᵏ[i][j] is the number of walks of length exactly k from vertex i to vertex j. A walk may repeat vertices and edges.
By induction on k. For k = 1 the claim is the definition of A.
Assume it for k. A walk of length k+1 from i to j is a walk of length k from i to some t, followed by an edge from t to j. Summing over t gives Σ_t A^k[i][t] · A[t][j], which is exactly A^{k+1}[i][j] by the definition of matrix multiplication.
□
The proof is the definition of matrix multiplication read as a combinatorial statement: the sum over the middle index is the sum over the intermediate vertex.
Example · Counting triangles
A³[v][v] counts closed walks of length 3 from v back to itself, and each such walk is a triangle traversed from v. Each triangle gives 6 closed walks — three starting vertices, two directions — so the number of triangles is (Σ_v A³[v][v]) / 6, one sixth of the trace of A³.
That is a genuine algorithm: matrix multiplication counts triangles in O(n^ω) where ω < 2.4 is the matrix multiplication exponent, which beats the obvious O(n³) enumeration. It is one of the standard examples of algebra outperforming combinatorics.
Other representations
- Edge list. Just the pairs. Minimal space, and every query is a scan. Kruskal's algorithm in “Spanning Trees and Minimum Spanning Trees” sorts exactly this.
- Incidence matrix. Rows are vertices, columns edges, with a 1 where they meet. Useful in flow problems and rarely elsewhere here.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Choosing a representation
Ask which operation dominates.
1
Estimate the density
|E| near n² is dense and favours the matrix; |E| near n is sparse and favours lists, usually decisively.
2
Ask which query dominates
Repeated adjacency tests favour the matrix; repeated neighbour iteration favours lists.
3
Check the space budget
n² entries is impossible past a few tens of thousands of vertices. Real large graphs are always stored as lists.
4
Use powers when counting walks
Aᵏ answers walk-counting questions directly, and nothing else does so cleanly.
Representations
Score 0 / 0Choose the answer you can justify.
Walks in a 4-cycle
C₄ with vertices 1–2–3–4–1.
0 1 0 1 2 0 2 0
A = 1 0 1 0 A² = 0 2 0 2
0 1 0 1 2 0 2 0
1 0 1 0 0 2 0 2
A²[1][1] = 2: the walks 1→2→1 and 1→4→1 — which is deg(1).
A²[1][3] = 2: the walks 1→2→3 and 1→4→3.
A²[1][2] = 0: no walk of length 2 joins adjacent vertices here,
because C₄ is bipartite — “Bipartite Graphs”.
trace(A³) = 0, so C₄ contains no triangle. ✓
The zeros in A² at adjacent positions are the bipartiteness of “Bipartite Graphs” showing up in the algebra: in a bipartite graph every walk of even length ends on the same side it started, so it can never end at a neighbour.
Common mistakes
1
Confusing walks with pathsAᵏ counts walks, which may revisit vertices. Counting paths is a much harder problem with no matrix formula.
2
Using a matrix for a large sparse graphThe space is quadratic and almost all of it is zeros. Lists are the default for anything real.
3
Forgetting each edge appears twice in the listsSo the total list length is 2|E|, not |E|. It matters for the space estimate and for iterating edges without duplication.
Check your understanding
✓
Finish when you can predict which structure suits a problem.
For a road network of a million junctions with an average of three roads each, state the space each representation needs: |E| = 1.5 million, so the lists hold 2|E| = 3 million entries against the matrix's 10¹² — a factor of about 300 000. Then say which queries each makes cheap.
Note: Sparse matrix formats used in practice — compressed sparse row and its relatives — are adjacency lists with the indices packed into flat arrays. The trade-off in the table is the one every graph library is designed around.