The adjacency matrix

Lesson · 7 min read · Graphs · Storing a graph

An n × n table with a 1 wherever an edge exists: constant-time edge checks, at the price of n² memory.

Structure

A graph has to live in memory as something an algorithm can query. The most direct choice is an adjacency matrix: an n × n table in which entry [i][j] is 1 if there is an edge from node i to node j, and 0 if not. Nodes are numbered 0 to n − 1 so that they can index the table.

stored as→

An undirected graph and its matrix. Row i lists the neighbours of i; the matrix is symmetric.

For an undirected graph every edge appears twice, at [i][j] and at [j][i], so the matrix is symmetric about its diagonal. The diagonal itself is 0 unless a node has an edge to itself.

Directed and weighted graphs

For a directed graph, [i][j] records only the edge i → j, so the matrix is no longer symmetric. Row i lists the edges leaving i; column j lists the edges arriving at j. Reading a column gives in-degrees, reading a row gives out-degrees.

Step 1 / 2

stored as→
Row 2 (edges leaving 2) and column 1 (edges arriving at 1).
Step 2 / 2

stored as→
A weight matrix: ∞ where there is no edge, 0 on the diagonal. This is the input to Floyd–Warshall.

For a weighted graph the entry holds the weight. "No edge" then needs a value that cannot be a weight: infinity is the usual choice for shortest-path work, because it makes "no edge" behave as an impossibly long one in every comparison. The diagonal is 0: getting from a node to itself costs nothing.

Implementation

Building the matrix from a list of edges is two lines; the only decision is whether to fill both halves.

def build_matrix(n, edges, directed=False):
    m = [[0] * n for _ in range(n)]      # not [[0] * n] * n: that repeats one row n times
    for u, v in edges:
        m[u][v] = 1
        if not directed:
            m[v][u] = 1
    return m

def has_edge(m, u, v):
    return m[u][v] == 1                  # O(1)

def neighbours(m, u):
    return [v for v in range(len(m)) if m[u][v] == 1]   # O(n), however few there are

using Matrix = std::vector<std::vector<int>>;

Matrix build_matrix(int n, const std::vector<std::pair<int, int>>& edges, bool directed = false) {
    Matrix m(n, std::vector<int>(n, 0));
    for (auto [u, v] : edges) {
        m[u][v] = 1;
        if (!directed) m[v][u] = 1;
    }
    return m;
}

bool has_edge(const Matrix& m, int u, int v) {
    return m[u][v] == 1;                 // O(1)
}

std::vector<int> neighbours(const Matrix& m, int u) {   // O(n), however few there are
    std::vector<int> out;
    for (int v = 0; v < (int)m.size(); ++v)
        if (m[u][v] == 1) out.push_back(v);
    return out;
}

static int[][] buildMatrix(int n, int[][] edges, boolean directed) {
    int[][] m = new int[n][n];
    for (int[] e : edges) {
        m[e[0]][e[1]] = 1;
        if (!directed) m[e[1]][e[0]] = 1;
    }
    return m;
}

static boolean hasEdge(int[][] m, int u, int v) {
    return m[u][v] == 1;                 // O(1)
}

static List<Integer> neighbours(int[][] m, int u) {    // O(n), however few there are
    List<Integer> out = new ArrayList<>();
    for (int v = 0; v < m.length; v++)
        if (m[u][v] == 1) out.add(v);
    return out;
}

function buildMatrix(n, edges, directed = false) {
    // not new Array(n).fill(new Array(n)): that shares one row n times
    const m = Array.from({ length: n }, () => new Array(n).fill(0));
    for (const [u, v] of edges) {
        m[u][v] = 1;
        if (!directed) m[v][u] = 1;
    }
    return m;
}

const hasEdge = (m, u, v) => m[u][v] === 1;                       // O(1)
const neighbours = (m, u) => m[u].flatMap((x, v) => (x === 1 ? [v] : []));   // O(n), however few there are

fn build_matrix(n: usize, edges: &[(usize, usize)], directed: bool) -> Vec<Vec<u8>> {
    let mut m = vec![vec![0u8; n]; n];
    for &(u, v) in edges {
        m[u][v] = 1;
        if !directed { m[v][u] = 1; }
    }
    m
}

fn has_edge(m: &[Vec<u8>], u: usize, v: usize) -> bool {
    m[u][v] == 1                         // O(1)
}

fn neighbours(m: &[Vec<u8>], u: usize) -> Vec<usize> {  // O(n), however few there are
    (0..m.len()).filter(|&v| m[u][v] == 1).collect()
}

buildMatrix :: Int -> [(Int, Int)] -> Bool -> Array (Int, Int) Int
buildMatrix n edges directed =
  accumArray (\_ x -> x) 0 ((0, 0), (n - 1, n - 1))
    [ (e, 1) | (u, v) <- edges, e <- (u, v) : [ (v, u) | not directed ] ]

hasEdge :: Array (Int, Int) Int -> Int -> Int -> Bool
hasEdge m u v = m ! (u, v) == 1          -- O(1)

neighbours :: Array (Int, Int) Int -> Int -> [Int]
neighbours m u = [ v | v <- [0 .. n], m ! (u, v) == 1 ]   -- O(n), however few there are
  where (_, (_, n)) = bounds m

In Python, [[0] * n] * n creates n references to the same row, so setting one entry sets a whole column. Build each row separately.

What it costs

The matrix answers "is there an edge between u and v?" in one memory read, which no other representation matches. Everything else is paid for with n²: the memory is n² whatever the number of edges, and listing a node's neighbours means reading its whole row.

Operation	Cost	Note
Is there an edge u → v?	O(1)	one lookup
List the neighbours of u	O(n)	read the whole row
Add or remove an edge	O(1)	set one entry (two if undirected)
Add a node	O(n²)	the table must be rebuilt one size larger
Visit every edge (a traversal)	O(n²)	every entry is read
Memory	O(n²)	10⁴ nodes is 10⁸ entries

TimeO(n²) to build or traverse

SpaceO(n²)

Use a matrix when the graph is dense (m close to n²), when n is small (a few hundred), or when the algorithm itself works on the matrix: Floyd–Warshall and some dynamic programming over subsets of nodes do. Otherwise use an adjacency list.