Adjacency Matrix Explained: When O(1) Edge Lookup Matters

You have a graph. Six cities, some roads between them. Now you need to answer one question a thousand times per second: is there a direct road between city A and city B?

If you're storing this graph as an adjacency list, you scan through A's neighbor list every time. That's O(degree) per query. For a dense graph, that cost accumulates fast. An adjacency matrix answers the same question in O(1), always. One array lookup, done.

No scanning. No iterating. Just matrix[a][b] and you're home.

The Adjacency Matrix Is a Grid. One Cell Per Possible Edge.

An adjacency matrix is a V×V two-dimensional array where matrix[i][j] tells you whether an edge exists from vertex i to vertex j.

For an unweighted graph, values are 0 or 1. A 1 means the edge is there. A 0 means it isn't and you can stop worrying about it.

Take a simple undirected graph with four vertices (0, 1, 2, 3) and edges: 0-1, 0-2, 1-3, 2-3.

    0  1  2  3
0 [ 0, 1, 1, 0 ]
1 [ 1, 0, 0, 1 ]
2 [ 1, 0, 0, 1 ]
3 [ 0, 1, 1, 0 ]

Graph mapped to its adjacency matrix: edges become lit cells, non-edges stay dark

Row 0, column 1 is 1: edge from vertex 0 to vertex 1. Row 0, column 3 is 0: no edge. To check any edge, you read one cell. That's it.

Notice the symmetry. Because the graph is undirected, matrix[i][j] always equals matrix[j][i]. Every edge appears twice, which means you're storing the same fact in two places, which means the matrix is either "charmingly redundant" or "wasteful," depending on how you feel about O(V²) space. Spoiler: you're about to have feelings about it.

Building One Takes About Ten Seconds

Allocate a V×V grid of zeros, then set the cells for every edge you have.

def build_adjacency_matrix(
    num_vertices: int,
    edges: list[tuple[int, int]]
) -> list[list[int]]:
    matrix = [[0] * num_vertices for _ in range(num_vertices)]
    for u, v in edges:
        matrix[u][v] = 1
        matrix[v][u] = 1  # remove for directed graphs
    return matrix

function buildAdjacencyMatrix(
    numVertices: number,
    edges: [number, number][]
): number[][] {
    const matrix = Array.from(
        { length: numVertices },
        () => new Array(numVertices).fill(0)
    );
    for (const [u, v] of edges) {
        matrix[u][v] = 1;
        matrix[v][u] = 1; // remove for directed graphs
    }
    return matrix;
}

Edge lookup is matrix[u][v]. Finding all neighbors of vertex u means scanning row u and collecting every index j where the value is 1. That second part is O(V), which will come back to haunt you.

Direction and Weight Both Fit in the Same Grid

For a directed graph, set only matrix[u][v] = 1, not the reverse. The matrix is no longer symmetric. A 1 at row u, column v means the edge goes from u to v. The reverse cell is independent.

For a weighted graph, store the weight instead of 1. Use float('inf') or Infinity to represent "no edge" when 0 is a valid weight.

# Weighted directed graph
matrix[u][v] = weight
# "No edge" is float('inf') when weights can be zero

This is exactly how Floyd-Warshall initializes its distance table: diagonal set to 0, known edges get their weight, everything else starts at infinity. The algorithm then runs in-place on that matrix for three nested loops over every vertex pair. For all-pairs shortest paths on a dense graph, the adjacency matrix isn't just convenient, it's the natural starting point.

O(V²) Space. Whether You Like It or Not.

Here's the part that makes interviewers nod knowingly. An adjacency matrix costs O(V²) space regardless of how many edges actually exist.

A graph with 1,000 vertices requires a million-cell grid even if only 999 edges are present. 999 cells have a 1 in them. The other 999,001 sit there, uselessly zero, judging you.

For sparse graphs, most of those cells stay empty forever. You've allocated a stadium to store a bicycle.

Here's the full operation profile:

Operation	Time
Check if edge (u, v) exists	O(1)
Add or remove an edge	O(1)
Find all neighbors of vertex u	O(V)
Iterate all edges in the graph	O(V²)
Space	O(V²)

The O(1) edge check is the reason to use this structure. If your algorithm asks "does this edge exist?" thousands of times, the matrix pays for itself. If your algorithm mostly iterates neighbors, an adjacency list is faster because it only touches edges that are actually there.

Dense vs. Sparse: The One Question That Decides

Use an adjacency matrix when the graph is dense (E approaches V²) or when O(1) edge existence checks are the bottleneck.

Dense means most possible edges are present. A tiny network where nearly every node connects to every other one. A routing table for a small cluster. A round-robin tournament bracket. In dense graphs, E is O(V²), so the O(V²) space cost is proportionate to what you'd store in a list anyway. The waste disappears. And O(1) lookups beat scanning.

Sparse means few edges relative to vertices. A city map. A dependency graph. A social network where most people have not friended every other person on the platform. Most graphs in interview problems are deliberately sparse, with only a few edges per node. Adjacency lists win there on both space and traversal speed.

Rough rule: if E is close to V², reach for the matrix. If E is O(V) or O(V log V), use a list. The post Adjacency List vs Adjacency Matrix covers the trade-off in full detail.

BFS Still Works. But You're Scanning the Zeros.

BFS and DFS work fine on adjacency matrices. The only change is how you find neighbors: instead of iterating a stored list, you scan the full row and check each cell.

from collections import deque

def bfs(matrix: list[list[int]], start: int) -> list[int]:
    num_vertices = len(matrix)
    visited = [False] * num_vertices
    queue = deque([start])
    visited[start] = True
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in range(num_vertices):
            if matrix[node][neighbor] == 1 and not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

    return order

The inner loop scans all V vertices every time, making BFS O(V²) total on a matrix. The adjacency list version is O(V + E). For a sparse graph with 1,000 nodes and 1,200 edges, you're doing about a million iterations instead of 2,200. On a sparse graph, running BFS on a matrix is the algorithmic equivalent of reading every page of a dictionary to find one word.

For dense graphs where E is already O(V²), they're equivalent and the extra work evaporates. The matrix doesn't hurt you there.

Two Problems Where the Matrix Is the Right Call

Floyd-Warshall. The whole algorithm is three nested loops over a V×V DP table that starts as a weighted adjacency matrix. If an interview asks for all-pairs shortest paths on a small or dense graph, the matrix is the natural starting point. See the full walkthrough in Floyd-Warshall Algorithm.

Small, fully-connected graphs. When a problem gives you 5 to 10 nodes with complex relationships, a matrix is often cleaner to write than a list. Tournament brackets, round-robin competitions, small flow networks. For V = 10, the O(V²) cost is 100 cells. That's nothing. The simplicity of matrix[u][v] beats the overhead of managing adjacency lists.

One pattern worth knowing: each row can be stored as a bitmask where bit j is set if an edge to j exists. Edge checks become bitwise AND. Mostly a competitive programming trick, but if an interview involves sets of nodes rather than individual pairs, it's worth a mention.

What You'll Write in Practice

For most interview graph problems, you'll default to an adjacency list. Most interview graphs are sparse by design, and list-based traversal is faster and less code to write under pressure.

Reach for the matrix when the problem has dense connectivity, requires repeated O(1) edge checks, or has a small enough V that the V² space cost is irrelevant. "I'll use an adjacency matrix here because the graph is fully connected and I need constant-time edge lookups" is exactly the kind of trade-off reasoning that earns credit on the rubric.

That reasoning only comes naturally when you've practiced explaining choices out loud. SpaceComplexity runs voice-based mock interviews where you have to justify your representation choice in real time, not just pick the right data structure in silence.

For the traversal algorithms that run on either structure, see Breadth-First Search and Depth-First Search.