9.3 Adjacency Matrices

Problem

You need a graph representation that can answer edge-existence queries quickly.

An adjacency list is efficient for traversal, but checking whether an edge exists can require scanning a neighbor list. If your algorithm repeatedly asks questions such as:

Is there an edge from u to v?

then an adjacency matrix may be a better representation.

Solution

Represent the graph as a two-dimensional table.

For a graph with n vertices, create an n × n matrix. The entry at matrix[u][v] records whether the edge u -> v exists.

For an unweighted directed graph:

def build_matrix(n, edges):
    matrix = [[False] * n for _ in range(n)]

    for u, v in edges:
        matrix[u][v] = True

    return matrix

Example:

edges = [
    (0, 1),
    (0, 2),
    (1, 3),
]

matrix = build_matrix(4, edges)

Result:

[
  [False, True,  True,  False],
  [False, False, False, True ],
  [False, False, False, False],
  [False, False, False, False],
]

Now edge lookup is constant time:

if matrix[0][2]:
    print("0 can reach 2 directly")

Discussion

An adjacency matrix trades memory for lookup speed.

With an adjacency list, testing whether u -> v exists takes time proportional to the degree of u, unless the neighbor collection is a set. With an adjacency matrix, the same test is a direct table lookup.

This is useful when the graph is dense, when edge lookup is the dominant operation, or when the algorithm naturally operates over all vertex pairs.

Common examples include:

Use case	Why a matrix helps
Dense graphs	Most possible edges exist
Transitive closure	Algorithms inspect vertex pairs
Floyd-Warshall	Dynamic programming over all pairs
Graph complements	Need to test missing edges quickly
Small graphs	Simplicity matters more than memory
Bitset optimization	Rows can be compressed into machine words

The cost is space. For n vertices, the matrix always uses O(n²) memory, regardless of how many edges exist.

A graph with one million vertices would require one trillion entries. Even if each entry used only one bit, that is still large. With ordinary boolean objects or integers, it becomes impractical.

Use an adjacency matrix deliberately. It is excellent for the right workload and wasteful for the wrong one.

Directed Graphs

For a directed graph, store only the directed relation.

def add_directed_edge(matrix, u, v):
    matrix[u][v] = True

The entry matrix[u][v] is independent of matrix[v][u].

Example:

matrix[0][1] = True
matrix[1][0] = False

This means 0 -> 1 exists, but 1 -> 0 does not.

Directed matrices are commonly used for dependency graphs, reachability relations, finite automata, and transition systems.

Undirected Graphs

For an undirected graph, the matrix must be symmetric.

def add_undirected_edge(matrix, u, v):
    matrix[u][v] = True
    matrix[v][u] = True

For every edge u -- v, both entries must be set.

A missing symmetric update is a frequent bug. It creates a graph that behaves directed even though the problem says undirected.

You can test the invariant directly:

def is_symmetric(matrix):
    n = len(matrix)

    for i in range(n):
        for j in range(n):
            if matrix[i][j] != matrix[j][i]:
                return False

    return True

This check costs O(n²), so it is usually used in tests, not in hot code.

Weighted Graphs

For weighted graphs, store a weight instead of a boolean.

Use a sentinel value to represent a missing edge.

For shortest-path algorithms, a common sentinel is infinity:

def build_weight_matrix(n, edges):
    inf = float("inf")
    matrix = [[inf] * n for _ in range(n)]

    for i in range(n):
        matrix[i][i] = 0

    for u, v, weight in edges:
        matrix[u][v] = weight

    return matrix

Example:

edges = [
    (0, 1, 5),
    (0, 2, 2),
    (1, 3, 7),
]

matrix = build_weight_matrix(4, edges)

Here:

matrix[0][1] == 5
matrix[0][3] == float("inf")
matrix[0][0] == 0

The diagonal is set to zero because the distance from a vertex to itself is usually zero.

This convention works well for Floyd-Warshall and other all-pairs shortest-path algorithms.

Recipe: Edge Existence Matrix

Use this version when edges are unweighted and vertex IDs are integers from 0 to n - 1.

class GraphMatrix:
    def __init__(self, n, directed=True):
        self.n = n
        self.directed = directed
        self.matrix = [[False] * n for _ in range(n)]

    def add_edge(self, u, v):
        self.matrix[u][v] = True

        if not self.directed:
            self.matrix[v][u] = True

    def has_edge(self, u, v):
        return self.matrix[u][v]

    def neighbors(self, u):
        for v, exists in enumerate(self.matrix[u]):
            if exists:
                yield v

Example:

g = GraphMatrix(4, directed=False)
g.add_edge(0, 1)
g.add_edge(0, 2)

print(g.has_edge(1, 0))
print(list(g.neighbors(0)))

Output:

True
[1, 2]

This class gives constant-time edge checks, but neighbors(u) scans the whole row. That scan costs O(V), even if u has only a few neighbors.

This is the central trade-off.

Recipe: Weighted Matrix

Use this version when edge weights matter.

class WeightedGraphMatrix:
    def __init__(self, n, directed=True):
        self.n = n
        self.directed = directed
        self.inf = float("inf")
        self.matrix = [[self.inf] * n for _ in range(n)]

        for i in range(n):
            self.matrix[i][i] = 0

    def add_edge(self, u, v, weight):
        self.matrix[u][v] = weight

        if not self.directed:
            self.matrix[v][u] = weight

    def weight(self, u, v):
        return self.matrix[u][v]

    def has_edge(self, u, v):
        return self.matrix[u][v] != self.inf

Example:

g = WeightedGraphMatrix(3, directed=True)
g.add_edge(0, 1, 8)
g.add_edge(1, 2, 4)

print(g.weight(0, 1))
print(g.weight(0, 2))

Output:

8
inf

Be careful with zero-weight edges. Do not use 0 as the sentinel for a missing edge if zero is a valid edge weight.

Complexity Characteristics

For V vertices, an adjacency matrix has predictable costs.

Operation	Complexity
Memory usage	O(V²)
Add edge	O(1)
Remove edge	O(1)
Check edge existence	O(1)
Enumerate neighbors	O(V)
Traverse graph	O(V²)

The traversal cost differs from adjacency lists. With adjacency lists, traversal is O(V + E). With an adjacency matrix, traversal is typically O(V²) because each row scan checks every possible neighbor.

This matters for sparse graphs. If E is much smaller than V², adjacency lists are usually better.

Matrix vs List

Use this comparison as a quick rule.

Requirement	Prefer
Sparse graph	Adjacency list
Dense graph	Adjacency matrix
Fast edge lookup	Adjacency matrix
Fast neighbor iteration	Adjacency list
All-pairs algorithms	Adjacency matrix
Memory efficiency	Adjacency list
Simple small graph	Either
Bitset acceleration	Adjacency matrix

The choice is not permanent. Some algorithms convert between representations. For example, a graph may be loaded as an edge list, converted to an adjacency list for traversal, and converted to a matrix for all-pairs dynamic programming.

Common Pitfalls

Do not use an adjacency matrix for a huge sparse graph. It can fail before the algorithm begins because memory allocation alone is too large.

Do not forget the symmetric entry for undirected graphs.

Do not use a sentinel value that conflicts with valid weights.

Do not assume neighbor iteration is cheap. It scans an entire row.

Do not forget to initialize the diagonal for shortest-path matrices.

Do not mix external vertex labels with matrix indexes without a mapping layer. If vertices are strings, map them to integer IDs first.

labels = ["A", "B", "C"]
index = {label: i for i, label in enumerate(labels)}

Then store edges using indexes:

u = index["A"]
v = index["B"]
matrix[u][v] = True

Takeaway

An adjacency matrix is the right representation when constant-time edge lookup or all-pairs computation matters more than memory usage. It gives simple indexing and predictable operations, but it pays O(V²) space and often O(V²) traversal time. For dense graphs, small graphs, and matrix-oriented algorithms, that trade-off is acceptable. For large sparse graphs, use an adjacency list instead.