A seating chart versus a phone's contact list
An adjacency matrix checks any connection instantly but wastes space on pairs with no relationship. An adjacency list stores only real connections but costs more to check one specific pair.
After this lesson
You should be able to
- Build an adjacency matrix for a small graph.
- Build an adjacency list for the same graph.
- State the space and lookup-time trade-off between the two.
The matrix: a full attendance grid
An adjacency matrix is a V-by-V grid, one row and one column per vertex. Cell [i][j] holds 1 if an edge runs from vertex i to vertex j, 0 otherwise. Checking whether two specific vertices are connected is one array lookup, always — exactly as fast whether the graph has two edges or two thousand.
The cost is space: a matrix always allocates V squared cells, regardless of how many edges actually exist. A social network of ten thousand people with an average of two hundred friends each would need a matrix of one hundred million cells to represent perhaps two million real edges — almost all of it wasted on pairs with no connection.
A B C D
A [ 0 1 1 0 ]
B [ 1 0 0 1 ]
C [ 1 0 0 1 ]
D [ 0 1 1 0 ]
/* row A, column B is 1: an edge exists from A to B */The list: only the contacts you actually have
An adjacency list keeps one list per vertex, holding only its actual neighbors — the same idea as a phone storing your contacts, not a grid of every phone number in the country marked yes-or-no. Space used is proportional to the number of edges that actually exist, which for a sparse graph — one with far fewer edges than the V-squared maximum — is dramatically smaller than a matrix.
The cost flips: checking whether two specific vertices are connected now means walking one vertex's whole list to look for the other — cheap when the list is short, slower when a vertex has thousands of neighbors.
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]
/* struct AdjNode { int vertex; struct AdjNode *next; };
one linked list per vertex — the exact shape from Unit I */Try it yourself
A graph has 1,000 vertices and 3,000 edges. Estimate the space an adjacency matrix needs versus an adjacency list, and say which representation fits better.
Need a hint?
A matrix needs V-squared cells regardless of edge count. A list needs space proportional to the edge count.
Check the worked solution
The matrix needs 1,000 x 1,000 = 1,000,000 cells, almost all storing a 0 for a pair that is not connected. The list needs space for roughly 3,000 entries, one per edge (or 6,000 for an undirected graph stored both ways). The list wins by more than two orders of magnitude here — this is exactly the sparse-graph case the previous section described, and it is the common case in practice.
Quick check
For a sparse graph — one with far fewer edges than the maximum possible — which representation is generally more space-efficient?
Why this lesson exists
Syllabus mapping
Representation of Graphs
Maps to course outcomes CO1, CO2.