Graph Representations: Adjacency List vs. Matrix and Why It Actually Matters

Before you can run BFS, Dijkstra, or any graph algorithm, you have to answer a boring but critical question: how do you actually store the graph in memory?

The answer matters more than most people think. The wrong representation can turn an O(V + E) algorithm into O(V^2), blow up your memory by orders of magnitude, or make a simple operation require scanning the entire data structure. And in interviews, choosing the right representation signals that you actually understand graphs, not just the algorithms that run on them.

There are three main representations. Let's go through each one honestly.

Adjacency Matrix

A 2D array where matrix[i][j] indicates whether there's an edge from node i to node j (and optionally, its weight).

# unweighted graph with 5 nodes
n = 5
adj_matrix = [[0] * n for _ in range(n)]

# add edge from 0 to 1
adj_matrix[0][1] = 1
adj_matrix[1][0] = 1  # for undirected graph

# add weighted edge from 2 to 3 with weight 5
adj_matrix[2][3] = 5
adj_matrix[3][2] = 5

Check if edge exists between u and v: adj_matrix[u][v] — O(1). Instant. Get all neighbors of node u: Scan the entire row. O(V). Space: O(V^2). Always. Regardless of how many edges exist. Add an edge: O(1). Remove an edge: O(1).

When to Use Adjacency Matrix

The matrix shines in specific situations:

Dense graphs. If the graph has close to V^2 edges (like a complete graph or near-complete graph), the matrix doesn't waste much space since most entries are non-zero. And O(V) neighbor scanning isn't worse than the adjacency list, which would have close to V neighbors per node anyway. Frequent edge existence queries. If your algorithm constantly asks "is there an edge between u and v?" (like Floyd-Warshall does), the O(1) lookup is unbeatable. Small graphs. If V is under 1000 or so, the V^2 space is negligible, and the simplicity of a 2D array is hard to beat. Floyd-Warshall algorithm. Specifically designed around the matrix representation. The algorithm literally iterates over matrix[i][j] entries.

# Floyd-Warshall — all-pairs shortest paths
def floyd_warshall(n, adj_matrix):
    dist = [row[:] for row in adj_matrix]  # copy

for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

return dist

When NOT to Use Adjacency Matrix

Sparse graphs. A social network with 10 million users where each user has 100 friends has V=10^7 and E=10^9. An adjacency matrix would use 10^14 entries. That's about 100 terabytes. An adjacency list uses space proportional to the actual edges — about 10^9 entries, or a few gigabytes. When you need to iterate over neighbors. If your algorithm's main operation is "for each neighbor of u, do something" (like BFS, DFS, Dijkstra), scanning a row of V entries to find the few non-zero ones is wasteful. The adjacency list gives you the neighbors directly.

Adjacency List

Each node stores a list of its neighbors. The most common representation in practice.

from collections import defaultdict

# using a dictionary of lists
graph = defaultdict(list)

# add edge from 0 to 1
graph[0].append(1)
graph[1].append(0)  # for undirected graph

# with weights
weighted_graph = defaultdict(list)
weighted_graph[0].append((1, 5))  # edge to node 1 with weight 5
weighted_graph[1].append((0, 5))

Or using a list of lists when nodes are numbered 0 to n-1:

n = 5
graph = [[] for _ in range(n)]

# add edge from 0 to 1
graph[0].append(1)
graph[1].append(0)

Check if edge exists between u and v: O(degree(u)) — scan u's neighbor list. Worse than matrix. Get all neighbors of node u: O(degree(u)). Optimal — you only touch actual neighbors. Space: O(V + E). Proportional to the actual size of the graph. Add an edge: O(1) — append to both lists. Remove an edge: O(degree(u)) — find and remove from the list. Slow if you need it often.

When to Use Adjacency List

Almost always. Seriously. The adjacency list is the default representation for graphs in most contexts:

• BFS and DFS are O(V + E) with an adjacency list, but O(V^2) with a matrix (because scanning each row for neighbors takes O(V))
• Dijkstra, Bellman-Ford, Kruskal's, Prim's — all designed around adjacency lists
• Memory-efficient for sparse graphs, which is the common case
• Easier to construct from edge lists (the typical input format in interview problems)

# BFS with adjacency list — clean and efficient
from collections import deque

def bfs(graph, start, n):
    visited = [False] * n
    visited[start] = True
    queue = deque([start])
    order = []

while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:  # only actual neighbors
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

return order

Compare with the matrix version:

# BFS with adjacency matrix — wasteful for sparse graphs
def bfs_matrix(matrix, start, n):
    visited = [False] * n
    visited[start] = True
    queue = deque([start])
    order = []

while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in range(n):  # check ALL nodes
            if matrix[node][neighbor] and not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

return order

For a graph with V=10000 and E=20000 (sparse), the list version does about 20000 neighbor checks total. The matrix version does 100 million. Same algorithm, different representation, wildly different performance.

Adjacency Set

A variant: use a set instead of a list for neighbors.

graph = defaultdict(set)
graph[0].add(1)
graph[1].add(0)

Check if edge exists: O(1) average (hash set lookup). Add an edge: O(1). Remove an edge: O(1). Iterate neighbors: O(degree(u)).

This is great when you need both fast neighbor iteration AND fast edge existence queries. The tradeoff is higher constant factors and more memory per edge compared to a plain list.

Edge List

The simplest representation: just a list of all edges.

edges = [
    (0, 1, 5),   # edge from 0 to 1, weight 5
    (1, 2, 3),
    (0, 2, 10),
]

Check if edge exists: O(E). Terrible. Get all neighbors: O(E). Also terrible. Space: O(E). Sort by weight: O(E log E). And this is where edge lists shine.

When to Use Edge List

Edge lists are the input format for many problems, and they're the ideal representation for algorithms that process edges in sorted order:

• Kruskal's MST — sort edges by weight, process them in order
• Bellman-Ford — iterate over all edges V-1 times

For Kruskal's, you don't need to build an adjacency list at all. Just sort the edge list and go.

def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])  # sort by weight
    uf = UnionFind(n)
    mst_weight = 0
    mst_edges = []

for u, v, w in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst_weight += w
            mst_edges.append((u, v, w))

return mst_weight, mst_edges

For most other algorithms, you'll convert the edge list to an adjacency list first:

def edges_to_adj_list(n, edges, directed=False):
    graph = [[] for _ in range(n)]
    for u, v, *w in edges:
        weight = w[0] if w else 1
        graph[u].append((v, weight))
        if not directed:
            graph[v].append((u, weight))
    return graph

The Decision Matrix

Here's a practical summary:

Operation	Adj. Matrix	Adj. List	Edge List
Space	O(V^2)	O(V + E)	O(E)
Check edge (u,v)	O(1)	O(deg(u))	O(E)
All neighbors of u	O(V)	O(deg(u))	O(E)
Add edge	O(1)	O(1)	O(1)
Remove edge	O(1)	O(deg(u))	O(E)
Iterate all edges	O(V^2)	O(V + E)	O(E)

Default to adjacency list. Switch to matrix only for dense graphs, small graphs, or algorithms like Floyd-Warshall. Use edge list when you just need to sort and process edges.

Implementation Choices in Practice

Directed vs. Undirected

For an undirected graph, add the edge in both directions:

# adjacency list, undirected
graph[u].append(v)
graph[v].append(u)

# adjacency matrix, undirected
matrix[u][v] = 1
matrix[v][u] = 1

For a directed graph, only add it once. This seems obvious, but getting it wrong is a common bug. Read the problem statement carefully to determine if the graph is directed.

Handling Multiple Edges and Self-Loops

Adjacency lists naturally handle multiple edges between the same pair of nodes (just append both). Adjacency matrices don't — the cell matrix[u][v] can only hold one value. If you need multi-edges, use a list or store a count.

Self-loops: graph[u].append(u) or matrix[u][u] = 1. Most algorithms work fine with self-loops, but some (like topological sort) might need special handling.

Node Labels That Aren't Integers

If nodes are strings or other non-integer types, use a dictionary:

graph = defaultdict(list)
graph["New York"].append(("Boston", 200))
graph["Boston"].append(("New York", 200))

Or map labels to integers first:

label_to_id = {}
def get_id(label):
    if label not in label_to_id:
        label_to_id[label] = len(label_to_id)
    return label_to_id[label]

Integer-based representations are faster because array indexing is O(1) without hash overhead.

Implicit Graphs

Sometimes you don't build the graph explicitly at all. Grid problems, for example:

# implicit graph — neighbors are adjacent cells
def get_neighbors(r, c, rows, cols):
    neighbors = []
    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            neighbors.append((nr, nc))
    return neighbors

The "graph" is the grid itself. Neighbors are computed on the fly. This is memory-efficient and natural for grid-based BFS/DFS problems. No need to convert the grid into an adjacency list unless you're doing something unusual.

Common Mistakes

Using a matrix for a sparse graph and wondering why it's slow. If V is 10^5 and E is 10^5, an adjacency matrix uses 10^10 space. You'll run out of memory before the algorithm even starts. Building the wrong graph direction. If the problem says "course B has prerequisite A," the edge goes from A to B (A must come before B), not B to A. Draw it out before coding. Not handling 0-indexed vs. 1-indexed nodes. Some problems use 1-indexed nodes. If you create a graph with n entries (0 to n-1) and the problem uses nodes 1 to n, you'll be off by one. Either create n+1 entries or subtract 1 from every node. Forgetting to add edges in both directions for undirected graphs. This is the single most common graph bug. If the traversal is missing nodes or components, check this first. Using adjacency list but needing fast edge queries. If your algorithm repeatedly checks "does edge (u,v) exist?", an adjacency list is O(degree) per check. Switch to an adjacency set, or precompute a matrix if the graph is small enough.

The Bottom Line

Graph representation is a foundational decision that affects everything downstream. The adjacency list is your default — it handles sparse graphs efficiently, supports all standard algorithms, and matches the way interview problems present input. Reach for the matrix only when the algorithm demands it (Floyd-Warshall) or the graph is small and dense. Use edge lists when all you need is to sort and process edges.

Get comfortable building graphs from scratch on CodeUp. Start by converting edge lists to adjacency lists, then implement BFS and DFS on both representations. Once you can build a graph in your sleep, graph problems become purely about the algorithm — not about struggling with the data structure underneath.