An adjacency matrix is a square grid of numbers that represents which nodes in a graph are connected. You label each row and each column with a node, then fill in a 1 wherever two nodes share an edge and a 0 wherever they don’t. The result is a simple table that captures the entire structure of a graph in a format computers (and humans) can work with quickly.
The Basic Idea
Start with a graph that has n nodes. Your adjacency matrix will be an n × n grid. Assign each node a number from 1 to n (or 0 to n−1 if you’re coding). Those numbers become both the row labels and the column labels. The cell at row i, column j gets a 1 if there’s an edge between node i and node j, and a 0 if there isn’t.
That’s the entire concept. The non-zero entries in any given row tell you exactly which nodes that row’s node is connected to. If row 3 has 1s in columns 1 and 5, node 3 is connected to nodes 1 and 5.
Step-by-Step Construction
Here’s how to build one by hand for a small graph:
- List your nodes. Write down every node and assign each one a consistent index. For a graph with nodes A, B, C, D, you might use A=0, B=1, C=2, D=3.
- Create an empty grid. Draw an n × n table (4 × 4 in this case) and label both the rows and columns with your node indices.
- Fill in zeros everywhere. Start with the assumption that nothing is connected.
- Mark each edge. For every edge in your graph, find the corresponding row and column and change that 0 to a 1. If A connects to C, set position (0, 2) to 1.
For example, a triangle connecting nodes 0, 1, and 2 produces this matrix:
0 1 2
0 [ 0, 1, 1 ]
1 [ 1, 0, 1 ]
2 [ 1, 1, 0 ]
Every edge shows up twice because the connection goes both ways. That brings us to an important distinction.
Undirected vs. Directed Graphs
In an undirected graph, edges have no direction. If node 1 connects to node 2, then node 2 also connects to node 1. This means the matrix is always symmetric: the value at row i, column j is identical to the value at row j, column i. You could fold the matrix along its diagonal and the two halves would match perfectly.
In a directed graph, edges point one way. An edge from node 1 to node 2 doesn’t guarantee an edge from node 2 back to node 1. The convention is that row i, column j represents an edge from node i to node j. This means the matrix is not necessarily symmetric. You have to be careful about which direction you’re recording.
If you’re working with a social network where “A follows B” doesn’t mean “B follows A,” you need a directed adjacency matrix. If you’re mapping roads that go both ways, an undirected one works.
Weighted Graphs
Not all connections are equal. In a weighted graph, edges carry values representing distance, cost, capacity, or some other quantity. Instead of filling the matrix with 1s and 0s, you store the weight of each edge directly in the cell. An edge between nodes 2 and 4 with a weight of 7.5 means position (2, 4) holds 7.5.
Where there’s no edge, you typically store either zero or infinity, depending on the application. If you’re computing shortest paths, infinity (or a very large number) is the standard choice, because it signals “no direct route.” The diagonal is usually set to zero, since the distance from any node to itself is nothing.
Self-Loops and the Diagonal
In a simple graph (the most common type in textbooks), no node connects to itself. That means every value along the main diagonal of the matrix is 0. If your graph does allow self-loops, where a node has an edge back to itself, you place a 1 (or the edge weight) at position (i, i) for that node.
Multigraphs, which allow more than one edge between the same pair of nodes, can use integers greater than 1 in the matrix to represent the count of parallel edges. Position (2, 3) holding a 3 means there are three separate edges between nodes 2 and 3.
Building One in Code
The most common approach is to start with an edge list (a collection of pairs like (0, 1), (1, 2), (0, 2)) and convert it into a matrix. In Python, using NumPy:
import numpy as np
n = 4 # number of nodes
edges = [(0, 1), (1, 2), (0, 2), (2, 3)]
matrix = np.zeros((n, n), dtype=int)
for i, j in edges:
matrix[i][j] = 1
matrix[j][i] = 1 # remove this line for directed graphs
For directed graphs, you only set the cell in one direction. For weighted graphs, replace the 1 with the weight value. Libraries like NetworkX can also convert a graph object directly into a NumPy array with a single function call, which is useful when your graph is already built programmatically.
When an Adjacency Matrix Is the Right Choice
An adjacency matrix uses O(V²) memory, where V is the number of nodes. A graph with 1,000 nodes requires a million-entry table regardless of how many edges actually exist. For dense graphs, where most nodes connect to most other nodes, this cost is reasonable because you’d be storing nearly that much data anyway. The payoff is speed: checking whether two specific nodes are connected takes constant time. You just look up one cell.
For sparse graphs, where the edge count is much smaller than the possible maximum, an adjacency list is typically more efficient. Lists store only the edges that exist, using O(V + E) space. A social network with millions of users but only a few hundred connections per person would waste enormous memory as a full matrix.
That said, adjacency matrices shine when you need to perform matrix math on a graph. Algorithms for shortest paths, spectral clustering, and graph neural networks all rely on matrix operations that are straightforward with this representation. Multiplying the adjacency matrix by itself, for instance, tells you how many paths of length 2 exist between each pair of nodes.
Handling Large Sparse Matrices
If you need matrix format but your graph is sparse, compressed storage formats let you have both. Formats like compressed sparse row (CSR) store only the non-zero entries along with their positions, dramatically reducing memory for graphs with few edges relative to their size. In Python, SciPy’s sparse matrix tools handle this. CSR is particularly efficient for row slicing and fast matrix-vector products, which are the most common operations in graph algorithms.
The tradeoff is that modifying the structure of a sparse matrix (adding or removing edges) is slower than with a regular array. If your graph changes frequently, build it in a flexible format first and convert to CSR once the structure is final.