Card 05/ 08
Adjacency List vs Adjacency Matrix
The list grows with the edges, and the matrix with the square of the vertices.
An adjacency list and an adjacency matrix store the same graph, and the choice between them comes down to one question: how many of the possible edges exist. This card covers what each operation costs in each representation, how density decides between them, and the one job where a plain edge list is the right choice.
An adjacency list keeps one list of neighbours per vertex. An adjacency matrix is a V by V grid with a mark in row u, column v when an edge joins them. An edge list is the plain list of joined pairs. V is the number of vertices, E the number of edges, and the degree of a vertex is how many edges it has. The table compares the three.
| Operation | Adjacency list | Adjacency matrix | Edge list |
|---|---|---|---|
| Check whether edge u-v exists | O(degree of u), a scan of one list | O(1), one cell | O(E), a scan of every edge |
| List the neighbours of v | O(degree of v) | O(V), a scan of the whole row | O(E) |
| Add an edge | O(1), two appends | O(1), two cells | O(1), one append |
| Remove an edge | O(degree), a search of two lists | O(1), two cells | O(E) |
| Visit every edge | O(V + E) | O(V²) | O(E) |
| Memory | O(V + E) | O(V²) | O(E) |
Density is the share of possible edges that exist, and it decides the choice. A graph is sparse when E is close to V and dense when E is close to V², the most an undirected graph can have being V × (V - 1) / 2. A run counted the storage for three graphs.
| Graph | Edges | List entries | Matrix cells |
|---|---|---|---|
| 1,000 vertices, 4 edges at each | 2,000 | 4,000 | 1,000,000 |
| 1,000 vertices, every pair joined | 499,500 | 999,000 | 1,000,000 |
| 1,000,000 vertices, 4 edges at each | 2,000,000 | 4,000,000 | 1,000,000,000,000 |
On the sparse graphs the matrix spent 250 times, then 250,000 times, as much space, almost all of it on cells holding 0. On the complete graph the two were about the same size, and there the matrix's O(1) edge check comes at no extra cost. Most graphs met in practice, such as road networks, social networks and the links between web pages, are sparse, which is why the adjacency list is the default.
The edge list loses on every neighbour question but is the smallest and the easiest to sort. That makes it the right input for algorithms that work through edges in order of weight, such as Kruskal's algorithm for connecting every vertex at the least total cost, which sorts the edges and never asks for a vertex's neighbours.
A rule of thumb: use the adjacency list unless the graph is dense or small and the code checks single edges far more often than it lists neighbours; keep an edge list when the algorithm only sorts or scans the edges.
← → move through sections and cards