Graph Representation: Adjacency List vs Matrix, Building Graphs from Input, and Cycle Detection

By 0xmote · May 25, 2026 · 15 min read · Updated Sep 27, 2026 Intermediate Tutorial

Key takeaways

Most graph bugs happen before the traversal starts: a missing reverse edge, a 1-indexed input stored in a 0-indexed list, a matrix that does not fit in memory. This guide covers how to choose and build a graph representation, what each one costs, and the component, cycle and topological-sort patterns that sit on top of it.

Introduction

A graph is a set of vertices connected by edges. Trees, road maps, dependency lists, social networks, grids and the states of a puzzle are all graphs, which is why graph problems show up so often in interviews and contests. The traversal algorithms themselves, BFS and DFS, are short. In my experience the part that actually breaks is the step before them: turning the input into a structure the traversal can walk.

The input is almost never handed to you as a graph. It arrives as a list of pairs, a list of prerequisites, a grid of characters, or a rule for which words are one letter apart. You have to decide which way edges point, whether vertices are numbered from 0 or 1, and how to store neighbors so that the traversal costs O(V + E) and not O(V²). This article focuses on those decisions and on the problems that sit directly on top of the representation. Traversal order and when to choose BFS or DFS are covered in BFS vs DFS.

The Properties That Change the Code

    1 --- 2
    |     |
    3 --- 4

Vertices 1 to 4, edges 1-2, 1-3, 2-4 and 3-4. The degree of vertex 1 is 2, 1 → 2 → 4 is a path, and 1 → 2 → 4 → 3 → 1 is a cycle. The vocabulary matters less than the questions it forces you to answer before writing code:

Directed or undirected? “a depends on b”, “a follows b” and one-way streets are directed. Friendships and two-way roads are undirected, which means every input edge is stored twice.
Weighted? If edges have costs and the question asks for the cheapest path, BFS is no longer correct; you need Dijkstra (non-negative weights) or Bellman-Ford.
Multi-edges and self-loops? Some inputs repeat an edge or connect a vertex to itself. They matter for cycle detection and degree counts.
Sparse or dense? A simple undirected graph has at most V(V-1)/2 edges. Most problem inputs are far below that: 10^5 vertices and 2·10^5 edges is typical, and that is what makes the adjacency matrix a bad default.

Adjacency List: The Default

An adjacency list stores, for each vertex, only the vertices it is connected to. Memory is O(V + E), and iterating over a vertex’s neighbors costs O(degree), which is what makes BFS and DFS O(V + E).

Building it from an edge list

The input usually looks like “n vertices, then m lines of a b”. With vertices numbered 1 to n, allocate n + 1 slots and ignore index 0, rather than subtracting 1 everywhere and forgetting once:

n = 5
edges = [(1, 2), (1, 3), (2, 4), (3, 4)]

graph = [[] for _ in range(n + 1)]  # index 0 unused, vertex 5 is isolated
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)  # omit this line for a directed graph

print(graph)  # [[], [2, 3], [1, 4], [1, 4], [2, 3], []]

For weighted graphs, store (neighbor, weight) pairs:

graph = [[] for _ in range(n + 1)]
for a, b, w in [(1, 2, 5), (1, 3, 3), (2, 4, 2), (3, 4, 2)]:
    graph[a].append((b, w))
    graph[b].append((a, w))

Why I prefer a list of lists over a dict

A defaultdict(list) looks convenient, but it has two traps. First, vertices with no edges never become keys, so a loop like for node in graph silently skips isolated vertices, and a component count comes out too low. Second, merely reading graph[x] for a missing key inserts it, which can blow up an iteration over the same dict:

from collections import defaultdict

g = defaultdict(list)
for a, b in [(1, 2), (2, 3)]:
    g[a].append(b)
print(list(g))  # [1, 2]  vertex 3 is missing

for node in g:
    for nb in g[node]:
        _ = g[nb]  # inserts key 3 during iteration
# RuntimeError: dictionary changed size during iteration

When vertices are integers 0..n or 1..n, a list of lists avoids both problems and is faster to index. A dict is the right choice when vertices are strings or sparse IDs, and then you should add every vertex explicitly, not only the ones that appear in edges.

Checking whether an edge exists

Checking b in graph[a] scans the neighbor list, so it costs O(degree(a)), not O(1). If a problem asks many “is there an edge?” questions, store neighbors in sets (graph = [set() for _ in range(n + 1)]), which also removes duplicate edges for free.

Adjacency Matrix: When It Wins and What It Costs

An adjacency matrix is a V × V grid where matrix[i][j] is 1 (or the edge weight) if there is an edge from i to j. Edge checks are O(1), and the code is simple. The price is O(V²) memory and O(V) time to list a vertex’s neighbors, which makes BFS and DFS O(V²) regardless of the number of edges.

To see what O(V²) means in practice, I measured a list-of-lists matrix of zeros with tracemalloc in CPython 3.11:

import tracemalloc

N = 2000
tracemalloc.start()
matrix = [[0] * N for _ in range(N)]
print(tracemalloc.get_traced_memory()[0] / 1e6)  # about 32 MB

That is 8 bytes per cell, because each slot holds a pointer. By the same arithmetic, 10^4 vertices need about 800 MB and 10^5 vertices about 80 GB, while an adjacency list for 2000 vertices and 10^4 random edges measured under 1 MB. A bytearray per row cuts the matrix to one byte per cell (about 4 MB for N = 2000), which is worth knowing when you do need a matrix of booleans.

The matrix is the right choice when V is small (a few hundred to a couple of thousand), when the graph is dense, or when the algorithm touches every pair anyway, as Floyd-Warshall all-pairs shortest paths does in O(V³).

The row-aliasing bug

One mistake is specific to building matrices in Python:

bad = [[0] * 3] * 3
bad[0][1] = 1
print(bad)   # [[0, 1, 0], [0, 1, 0], [0, 1, 0]]  every row changed

good = [[0] * 3 for _ in range(3)]
good[0][1] = 1
print(good)  # [[0, 1, 0], [0, 0, 0], [0, 0, 0]]

[row] * 3 copies the reference to one row three times. Setting one edge sets it in every row, and the resulting graph looks like every vertex is connected to everything.

Comparison

	Adjacency list	Adjacency matrix
Memory	O(V + E)	O(V²)
Is (u, v) an edge?	O(deg(u)), or O(1) average with sets	O(1)
List neighbors of u	O(deg(u))	O(V)
BFS / DFS over the whole graph	O(V + E)	O(V²)
Good fit	Almost all problem inputs	Small or dense graphs, Floyd-Warshall

Two other representations

Edge list. Sometimes you do not need neighbors at all. Kruskal’s minimum spanning tree sorts all edges by weight, and Bellman-Ford relaxes every edge V - 1 times. Both just keep the input as a list of (u, v, w) tuples.

Implicit graphs. In a grid, each cell is a vertex and its four neighbors are edges, but building an adjacency list would only waste memory. Generate neighbors on the fly:

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1" or seen[r][c]:
                continue
            islands += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                y, x = stack.pop()
                for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < rows and 0 <= nx < cols \
                            and grid[ny][nx] == "1" and not seen[ny][nx]:
                        seen[ny][nx] = True
                        stack.append((ny, nx))
    return islands

print(count_islands(["11000", "11000", "00100", "00011"]))  # 3

The same idea applies to puzzle states and word ladders: the “graph” is a rule for producing neighbors, not a stored structure.

Traversal on Top of the Representation

Traversal itself is covered in depth in BFS vs DFS, so here is only the one version you need most often: shortest path length in an unweighted graph. BFS visits vertices in order of distance from the start, so the first time a vertex is reached is along a shortest path. Storing distances in a dict doubles as the visited set:

from collections import deque

def shortest_path(graph, start, end):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == end:
            return dist[node]
        for nb in graph[node]:
            if nb not in dist:          # mark when enqueued, not when popped
                dist[nb] = dist[node] + 1
                queue.append(nb)
    return -1

graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
print(shortest_path(graph, 1, 4))  # 2  (1 -> 2 -> 4)
print(shortest_path(graph, 1, 1))  # 0
print(shortest_path(graph, 4, 1))  # -1  edges are directed

Marking a vertex when it is enqueued rather than when it is dequeued matters: otherwise the same vertex can enter the queue once per incoming edge, which on dense graphs turns O(V + E) into something much slower.

Problems That Sit Directly on the Representation

Counting connected components

Start a traversal from every vertex that has not been seen yet; each start is a new component. A recursive DFS is the shortest way to write this, and it is also the most common way to fail a hidden test in Python:

import sys
print(sys.getrecursionlimit())  # 1000

# A path 0-1-2-...-4999 makes a recursive DFS 5000 frames deep:
# RecursionError: maximum recursion depth exceeded

sys.setrecursionlimit(10**6) is a common fix, but the limit exists to protect the C stack; raising it far enough can crash the interpreter with a segmentation fault instead of an exception. I have seen a solution pass every sample, then die on the one test shaped like a long chain. The robust version uses an explicit stack:

def count_components(n, edges):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    seen = [False] * n
    count = 0
    for s in range(n):
        if seen[s]:
            continue
        count += 1
        seen[s] = True
        stack = [s]
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if not seen[v]:
                    seen[v] = True
                    stack.append(v)
    return count

print(count_components(5, [[0, 1], [1, 2], [3, 4]]))  # 2
print(count_components(6, [[0, 1], [1, 2], [3, 4]]))  # 3  isolated vertex 5 counts

If you only need connectivity and edges arrive one at a time, Union-Find skips building the graph entirely and handles each edge in nearly constant amortized time:

def count_components_uf(n, edges):
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving
            x = parent[x]
        return x

    comps = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            comps -= 1
    return comps

print(count_components_uf(5, [[0, 1], [1, 2], [3, 4]]))  # 2

Cycle detection in a directed graph

A directed graph has a cycle exactly when DFS finds an edge back to a vertex that is still on the current path. A plain visited set cannot tell “on the current path” from “finished earlier”, and it reports false cycles on diamond shapes such as 1 → 2 → 4 and 1 → 3 → 4, where 4 is reached twice without any cycle. Three colors fix that:

def has_cycle_directed(graph):
    WHITE, GRAY, BLACK = 0, 1, 2  # unvisited, on current path, finished
    color = {u: WHITE for u in graph}

    def dfs(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                return True             # back edge
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    return any(color[u] == WHITE and dfs(u) for u in graph)

print(has_cycle_directed({1: [2], 2: [3], 3: [1]}))                # True
print(has_cycle_directed({1: [2, 3], 2: [4], 3: [4], 4: []}))      # False

This version is recursive for readability; for deep graphs, use Kahn’s algorithm below, which detects cycles without recursion.

Cycle detection in an undirected graph

In an undirected graph every edge is stored in both directions, so DFS always sees the vertex it just came from as “visited”. The usual fix is to skip the parent vertex, but that misses a real cycle formed by two parallel edges between the same pair. Skipping the specific edge you arrived by, identified by its index, handles both cases:

def has_cycle_undirected(n, edges):
    graph = [[] for _ in range(n)]
    for i, (a, b) in enumerate(edges):
        graph[a].append((b, i))
        graph[b].append((a, i))

    seen = [False] * n
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        stack = [(s, -1)]
        while stack:
            u, via = stack.pop()
            for v, eid in graph[u]:
                if eid == via:
                    continue            # the edge we arrived by
                if seen[v]:
                    return True
                seen[v] = True
                stack.append((v, eid))
    return False

print(has_cycle_undirected(3, [(0, 1), (1, 2)]))          # False
print(has_cycle_undirected(3, [(0, 1), (1, 2), (2, 0)]))  # True
print(has_cycle_undirected(2, [(0, 1), (0, 1)]))          # True  parallel edges

Union-Find gives the same answer more simply: an edge whose two endpoints already share a root closes a cycle.

Topological sort (Kahn’s algorithm)

Course Schedule style problems give pairs [course, prerequisite]. The edge direction is the first decision: prerequisite → course, because the prerequisite must come first. Kahn’s algorithm repeatedly takes a vertex with no remaining incoming edges. If the queue runs dry before every vertex is placed, the remaining vertices all have an incoming edge from each other, which means a cycle.

from collections import deque

def topo_order(n, prereqs):
    graph = [[] for _ in range(n)]
    indeg = [0] * n
    for course, pre in prereqs:
        graph[pre].append(course)
        indeg[course] += 1

    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == n else []  # [] means a cycle

print(topo_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))  # [0, 1, 2, 3]
print(topo_order(2, [[1, 0], [0, 1]]))                  # []

Reversing the edge direction here still produces an order, just the reverse of the correct one, which is exactly the kind of bug that passes a symmetric sample and fails everything else.

Where Graph Solutions Go Wrong

When I review my own failed graph submissions, they fall into a short list, and almost none are about the traversal logic:

Forgetting the reverse edge in an undirected graph, so half the graph is unreachable from some starts.
Index mismatch: 1-indexed input into a list of size n, giving an IndexError on vertex n or silently merging vertex n into vertex 0 after subtracting inconsistently.
Isolated vertices: iterating over the keys of a dict built from edges, so vertices with no edges are never counted.
Recursion depth: a recursive DFS that works on random tests and fails on a chain of 10^5 vertices.
Marking visited too late in BFS, so vertices are enqueued many times.
Choosing a matrix for a sparse graph because the edge check looked convenient, then running out of memory at 10^4 or more vertices.

The habit that catches most of them is printing the adjacency list for the smallest sample before writing any traversal. If the list does not look like the picture in the problem statement, the rest does not matter yet.

Graph representation decisions at a glance

Decision	Default	Switch when
Storage	List of lists, size n + 1 for 1-indexed input	Vertices are strings or sparse IDs (dict with all vertices added)
Neighbor container	list	Many edge-existence checks or duplicate edges (set)
Matrix	Avoid	V is small, graph is dense, or Floyd-Warshall
DFS style in Python	Explicit stack	Depth is guaranteed small
Connectivity only	Union-Find	You need paths or order (traverse instead)
Directed cycle	Three colors or Kahn
Undirected cycle	Skip the arrival edge, or Union-Find