The Adjacency Matrix

An adjacency matrix stores a graph as a square grid with one row and one column per vertex, and the cell in row u, column v records whether an edge joins u to v. This card covers how the grid is laid out, why it is symmetric for an undirected graph, how it holds weights, and its two defining costs: any edge is checked in constant time, and the grid takes V² cells however few edges there are.

A graph is a set of vertices and the edges between pairs of them; V is the number of vertices and E the number of edges. The vertices are numbered 0 to V - 1 so that each has a row and a column, usually through a map from name to number.

The table draws the matrix for the undirected graph with vertices A to E and edges A-B, A-C, B-C, B-D, C-E and D-E. A 1 marks an edge and a 0 marks none, as a run that built the matrix printed them.

Row B reads 1 0 1 1 0, so the neighbours of B are A, C and D. Each undirected edge sets two cells, row u column v and row v column u, so the grid is symmetric about the diagonal from top left to bottom right: the run checked every pair and found it so. The 12 cells holding 1 are the same 12 entries an adjacency list would hold. The diagonal is all 0, because no vertex has an edge to itself.

A directed graph sets only the cell for the edge's own direction, so its matrix need not be symmetric. A weighted graph puts the weight in the cell instead of a 1, and marks a missing edge with a value no real weight can take, such as infinity or None.

The grid's strength is the edge check. Is B joined to D? Read row B, column D: one lookup, O(1), whatever the size of the graph. The run read 1 there, and 0 for A and E. Its cost is the space. Five vertices take 25 cells for 6 edges, and the grid always takes V² cells, so a thousand vertices take a million cells even with a few thousand edges. Listing the neighbours of a vertex means scanning its whole row, O(V), even when it has two neighbours, and adding a vertex means building a larger grid.

The matrix suits a dense graph, one where most pairs of vertices are joined, and code that asks "is u joined to v?" more often than "what are the neighbours of u?".