Graph Representations

A graph is a collection of vertices (nodes) connected by edges (links), and it’s one of the most versatile data structures in computer science — it models anything with relationships, from friend networks and road maps to task dependencies and web links. Before you can traverse a graph or run an algorithm like BFS, DFS, or Dijkstra’s on it, you first have to decide how to represent it in memory. That choice isn’t cosmetic: it directly determines how fast your algorithms run and how much memory they use. This lesson covers the three standard representations — the adjacency list, the adjacency matrix, and the edge list — and when to reach for each one.

Overview / How it works

A graph G = (V, E) is defined by a set of vertices V and a set of edges E connecting pairs of vertices. Edges can be directed (a one-way relationship, like \”A follows B\”) or undirected (a symmetric relationship, like \”A is friends with B\”), and they can be unweighted (an edge just exists or doesn’t) or weighted (an edge carries a cost, like flight price or road distance). None of that changes when you pick a representation — the representation only changes how the vertices and edges are stored.

Imagine a tiny social network with five people, numbered 0 through 4, where 0–1, 0–2, and 1–2 are mutual friends, and 3–4 is a separate friendship. There are three natural ways to write this down:

Edge list

The simplest representation: just a flat list of the edges themselves, e.g. [(0, 1), (0, 2), (1, 2), (3, 4)]. It’s compact and is exactly how you’d receive graph data from a file or an API, but it’s slow to query — to find out who 0 is friends with, you must scan every edge.

Adjacency matrix

A V x V grid (a list of lists, or a 2D array) where cell matrix[u][v] is 1 (or a weight) if an edge exists between u and v, and 0 otherwise. Checking \”does an edge exist between u and v?\” is a single array lookup — O(1) — regardless of how many edges the graph has. The cost is space: the matrix always uses V² cells even if the graph has very few edges.

Adjacency list

For each vertex, store only the list (or set) of its neighbors, e.g. a dictionary mapping 0 -> [1, 2], 1 -> [0, 2], 2 -> [0, 1], 3 -> [4], 4 -> [3]. This is the representation used in the overwhelming majority of real code, because most real-world graphs are sparse — the number of edges E is far smaller than the theoretical maximum V². A road network, a social graph, or a dependency graph rarely has anywhere close to every vertex connected to every other vertex, so storing only the edges that actually exist saves enormous amounts of memory.

In Python, an adjacency list is usually a dict mapping each vertex to a list (or set) of neighbors — collections.defaultdict(list) is a natural fit because it lets you append a neighbor without first checking whether the vertex has been seen before. For weighted graphs, the adjacency list becomes a dict of dicts: each vertex maps to a dict of {neighbor: weight} pairs, which gives you both the neighbor list and an O(1) average-case weight lookup in one structure.

Time and Space Complexity

Let V be the number of vertices and E be the number of edges. The three representations trade space for query speed in different ways:

Representation	Space	Add Edge	Check Edge (u, v)	Iterate Neighbors of v	Iterate All Edges
Adjacency List	O(V + E)	O(1)	O(degree(u)), worst O(V)	O(degree(v))	O(V + E)
Adjacency Matrix	O(V²)	O(1)	O(1)	O(V)	O(V²)
Edge List	O(E)	O(1)	O(E)	O(E)	O(E)

The reasoning behind each cell: an adjacency list only stores an entry per vertex plus one entry per edge endpoint, so its space is proportional to V + E — for a sparse graph where E is close to V, that’s dramatically smaller than a matrix’s fixed V². Checking whether edge (u, v) exists in an adjacency list means scanning u‘s neighbor list (or, if you used a set instead of a list, an O(1) average-case hash lookup — a common upgrade). A matrix gives O(1) edge checks unconditionally because it’s just direct index access, which is why matrices shine for dense graphs or algorithms (like Floyd-Warshall) that repeatedly ask \”is there an edge here?\” An edge list has no per-vertex index at all, so any targeted query means a linear scan of every edge — it’s really only efficient for algorithms that process all edges once, such as Kruskal’s minimum spanning tree algorithm, which sorts the edge list by weight.

Examples

The following examples build the same small graph — vertices 0–4, with friendships 0–1, 0–2, 1–2, and 3–4 — using each representation.

Example 1: Building an adjacency list

from collections import defaultdict

def build_adjacency_list(edges: list[tuple[int, int]], num_vertices: int) -> dict[int, list[int]]:
    graph: dict[int, list[int]] = defaultdict(list)
    for vertex in range(num_vertices):
        graph[vertex]  # touching the key creates an empty list, so isolated vertices still appear
    for source, destination in edges:
        graph.append(destination)
        graph[destination].append(source)
    return dict(graph)


edges = [(0, 1), (0, 2), (1, 2), (3, 4)]
graph = build_adjacency_list(edges, num_vertices=5)
for vertex in sorted(graph):
    print(f\"{vertex}: {graph[vertex]}\")

Output:

0: [1, 2]
1: [0, 2]
2: [0, 1]
3: [4]
4: [3]

Because defaultdict(list) creates an empty list the moment a key is first accessed, the loop over range(num_vertices) guarantees every vertex shows up in the output — including vertex 3 and 4, whose only connection is to each other. For each edge, both directions are appended since this is an undirected graph: 0 gets 1 added to its list, and 1 gets 0 added to its list.

Example 2: Building an adjacency matrix

def build_adjacency_matrix(edges: list[tuple[int, int]], num_vertices: int) -> list[list[int]]:
    matrix = [[0] * num_vertices for _ in range(num_vertices)]
    for source, destination in edges:
        matrix[destination] = 1
        matrix[destination] = 1
    return matrix


edges = [(0, 1), (0, 2), (1, 2), (3, 4)]
matrix = build_adjacency_matrix(edges, num_vertices=5)
for row in matrix:
    print(row)

Output:

[0, 1, 1, 0, 0]
[1, 0, 1, 0, 0]
[1, 1, 0, 0, 0]
[0, 0, 0, 0, 1]
[0, 0, 0, 1, 0]

Row i represents vertex i‘s connections: row 0 is [0, 1, 1, 0, 0], meaning vertex 0 connects to vertices 1 and 2 but not to 0, 3, or 4. Notice the matrix is symmetric across its diagonal (matrix[u][v] == matrix[v][u] for every pair) — that symmetry is what makes a matrix undirected; a directed graph would only set matrix[destination], producing an asymmetric matrix.

Example 3: A weighted, string-keyed adjacency list

def build_weighted_adjacency_list(edges: list[tuple[str, str, int]]) -> dict[str, dict[str, int]]:
    graph: dict[str, dict[str, int]] = {}
    for source, destination, weight in edges:
        if source not in graph:
            graph = {}
        if destination not in graph:
            graph[destination] = {}
        graph[destination] = weight
    return graph


flights = [(\"JFK\", \"ORD\", 150), (\"JFK\", \"ATL\", 90), (\"ORD\", \"DEN\", 120)]
graph = build_weighted_adjacency_list(flights)
for city in sorted(graph):
    print(f\"{city}: {graph[city]}\")

print(\"JFK -> ATL costs\", graph[\"JFK\"][\"ATL\"])

Output:

ATL: {}
DEN: {}
JFK: {'ORD': 150, 'ATL': 90}
ORD: {'DEN': 120}
JFK -> ATL costs 90

This example treats vertices as airport codes rather than small integers, which is exactly where adjacency lists outshine matrices — you can’t index a Python list with the string \"JFK\", but a dict handles arbitrary hashable keys naturally. This graph is directed (flights only go one way in this data), so only graph[\"JFK\"][\"ORD\"] is set, not graph[\"ORD\"][\"JFK\"] — that’s why ORD and ATL print as empty dicts, since no flight departs from them in this dataset. The final line shows the payoff of the dict-of-dicts shape: looking up the weight of a specific edge is a single O(1) average-case dictionary access, graph[\"JFK\"][\"ATL\"], giving 90.

How it works step by step

Let’s trace build_adjacency_list by hand on a 4-vertex cycle: vertices 0, 1, 2, 3 with edges [(0, 1), (1, 2), (2, 3), (3, 0)].

1. Start with graph = defaultdict(list), completely empty.
2. The vertex-priming loop touches keys 0, 1, 2, 3 in order, creating four empty lists: {0: [], 1: [], 2: [], 3: []}.
3. Edge (0, 1): append 1 to graph[0] and 0 to graph[1]. State: {0: [1], 1: [0], 2: [], 3: []}.
4. Edge (1, 2): append 2 to graph[1] and 1 to graph[2]. State: {0: [1], 1: [0, 2], 2: [1], 3: []}.
5. Edge (2, 3): append 3 to graph[2] and 2 to graph[3]. State: {0: [1], 1: [0, 2], 2: [1, 3], 3: [2]}.
6. Edge (3, 0): append 0 to graph[3] and 3 to graph[0]. Final state: {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [2, 0]}.

Each vertex ends up with exactly two neighbors, which makes sense — in a 4-cycle, every vertex has degree 2. This vertex-by-vertex, edge-by-edge accumulation is exactly what happens under the hood any time you build a graph from a raw edge list, whether that list came from a file, a database query, or user input.

Common Mistakes

Mistake 1: Using a mutable default argument to accumulate a graph

A classic Python trap shows up often in graph-building helper functions:

def add_edge(source: int, destination: int, graph: dict[int, list[int]] = {}) -> dict[int, list[int]]:
    graph.setdefault(source, []).append(destination)
    return graph

first_call = add_edge(0, 1)
second_call = add_edge(5, 6)
print(first_call)

This looks reasonable — \”if no graph is passed, start with an empty one\” — but the default value {} is created once, when the function is defined, and every call that omits graph reuses that exact same dictionary object. Here, first_call and second_call are actually the same dict, so by the time you print first_call, it has been silently polluted with the edge from the second call: it would print {0: [1], 5: [6]} instead of the expected {0: [1]}. This bug gets worse the longer a program runs, since every omitted-argument call keeps mutating the same hidden object.

The fix is the standard Python idiom: default to None, and create a fresh dict inside the function body when no graph was passed in.

def add_edge(source: int, destination: int, graph: dict | None = None) -> dict[int, list[int]]:
    if graph is None:
        graph = {}
    graph.setdefault(source, []).append(destination)
    return graph


first_call = add_edge(0, 1)
second_call = add_edge(5, 6)
print(first_call)
print(second_call)

Output:

{0: [1]}
{5: [6]}

Now each call without an explicit graph argument gets its own independent dictionary, and the two calls no longer interfere with each other.

Mistake 2: Forgetting the symmetric assignment in an undirected adjacency matrix

When building an adjacency matrix for an undirected graph, it’s easy to set only one direction and forget the other:

def build_adjacency_matrix_buggy(edges: list[tuple[int, int]], num_vertices: int) -> list[list[int]]:
    matrix = [[0] * num_vertices for _ in range(num_vertices)]
    for source, destination in edges:
        matrix[destination] = 1
    return matrix

edges = [(0, 1), (1, 2)]
matrix = build_adjacency_matrix_buggy(edges, num_vertices=3)
for row in matrix:
    print(row)

This prints [0, 1, 0], [0, 0, 1], [0, 0, 0] — notice the matrix is no longer symmetric. If later code asks \”is vertex 2 connected to vertex 1?\” by checking matrix[2][1], it gets 0 (no edge) even though the graph clearly has a 1–2 friendship — the query only works in one direction. The fix, shown back in Example 2, is to set both matrix[destination] = 1 and matrix[destination] = 1 for every edge in an undirected graph. (For a genuinely directed graph, setting only one direction is correct — the bug only exists when the graph is meant to be undirected but the code treats it as directed.)

Best Practices

• Default to an adjacency list unless you have a specific reason not to — most real graphs are sparse, and it’s the most memory-efficient and generally-useful representation.
• Reach for an adjacency matrix when the graph is dense (edges close to V²), when V is small, or when your algorithm needs repeated O(1) edge-existence checks (e.g. Floyd-Warshall all-pairs shortest paths).
• Use an edge list when you mainly need to process every edge once, especially sorted by weight — Kruskal’s minimum spanning tree algorithm is the textbook example.
• When vertices aren’t small contiguous integers (strings, tuples, custom objects), use a dict-keyed adjacency list rather than trying to force list indices.
• For weighted graphs, a dict of dicts ({vertex: {neighbor: weight}}) gives you neighbor iteration and weight lookup in one structure.
• If you need fast \”is there an edge from u to v?\” checks but still want sparse-graph memory savings, store each vertex’s neighbors in a set instead of a list — that trades a small amount of memory for O(1) average-case membership checks.
• Always decide up front whether the graph is directed or undirected, and be consistent — an undirected edge means writing both directions, in every representation.
• Never use a mutable object (like {} or []) as a default argument for a function that builds or mutates a graph; default to None and initialize inside the function.

Practice Exercises

1. Isolated vertices. Given a directed edge list like [(0, 1), (1, 2), (3, 3)] and num_vertices = 5, write a function that returns every vertex with no outgoing and no incoming edges. Hint: build the adjacency list first, then track which vertices never appear as a source or a destination.

2. Matrix to list, and back. Write a function matrix_to_adjacency_list that converts an adjacency matrix (a list of lists of 0s and 1s) into an adjacency list (a dict). What is the time complexity of your conversion, in terms of V and E?

3. Total edge weight. Given a weighted, undirected graph stored as a dict of dicts (as in Example 3, but symmetric), write a function that sums the weight of every unique edge exactly once. Hint: iterating every vertex’s neighbor dict directly will count each undirected edge twice — think about how to avoid double-counting.

Summary

• An edge list is a flat list of edges — O(E) space, but any targeted query costs O(E); best for algorithms that process all edges once, like Kruskal’s algorithm.
• An adjacency matrix is a V x V grid — O(V²) space, but O(1) edge-existence checks; best for dense graphs or algorithms needing frequent edge lookups.
• An adjacency list stores each vertex’s neighbors directly — O(V + E) space, with edge checks costing up to O(degree(u)); the right default for most sparse, real-world graphs.
• Undirected edges must be recorded symmetrically in every representation — forgetting the reverse direction is a common bug.
• Never default a mutable argument like {} to a graph-building function — use None and initialize inside the function body.
• Choose vertex keys that fit your data: integer indices for lists/matrices, or a dict-keyed adjacency list when vertices are strings or other hashable objects.