Adjacency Matrix

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

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

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.

Its adjacency matrix is

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

Implementing the adjacency matrix

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;
    
}

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Adjacency Matrix

Representing the vertices

Adjacency matrix

Implementing the adjacency matrix