How it works
An adjacency list uses space proportional to vertices plus edges; an adjacency matrix uses the square of the vertices regardless of how few edges exist.
Choose the list for sparse graphs and the matrix when edge lookup between two named vertices must be constant.
Common error
Quoting a traversal cost without saying which representation it assumes. The answer differs.
Worked example
Example
Undirected edges: A-B, A-C, B-D, C-D
Adjacency of A: B, C
Adjacency of D: B, C
Each undirected edge appears at both endpointsAn adjacency list stores neighbors and is compact for sparse graphs. An adjacency matrix gives direct edge-membership checks but uses space proportional to the square of the vertex count.
Exercises
8.1.1 · Explain
For 5 vertices and 4 undirected edges, how many neighbor entries does a standard adjacency list store?
Show solution
There are 8 neighbor entries, two per undirected edge, in addition to the vertex-list structure.
8.1.2 · Explain
Compare adjacency-list and adjacency-matrix space in terms of V and E.
Show solution
An adjacency list uses O(V + E) space. An adjacency matrix uses O(V squared) space.