Adjacency matrix

An adjacency matrix stores a graph with $n$ vertices as an n \times n table, where the cell in row $u$ and column $v$ says whether there is an edge between $u$ and $v$. Checking whether two vertices are joined reads one cell.

The usual way to store a graph is an adjacency list. Take the matrix when $n$ is at most a few thousand and the program asks about pairs of vertices ("are $u$ and $v$ joined?", "is every pair joined?"), when the input already is a matrix, or for Floyd–Warshall. The matrix has n^2 cells however few edges there are.

How it works

Here is a graph with 6 vertices and 8 edges beside its matrix.

Fig. 1. Row 4 has 1s in columns 2, 5 and 6, the neighbours of vertex 4. Cell (2, 5) is 0, so 2 and 5 are not joined. The vertices are numbered from 1, so row 0 and column 0 are not used.

The number of 1s in row $v$ is the degree of $v$, so vertex 4 has degree 3. Cell (4, 5) and cell (5, 4) are both 1. In general cell $(u,v)$ equals cell $(v,u)$, so the matrix is symmetric. The diagonal from the top left corner is all 0, since no vertex is joined to itself.

The program first creates the matrix with every cell 0, then reads the edges one line at a time and adds each one to the matrix.

The matrix starts with every cell 0.

The line 1 2 sets cell (1, 2) and cell (2, 1) to 1.

The line 1 3 sets cell (1, 3) and cell (3, 1) to 1.

The line 2 3 sets cell (2, 3) and cell (3, 2) to 1.

The line 2 4 sets cell (2, 4) and cell (4, 2) to 1.

The line 3 5 sets cell (3, 5) and cell (5, 3) to 1.

The line 4 5 sets cell (4, 5) and cell (5, 4) to 1.

The line 4 6 sets cell (4, 6) and cell (6, 4) to 1.

The line 5 6 sets cell (5, 6) and cell (6, 5) to 1.

1/9

Fig. 2. Each line read sets two cells (blue).

After the eight lines the matrix is the one in Fig. 1: every edge has set two cells, 16 cells in all.

To go over the neighbours of $v$, the program reads all $n$ cells of row $v$ and takes the columns that hold 1. Vertex 1 has 2 neighbours, but finding them still takes 6 cells. To remove an edge, set its two cells back to 0.

With $n$ vertices and $m$ edges, the costs in big-O notation are:

Memory is the limit: for n = 1000 the matrix has 10^6 cells, 4 MB as int (4 bytes per cell). For n = 5000 it has 2.5 \cdot 10^7 cells: 100 MB as int, or 25 MB as char (1 byte per cell, vector<vector<char>>; the 0/1 code works unchanged). A typical memory limit is 128–256 MB, so a few thousand vertices fit. For n = 10^5 the matrix has 10^{10} cells, 40 GB as int, and doesn't fit.

In C++

The vertices are numbered from 1 to n, and the matrix is a vector of vectors with n + 1 rows of n + 1 zeros:

vector<vector<int>> a(n + 1, vector<int>(n + 1, 0));

Then a[u][v] is the cell in row u and column v, and row 0 and column 0 stay unused.

The program reads n, m and m lines u v, then q questions, each a line u v. For each question it prints YES if u and v are joined, and NO otherwise. The graph is undirected; the marked line is the one to remove for a directed graph. For the example with three questions the input is:

6 8
1 2
1 3
2 3
2 4
3 5
4 5
4 6
5 6
3
2 5
5 4
1 6

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // create the matrix
    vector<vector<int>> a(n + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        // add the edge: two cells
        a[u][v] = 1;
        a[v][u] = 1;   // remove this line if the graph is directed
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        // check the edge: one cell
        if (a[u][v]) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

To go over row v, loop over the columns: for (int u = 1; u <= n; u++) if (a[v][u]) takes each neighbour u of v.

Many problems give the graph as a matrix right away: n, then n rows of n numbers. Two nested loops read it:

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }

Since the matrix is symmetric, the cells right of the diagonal, with i < j, hold each edge once. For example, this input is a graph with 5 vertices:

5
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0

Directed graphs

In a directed graph, the line u v is an edge from u to v, so it sets one cell, a[u][v]: remove the marked line a[v][u] = 1; from the program. Now row v holds the edges that leave v, column v holds the edges that enter v, and the matrix is no longer symmetric.

Fig. 3. Row 4 holds the edges out of 4, to 5 and 6. Column 4 holds the edges into 4: only the one from 2.

Vertex 1 has no edge entering it, so column 1 is all 0. Vertex 6 has no edge leaving it, so row 6 is all 0.

Weighted edges

When each edge has a weight, a line of the input is u v w, and the cell holds the weight. For the example the input is:

6 8
1 2 4
1 3 1
2 3 2
2 4 5
3 5 8
4 5 3
4 6 6
5 6 2

An empty cell can't hold 0, because an edge of weight 0 would look the same. It holds a large number INF, written $\infty$ in the text, that no real weight reaches. Shortest-path algorithms such as Floyd–Warshall also put 0 on the diagonal, since the route from a vertex to itself has length 0. If the program only asks about edges, leave the diagonal at INF. The version for shortest paths creates the matrix like this:

    const int INF = 1e9;

    // create the matrix
    vector<vector<int>> a(n + 1, vector<int>(n + 1, INF));
    for (int v = 1; v <= n; v++) {
        a[v][v] = 0;
    }

A pair can appear in several lines. When the problem is about the shortest way between vertices, only the lightest of those edges matters, so the cell keeps the minimum. The body of the reading loop becomes (min needs <algorithm>):

        int u, v, w;
        cin >> u >> v >> w;
        // add the edge: two cells, keep the smallest weight if the pair repeats
        a[u][v] = min(a[u][v], w);
        a[v][u] = min(a[v][u], w);

Here is the whole weighted matrix; look at cell (1, 2).

Fig. 4. Cell (1, 2) holds the edge of weight 4, not the shortest distance 3 along the blue route through 3.

Examples of use

Floyd–Warshall starts from the weighted matrix built above and turns it into the table of shortest distances between all pairs in O(n^3).

A dense graph, with close to n^2 edges, often comes as a matrix. Dijkstra's algorithm and Prim's algorithm both have an O(n^2) version for this case.

Questions about pairs and triples of vertices use the one-cell check: is every pair joined, is the graph transitive (whenever $u$–$v$ and $v$–$w$ are edges, so is $u$–$w$), how many triangles (three vertices all joined to each other) it has. Three nested loops with an $O(1)$ check each make 10^6 steps for n = 100.

Breadth-first search and depth-first search work on a matrix by scanning row $v$ instead of the list of $v$. Each vertex costs $n$ steps, so the search takes O(n^2).

Common mistakes

• Creating a(n, vector<int>(n)) while the vertices are numbered from 1, so an edge to vertex n writes past the end of the matrix. Create n + 1 rows of n + 1 cells.

• Writing a[u][v] = w when a pair of vertices appears in several lines, so the last weight stays instead of the smallest. Take min.

Similar structures

An adjacency list keeps for each vertex only its neighbours, so its memory grows with the edges. On the example, row 4 of the matrix has 6 cells, and the list of 4 holds 3 numbers.

An edge list keeps the edges as read, for Bellman–Ford and Kruskal's algorithm.

Practice