adjacency matrix

An adjacency matrix is a data structure for storing graphs in memory. If the graph has $N$ nodes, then it can be represented by an $N\times N$ boolean matrix, with each element $M_{i,j}$ representing whether there exists an edge between node i and node j.

This is preferred when there are many edges but not many nodes. Otherwise, consider using adjacency list.

#include <vector>
#include <algorithm> // std::fill
 
constexpr int N = 100; // number of nodes
// vector<bool> stores one bit for each boolean
using std::vector;
 
// adjacency matrix of N x N
vector<vector<bool>> adj(N, vector<bool>(N));
 
void connect(int i, int j) {
    adj[i][j] = true;
    // uncomment if graph is not directed
    // adj[j][i] = true;
}
 
void disconnect(int i, int j) {
    adj[i][j] = false;
    // uncomment if graph is not directed
    // adj[j][i] = false;
}