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.
Representation Contract
An adjacency matrix expects vertices to be mapped to integer indexes. matrix[i][j] answers whether an edge from vertex i to vertex j exists, or stores the weight of that edge.
The matrix must have one row and one column for every vertex. For an undirected graph, matrix[i][j] and matrix[j][i] should agree.
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.
Edge Lookup
The main advantage is direct lookup:
if matrix[a][b]:
print("edge exists")This is O(1). An adjacency list might need to scan the neighbors of a.
Weighted Matrix
A weighted graph can use numbers:
INF = float("inf")
matrix = [
[0, 5, INF],
[INF, 0, 2],
[INF, INF, 0],
]Here INF means no direct edge. This form is common for Floyd-Warshall.
Complexity
An adjacency matrix uses O(V^2) space whether the graph has many edges or only a few. Scanning all neighbors of a vertex takes O(V) because the whole row must be checked.
This cost is acceptable for small or dense graphs, but wasteful for large sparse graphs.
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.
Another common mistake is forgetting symmetry in an undirected matrix. If a connects to b, then both matrix[a][b] and matrix[b][a] should be set.
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.
Do not use it by default for large sparse graphs. An adjacency list is usually more memory-efficient.
The Main Point
An adjacency matrix trades memory for direct edge lookup. It fits small or dense graphs better than large sparse graphs.