Graph Representations

The concept of a graph is abstract; it has to turn into a representation in code. There are two basic options, and the difference between them is an instance of this course’s recurring theme: the same data, a different layout, a different cost.

The choice depends on the graph’s edge density and on which operations will be performed often. A choice made without knowing these two factors can raise an algorithm’s cost by an entire order unnecessarily.

Adjacency Matrix

An adjacency matrix is a table of size $\lvert V \rvert \times \lvert V \rvert$. The cell at row $i$, column $j$ states whether an edge exists between $i$ and $j$; in a weighted graph it carries the weight.

INF = float("inf")
vertices = ["center", "east", "north", "south", "west"]
index = {name: i for i, name in enumerate(vertices)}
n = len(vertices)

matrix = [[INF] * n for _ in range(n)]
for i in range(n):
    matrix[i][i] = 0

for a, b, weight in [("north", "center", 4), ("south", "center", 2),
                      ("east", "center", 7), ("west", "north", 3),
                      ("west", "south", 5)]:
    matrix[index[a]][index[b]] = weight
    matrix[index[b]][index[a]] = weight           # undirected: both cells

print(matrix[index["west"]][index["north"]])      # 3    — edge exists
print(matrix[index["west"]][index["east"]])       # inf  — no edge
print(sum(1 for x in matrix[index["center"]] if x not in (0, INF)))   # 3 — degree

Advantage: Whether an edge exists between two vertices is answered by a single read, in $O(1)$.

Cost: Memory is always $O(\lvert V \rvert^2)$ — independent of the number of edges. Also, listing a vertex’s neighbors requires scanning the entire row: $O(\lvert V \rvert)$.

In an undirected graph the matrix is symmetric about its diagonal; storing only half halves the memory but does not change the order.

Adjacency List

An adjacency list keeps, for each vertex, only the list of its neighbors.

from collections import defaultdict

adjacency: dict[str, list[tuple[str, int]]] = defaultdict(list)
for a, b, weight in [("north", "center", 4), ("south", "center", 2),
                      ("east", "center", 7), ("west", "north", 3),
                      ("west", "south", 5)]:
    adjacency[a].append((b, weight))
    adjacency[b].append((a, weight))               # undirected: added both ways

print(sorted(adjacency["center"]))
# [('east', 7), ('north', 4), ('south', 2)]
print(len(adjacency["west"]))                      # 2   — degree read directly
print(any(neighbor == "east" for neighbor, _ in adjacency["west"]))   # False

Advantage: Memory is $O(\lvert V \rvert + \lvert E \rvert)$ — only existing edges are stored. Traversing a vertex’s neighbors takes time proportional to its degree.

Cost: Whether an edge exists between two vertices is found by scanning the list — $O(\text{degree})$.

Sparsity Decides

The deciding criterion is the ratio of edge count to vertex count.

If a graph is dense ($\lvert E \rvert \approx \lvert V \rvert^2$), the matrix is reasonable both in memory and in giving a constant-time edge query.

If a graph is sparse ($\lvert E \rvert \approx \lvert V \rvert$), the matrix stays almost entirely empty. In a road network with ten thousand vertices and thirty thousand edges, the matrix demands a hundred million cells; the adjacency list gets by with forty thousand entries.

The large majority of real graphs are sparse: each city connects to a handful of cities, each person to a few hundred people, each page to a few dozen pages. For this reason the default choice is the adjacency list; the matrix is preferred when vertex count is small or the graph is dense.

A Third Option: The Edge List

The plainest representation is a flat list of edges — this was the edges variable from the previous lesson.

It is unsuited to traversal: finding a vertex’s neighbors requires scanning the entire list. It is, however, the right choice in two situations: algorithms that work on all edges in sequence (such as a minimum-spanning-tree algorithm that sorts edges by weight and processes them), and cases where the graph needs to be stored or transmitted.

Comparison

Operation	Adjacency matrix	Adjacency list	Edge list
Memory	$O(V^2)$	$O(V + E)$	$O(E)$
Edge exists	$O(1)$	$O(\text{degree})$	$O(E)$
Traverse neighbors	$O(V)$	$O(\text{degree})$	$O(E)$
Add edge	$O(1)$	$O(1)$	$O(1)$
Remove edge	$O(1)$	$O(\text{degree})$	$O(E)$
Traverse all edges	$O(V^2)$	$O(V + E)$	$O(E)$

In the table, $V$ and $E$ denote the vertex and edge counts; “degree” is the neighbor count of the vertex in question and behaves like a small constant in sparse graphs.

Do not let the equality in the fourth row mislead: adding an edge in the matrix is constant time, but the matrix itself was allocated up front — adding a vertex requires rebuilding the matrix. In the adjacency list, adding a vertex only opens a new entry.

Vertex Identities

In the examples above, vertices were referred to by string names. In large graphs this produces two costs: a string hash is computed on every access, and every vertex name sits in memory as a separate object.

The common solution is to give vertices integer identities. Names are scanned once, each name is assigned a sequential number, and from then on every structure uses that number as an index.

names = ["center", "east", "north", "south", "west"]
identity = {name: i for i, name in enumerate(names)}

neighbor_list: list[list[int]] = [[] for _ in names]
for a, b in [("north", "center"), ("south", "center"), ("east", "center"),
             ("west", "north"), ("west", "south")]:
    neighbor_list[identity[a]].append(identity[b])
    neighbor_list[identity[b]].append(identity[a])

print(neighbor_list[identity["center"]])       # [2, 3, 1]
print([names[i] for i in neighbor_list[identity["center"]]])
# ['north', 'south', 'east']

The gain is not only speed: visited markers, distances, and parent records can also be kept in flat arrays instead of mappings. This is a significant improvement both in memory and in cache behavior, and it is the standard approach for libraries that work with large graphs.

Effect on Traversal Cost

The cost of the traversal algorithms taken up in the next two lessons depends directly on the representation. Each vertex is visited once and its neighbors are traversed:

• With an adjacency list the total cost is $O(V + E)$ — each edge is examined twice.
• With an adjacency matrix it is $O(V^2)$ — the entire row is scanned for each vertex, even where no edge exists.

In a sparse graph this is the difference between linear and quadratic. Representation choice is therefore not a detail but a decision that determines the algorithm’s cost class.

As a third option, both representations can be kept together: an adjacency list for traversal, an additional set for frequent edge tests. This approach, which trades memory to make both operations cheap, is one of the cases where keeping the same data in more than one structure is legitimate — a conscious use of the trade-off repeated since the first lesson of this course.

Summary

• The adjacency matrix makes edge queries constant time; its memory is $O(V^2)$ regardless of edge count.
• The adjacency list stores only existing edges; memory is $O(V + E)$, and traversing neighbors costs as much as the degree.
• The list suits sparse graphs, the matrix suits dense ones; most real graphs are sparse.
• The edge list is unsuited to traversal but suits algorithms that work over all edges and data transmission.
• Traversal algorithm cost depends on the representation: $O(V+E)$ with a list, $O(V^2)$ with a matrix.

Next Step

With a representation in place, traversal can begin. The next lesson takes up breadth-first search, which scans a graph layer by layer starting from an initial vertex, and how it solves the unweighted shortest-path problem.