Adjacency Matrix

Learn how graphs can be represented in code using adjacency matrices.

Let’s check out how to implement data structures to represent graphs. We’ll work with the following example graph:

g c c a a c->a d d c->d b b a->b b->c b->a b->d
An example graph with 4 nodes and 6 edges.

Representing the vertices

When discussing graphs, we usually think of the vertices as a set VV. In the example graph, the set of vertices is V={a,b,c,d}V = \{a, b, c, d\}.

But when working with graphs in code, it is more convenient to assign increasing integer IDs to the nodes so that information about them can be stored efficiently in an array-like data structure, such as a C++ vector.

In our example graph, we could map the node names to integer IDs like this:

  • a0a \to 0
  • b1b \to 1
  • c2c \to 2
  • d3d \to 3

The transformed graph is

g 2 2 0 0 2->0 3 3 2->3 1 1 0->1 1->2 1->0 1->3
The example graph with integer node names

If a graph has n=Vn = |V| nodes, the node IDs are integers 0,1,,n10, 1, \ldots, n-1. That means that we actually only need the single number nn to represent the set of nodes.

All of our graph algorithms will work on these integer node IDs. If the original names of the nodes (a,b,c,da, b, c, d) are still needed in the application, they can be stored for future reference.

vector<string> nodeNames = {"a", "b", "c", "d"};
map<string, int> nameToId = {{"a", 0}, {"b", 1}, {"c", 2}, {"d", 3}};

Adjacency matrix

Now that we’ve got the nodes covered, let’s look into data structures for the edges. There are two common ways to represent them: adjacency matrices and adjacency lists. Recall that two vertices are called adjacent if they are connected by an edge. In this lesson, we’ll check out the adjacency matrix data structure.

The adjacency matrix is a square matrix AA with nn rows and nn columns. The entries of the matrix are binary, either 00 or 11. The entry A[i,j]A[i, j] in the ii-th row and the jj-th column is 11 when the nodes ii and jj are connected by an edge, otherwise, it is 00.

Since our nodes are represented by integers starting with 00, our matrix is also 00-indexed: A[0,0]A[0, 0] is the top left entry, and A[n1,n1]A[n-1, n-1] is the bottom right entry.

Let’s look again at our example graph from above.

g 2 2 0 0 2->0 3 3 2->3 1 1 0->1 1->2 1->0 1->3
The example graph with integer node names.

Its adjacency matrix is

(0100101110010000)\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}

For example, the entry A[0,1]A[0, 1] is 11, because there is an edge from node 00 to node 11 in our graph. On the other hand, the entry A[3,2]A[3, 2] is 00, because there is no edge from node 33 to node 22 in our graph.

Since we only consider simple graphs without self-loops, the matrix’s main diagonal is always filled with zeros.

In an undirected graph, the adjacency matrix will always be symmetrical:

A[i,j]=A[j,i]for all0in1,0jn1A[i,j] = A[j, i] \quad \text{for all} \quad 0 \leq i \leq n-1, 0 \leq j \leq n-1

This is due to the symmetry condition on the edge set.

Implementing the adjacency matrix

In code, the adjacency matrix can be implemented naively using vectors of integers.

Press + to interact
#include <vector>
#include <iostream>
using namespace std;
int main() {
int n = 4;
vector<vector<int>> adjacencyMatrix(n, vector<int>(n, 0)); // initialize with zeros
// add edges using a loop over a vector of (source, target) pairs
vector<pair<int, int>> edges {{0, 1}, {1, 0}, {1, 2}, {1, 3}, {2, 0}, {2, 3}};
for (auto [u, v] : edges) {
adjacencyMatrix[u][v] = 1;
}
cout << "Edge from 0 to 1: " << adjacencyMatrix[0][1] << endl;
cout << "No edge from 0 to 3: " << adjacencyMatrix[0][3] << endl;
}

Some optimizations are possible in this implementation:

  • Instead of a nested vector of vectors, we can use a single vector with nnn*n entries, where A[i,j]A[i, j] is stored at index ni+jn*i+j.
  • Instead of a vector<int>, we can use a vector<bool>, which stores only one bit per entry.

When going with these optimizations, it is best to write a wrapper class that handles the indexing and also hides the vector<bool> object from the outside because it does not conform to the STL container interface.

Press + to interact
#include <vector>
#include <iostream>
using namespace std;
class AdjacencyMatrix {
private:
vector<bool> adj;
int n;
public:
AdjacencyMatrix(int _n)
: n {_n}
, adj {vector<bool>(_n*_n, 0)}
{}
void addEdge(int source, int target) {
this->adj[this->n * source + target] = true;
}
void removeEdge(int source, int target) {
this->adj[this->n * source + target] = false;
}
bool getEdge(int source, int target) {
return this->adj[this->n * source + target];
}
};
int main() {
int n = 4;
AdjacencyMatrix adjacencyMatrix(n); // create empty matrix
// add edges using a loop over a vector of (source, target) pairs
vector<pair<int, int>> edges {{0, 1}, {1, 0}, {1, 2}, {1, 3}, {2, 0}, {2, 3}};
for (auto [u, v] : edges) {
adjacencyMatrix.addEdge(u, v);
}
cout << boolalpha; // print booleans as true / false
cout << "Edge from 0 to 1: " << adjacencyMatrix.getEdge(0, 1) << endl;
cout << "No edge from 0 to 3: " << adjacencyMatrix.getEdge(0, 3) << endl;
}

In the above code snippet, we implemented an AdjacencyMatrix class, which uses these optimizations. The interface of the class consists of the functions getEdge, addEdge, and removeEdge that can be used to check and modify the edges. The actual representation of the adjacency matrix as a vector<bool> is an implementation detail hidden from the user of the class.