Graph Representations — Mathematics Knowledge System

Overview

A graph G = (V, E) can be stored in a computer in several standard ways, and the choice of representation drives the running time of every graph algorithm built on top of it. The two workhorse representations are the adjacency matrix, an |V|×|V| grid of 0s and 1s (or edge weights) where entry (i, j) records whether an edge connects vertex i to vertex j, and the adjacency list, where each vertex keeps a list of only its neighbors. A graph, viewed set-theoretically, is exactly a binary relation on V (the edge relation), so adjacency matrices are literally the relation matrices of that relation, and the two representations trade off differently depending on how dense or sparse the edge set is: adjacency matrices give O(1) edge lookups but cost Θ(|V|²) space regardless of how many edges exist, while adjacency lists cost Θ(|V| + |E|) space and are far more efficient for the sparse graphs (|E| ≪ |V|²) that dominate real-world applications like road networks and social graphs.

Intuition

The adjacency matrix is a lookup table: to check 'are vertices 3 and 7 connected?' you read one cell, A[3][7], in constant time — but you pay for an n×n grid whether or not most of it is zeros. The adjacency list is a phone book: each vertex only keeps track of who it's actually connected to, so a sparse graph (like a road network where each city connects to only a handful of others, not every other city) stores far less. For an undirected graph, the adjacency matrix is symmetric (A = Aᵀ) because an edge {u, v} means both A[u][v] and A[v][u] are 1, and the row sum at vertex v equals its degree — summing every row sum double-counts every edge once from each endpoint, which is exactly the handshaking lemma.

Formal Definition

Definition

For a graph G = (V, E) with V = {v_1,…,v_n}, the adjacency matrix A is the n×n matrix with:

A_{ij} = \begin{cases} 1 & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases}

Adjacency matrix entry

\text{Adj}[v_i] = \{\, v_j \in V : (v_i, v_j) \in E \,\}

Adjacency list at vertex v_i

\sum_{i=1}^{n} \deg(v_i) = 2|E| \qquad \text{(undirected graph)}

Handshaking lemma — sum of row sums of A

\text{Space: } \Theta(|V|^2) \text{ (matrix)} \quad \text{vs.} \quad \Theta(|V| + |E|) \text{ (list)}

Space complexity comparison

Worked Examples

Vertex 1 connects to 2 and 3, so row 1 has 1s in columns 2 and 3.
$A_1 = [0, 1, 1, 0]$
Vertex 2 connects to 1 and 3.
$A_2 = [1, 0, 1, 0]$
Vertex 3 connects to 1, 2, and 4.
$A_3 = [1, 1, 0, 1]$
Vertex 4 connects only to 3.
$A_4 = [0, 0, 1, 0]$

Answer: A = [[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]] — symmetric, as expected for an undirected graph.

Practice Problems

Difficulty 3/10

For the adjacency list Adj[1]={2,3}, Adj[2]={1}, Adj[3]={1}, how many edges does this undirected graph have?

Difficulty 4/10

A graph has 6 vertices and its adjacency matrix has 18 entries equal to 1 (counting both (i,j) and (j,i) for each undirected edge). How many edges does the graph have?

Difficulty 6/10

A social network has 10,000 users and each user follows about 50 others on average (a sparse graph). Compare the storage needed for an adjacency matrix versus an adjacency list, roughly, in number of entries stored.

Quiz

Summary

A graph is a binary relation on its vertex set; the adjacency matrix is literally that relation's matrix representation.
Adjacency matrix: n×n grid, O(1) edge lookup, but Θ(|V|²) space regardless of how many edges actually exist.
Adjacency list: each vertex stores only its neighbors, giving Θ(|V|+|E|) space — much better for sparse graphs.
For undirected graphs the adjacency matrix is symmetric, and the sum of all row sums (degrees) equals 2|E| (the handshaking lemma).
The choice of representation is driven by graph density and the operations needed: dense graphs and frequent adjacency tests favor matrices; sparse graphs and traversal-heavy algorithms (BFS/DFS) favor lists.

References

WebsiteWikipedia — Adjacency matrix
WebsiteWikipedia — Adjacency list