Adjacency List vs Adjacency Matrix: Choosing a Graph Representation

Before any graph algorithm runs, the graph has to be written down, and the choice decides the cost of everything that follows. Most interview graph problems arrive as a list of edges, and the first line of a good solution turns that list into an adjacency list. Knowing why, and when an adjacency matrix is the better choice, is a quick way to show you understand graphs rather than a memorised breadth-first search.

The problem it solves

A graph is a set of nodes and a set of edges between them. Algorithms mostly ask two questions about it:

• Is there an edge from A to B? Needed for checks such as "are these two users connected?"
• What are all the neighbours of A? Needed by every traversal: breadth-first search, depth-first search, Dijkstra, topological sort.

An edge list, the raw pairs, answers both by scanning every edge, which is O(E) per question. The two standard representations each make one of the questions cheap.

The intuition

An adjacency list keeps, for each node, the list of nodes it points to. It stores only the edges that exist: V entries for the nodes plus E entries for the edges, O(V + E) in total. Listing a node's neighbours means reading its list, which costs exactly its degree. Checking one specific edge means scanning that list, also O(degree); storing a set per node instead of a list brings that down to O(1) on average.

An adjacency matrix is a V × V grid where cell [a][b] is 1 when the edge exists. Checking an edge is one cell read, O(1). But the grid reserves a cell for every ordered pair, whether or not the edge exists, so it costs O(V²) memory, and listing a node's neighbours means scanning its whole row, O(V), even when the node has only one neighbour.

The deciding number is the density: how many of the V² possible edges exist. Real graphs such as road maps, social networks and dependency graphs are sparse: each node touches a handful of others, so E is far below V². For them the list wins on memory and on traversal. The matrix earns its place when the graph is dense, when V is small, or when the algorithm reads arbitrary pairs, as Floyd-Warshall does. The Big-O cheat sheet has both rows side by side.

Undirected graphs store every edge twice, once in each direction. Weighted graphs store the weight instead of a 1, or a (neighbour, weight) pair in the list.

Watch it run

The animation starts from one graph and two ways to write it down: four positions, four directed passes. Pass 1 is GK to DF: the list appends DF to GK's row and the matrix sets mat[GK][DF] = 1. Pass 2 is DF to MF, pass 3 MF to FW, and pass 4 MF to DF, each recorded in both structures at once. Both now hold the same four facts; the difference is what they store for the passes that never happened. The matrix reserves a cell for every ordered pair, 16 cells for 4 passes, and twelve of them are zero. "Did MF pass to DF?" is one lookup in the matrix: read mat[2][1], no scanning at all. The list stores only the passes that exist, so MF keeps [FW, DF] and nothing else. Listing a node's neighbours is instant on the list, but on the matrix it means scanning a whole row of mostly zeros. The last frame scales it up: eleven players is fine either way, but a whole league is O(n²) cells of almost entirely zero, so scarce edges pick the list.

The code

One builder for both representations, run on the animation's four passes:

from collections import deque

def build(nodes, edges, directed=True):
    adj = {v: [] for v in nodes}                       # adjacency list
    idx = {v: i for i, v in enumerate(nodes)}
    mat = [[0] * len(nodes) for _ in nodes]            # adjacency matrix
    for a, b in edges:
        adj[a].append(b)
        mat[idx[a]][idx[b]] = 1
        if not directed:
            adj[b].append(a)
            mat[idx[b]][idx[a]] = 1
    return adj, mat, idx

players = ["GK", "DF", "MF", "FW"]
passes = [("GK", "DF"), ("DF", "MF"), ("MF", "FW"), ("MF", "DF")]
adj, mat, idx = build(players, passes)
print(adj)          # {'GK': ['DF'], 'DF': ['MF'], 'MF': ['FW', 'DF'], 'FW': []}
print(mat)          # [[0, 1, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1], [0, 0, 0, 0]]
print(sum(map(len, adj.values())), len(players) ** 2)   # 4 16

The two questions, answered by each structure. The matrix reads one cell for an edge check but a whole row for the neighbours:

def has_edge_list(adj, a, b):
    return b in adj[a]                                 # O(degree of a)

def has_edge_matrix(mat, idx, a, b):
    return mat[idx[a]][idx[b]] == 1                    # O(1): one cell

def neighbours_matrix(mat, nodes, idx, a):
    return [nodes[c] for c, bit in enumerate(mat[idx[a]]) if bit]   # O(V): whole row

print(has_edge_list(adj, "MF", "DF"), has_edge_matrix(mat, idx, "MF", "DF"))   # True True
print(has_edge_list(adj, "DF", "GK"), has_edge_matrix(mat, idx, "DF", "GK"))   # False False
print(neighbours_matrix(mat, players, idx, "MF"))      # ['DF', 'FW']

What that means for a traversal. Breadth-first search on a ring of 300 nodes touches 300 list entries, one per edge, but 90,000 matrix cells, because every dequeued node scans a full row:

def bfs_list(adj, start):
    dist, q, touched = {start: 0}, deque([start]), 0
    while q:
        u = q.popleft()
        for v in adj[u]:                               # only real edges
            touched += 1
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist, touched

def bfs_matrix(mat, nodes, idx, start):
    dist, q, touched = {start: 0}, deque([start]), 0
    while q:
        u = q.popleft()
        for c, bit in enumerate(mat[idx[u]]):          # every cell of the row
            touched += 1
            if bit and nodes[c] not in dist:
                dist[nodes[c]] = dist[u] + 1
                q.append(nodes[c])
    return dist, touched

ring = list(range(300))
ring_edges = [(i, (i + 1) % 300) for i in ring]        # 300 nodes, 300 edges
a2, m2, i2 = build(ring, ring_edges)
print(bfs_list(a2, 0)[1], bfs_matrix(m2, ring, i2, 0)[1])   # 300 90000

Both representations checked against the raw edge set on 500 seeded random graphs, directed and undirected, with self-loops and repeated edges: every pair, every neighbour list and every BFS distance agree:

import random

random.seed(23)
ok = True
for _ in range(500):
    n = random.randint(1, 12)
    nodes = list(range(n))
    edges = list({(random.randrange(n), random.randrange(n)) for _ in range(random.randint(0, 30))})
    directed = random.random() < 0.5
    adj, mat, idx = build(nodes, edges, directed)
    pairs = set(edges) | ({(b, a) for a, b in edges} if not directed else set())
    for a in nodes:
        for b in nodes:
            ok &= has_edge_list(adj, a, b) == has_edge_matrix(mat, idx, a, b) == ((a, b) in pairs)
        ok &= sorted(set(adj[a])) == neighbours_matrix(mat, nodes, idx, a)
    s = random.randrange(n)
    ok &= bfs_list(adj, s)[0] == bfs_matrix(mat, nodes, idx, s)[0]
print(ok)           # True

The complexity

With V nodes and E edges:

• Memory: list O(V + E); matrix O(V²).
• Edge check: list O(degree), or O(1) on average with a set per node; matrix O(1).
• All neighbours of one node: list O(degree); matrix O(V).
• Full BFS or DFS: list O(V + E); matrix O(V²).
• Add an edge: O(1) for both. Adding a node to a matrix means growing every row.

Where it goes wrong

• Building a matrix for a large sparse graph. A hundred thousand nodes means ten billion cells, far past any interview memory limit.
• Forgetting the reverse edge. An undirected edge must go into both lists, or traversals miss half the graph.
• Dropping isolated nodes. Building the list only from the edges leaves out nodes with no edges; initialise every node first.
• Assuming labels are 0 to V - 1. A matrix needs an index map, as idx does here, when nodes are names.
• Scanning a list for repeated edge checks. If the algorithm asks "is there an edge?" many times, store a set per node.

When it shows up in interviews

It shows up at the start of almost every graph problem, when the input is an edge list and the first step is to build the adjacency list, as in number of connected components, topological sort and BFS. It also comes up directly: "how would you store this graph, and what does each operation cost?" The matrix appears in dense-graph questions and in grid problems, where the grid itself is an implicit graph and neighbours are computed rather than stored.

How to say it in an interview

"The graph is sparse, so I build an adjacency list: a dictionary from each node to its neighbours, O(V + E) memory. That makes a traversal O(V + E), because each node's neighbours cost exactly its degree. An adjacency matrix gives an O(1) edge check, but it costs O(V²) memory and turns every neighbour scan into a full row, so BFS becomes O(V²). I would switch to a matrix only for a small or dense graph, or an algorithm like Floyd-Warshall that reads arbitrary pairs; and if I needed fast edge checks on a sparse graph, I would keep a set per node instead."