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

We'll cover the following

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

An example graph with 4 nodes and 6 edges.

## Representing the vertices

When discussing graphs, we usually think of the vertices as a set $V$. In the example graph, the set of vertices is $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:

• $a \to 0$
• $b \to 1$
• $c \to 2$
• $d \to 3$

The transformed graph is

The example graph with integer node names

If a graph has $n = |V|$ nodes, the node IDs are integers $0, 1, \ldots, n-1$. That means that we actually only need the single number $n$ 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, 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}};


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 $A$ with $n$ rows and $n$ columns. The entries of the matrix are binary, either $0$ or $1$. The entry $A[i, j]$ in the $i$-th row and the $j$-th column is $1$ when the nodes $i$ and $j$ are connected by an edge, otherwise, it is $0$.

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

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

The example graph with integer node names.

$\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]$ is $1$, because there is an edge from node $0$ to node $1$ in our graph. On the other hand, the entry $A[3, 2]$ is $0$, because there is no edge from node $3$ to node $2$ 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] \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.

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

#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 $n*n$ entries, where $A[i, j]$ is stored at index $n*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.

#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.