An adjacency matrix stores graph connections in a two-dimensional table. The cell at row i and column j says whether an edge from i to j exists.
It is useful when the algorithm needs fast edge lookup between specific pairs of vertices.
Core Idea
For V vertices, an adjacency matrix uses V * V cells. Checking whether an edge exists can be constant time, but scanning all neighbors of one vertex may require checking an entire row.
This representation is often reasonable for dense graphs and small graphs.
Python Example
matrix = [
[False, True, True],
[True, False, False],
[True, False, False],
]
has_edge = matrix[0][2]has_edge is True, so vertex 0 is connected to vertex 2.
Common Confusions
An adjacency matrix can use booleans for unweighted graphs or numbers for weighted graphs. A special value may be needed to mean “no edge.”
The matrix can waste memory for sparse graphs because most cells may be empty or false.
When To Use It
Use an adjacency matrix when the graph is dense, the number of vertices is small, or the algorithm frequently asks whether a particular edge exists.