PYTHON / DATA STRUCTURES AND ALGORITHMS
Graphs and their representations
Build a graph as an adjacency dict, adjacency matrix, or edge list, and pick the representation from the graph's density and query pattern.
What you will learn
- Store sparse graphs as a dict of sets: O(V+E) space, average O(1) edge tests
- Write add_edge once so undirected edges can never be stored in one direction only
- Use a matrix only when E approaches V^2, because it always costs V^2 cells
- Model weights as a dict of dicts so adj[u][v] holds the edge's weight
Understanding Graphs and their representations
A graph is just a set of nodes plus a set of edges saying which nodes touch which. Unlike a binary tree there is no root, no left/right, no guarantee of acyclicity, and a node may have any number of neighbours; a tree and a linked list are both special cases of a graph. Because of that, a graph structure stores only the relation "u is adjacent to v" — everything else, like distance or ordering, is computed by an algorithm on top of that relation.
Three representations cover almost all Python code. An adjacency list is a dict mapping each node to its neighbour collection: it uses O(V+E) space, listing the neighbours of u costs O(deg(u)), and if the neighbours are a set then "is u-v an edge?" is average O(1). An adjacency matrix is a V x V table of 0/1 (or weights): edge lookup is a single index, but it always burns V^2 cells and listing one node's neighbours means scanning a whole row of V entries. An edge list, a flat list of (u, v) tuples, is the most compact input format and the worst thing to query, since any neighbour question means scanning all E edges.
The one invariant that bites people is direction. In a directed graph adj[u] contains v only if the edge points u -> v; in an undirected graph every edge must be recorded twice, and if you forget one side, no exception is raised — traversals silently see a smaller graph. Density decides the representation: a social graph with 10^5 nodes and 4x10^5 edges needs 10^10 matrix cells, so use a dict of sets; a dense 200-node distance table with weights is perfectly happy as a matrix.
graph = {
"A": {"B", "C"},
"B": {"A", "D"},
"C": {"A", "D"},
"D": {"B", "C", "E"},
"E": {"D"},
}
print("neighbours of D:", sorted(graph["D"]))
print("degree of D:", len(graph["D"]))
print("A-D an edge?", "D" in graph["A"])
print("symmetric:", all(u in graph[v] for u in graph for v in graph[u]))
nodes = sorted(graph)
pos = {name: i for i, name in enumerate(nodes)}
matrix = [[0] * len(nodes) for _ in nodes]
for u in graph:
for v in graph[u]:
matrix[pos[u]][pos[v]] = 1
print(" " + " ".join(nodes))
for name in nodes:
print(name + " " + " ".join(str(c) for c in matrix[pos[name]]))
edges = sorted({tuple(sorted((u, v))) for u in graph for v in graph[u]})
print("edge list:", edges)
print("space: %d matrix cells vs %d adjacency entries"
% (len(nodes) ** 2, sum(len(s) for s in graph.values())))A graph representation is a space/time trade-off: adjacency dicts cost O(V+E) space with O(deg) neighbour scans, matrices cost O(V^2) space for constant-time edge tests.
Worked examples
Weighted directed graph as a dict of dicts
Stores a weight per edge and computes in-degrees from the outgoing-edge table.
from collections import defaultdict
roads = [("home", "work", 12), ("home", "gym", 5),
("gym", "work", 9), ("work", "home", 15)]
out = defaultdict(dict)
nodes = set()
for u, v, w in roads:
out[u][v] = w
nodes.update((u, v))
for n in sorted(nodes):
print(n, "->", dict(sorted(out[n].items())))
in_deg = {n: 0 for n in nodes}
for u in list(out):
for v in out[u]:
in_deg[v] += 1
print("in-degrees:", dict(sorted(in_deg.items())))
print("weight home->gym:", out["home"]["gym"])
print("weight gym->home:", out["gym"].get("home", "no edge"))Example explained
Line 1out[u][v] = w replaces the neighbour set with a mapping, so the weight lives in the same lookup as adjacency.
Line 2Only out['home']['work'] is set, not the reverse, so this graph is directed: gym->home does not exist.
Line 3In-degree is not stored anywhere, so it must be counted by walking every outgoing list once, O(V+E).
Line 4out['gym'].get('home', ...) avoids a KeyError; out['gym']['home'] would raise because inner dicts are plain dicts.
Edge list to adjacency dict, including isolated nodes
Shows why the node set must be seeded separately instead of derived from the edges.
edges = [(1, 2), (2, 3), (3, 1), (4, 3)]
nodes = [1, 2, 3, 4, 5] # 5 has no edges at all
adj = {n: [] for n in nodes} # every node exists up front
for u, v in edges:
adj[u].append(v)
for n in nodes:
print(n, adj[n])
from_edges = {}
for u, v in edges:
from_edges.setdefault(u, []).append(v)
print("keys built from edges only:", sorted(from_edges))
try:
from_edges[5]
except KeyError as e:
print("KeyError:", e)Example explained
Line 1The comprehension {n: [] for n in nodes} guarantees adj[5] exists as an empty list, so node 5 is part of the graph.
Line 2Node 5 prints as 5 [] — an isolated node is a real node with degree 0, not a missing key.
Line 3from_edges never sees 5 (and would also miss any node that is only a target), so lookups crash later during traversal.
Why a matrix row scan costs O(V)
Counts cells touched to list one leaf's neighbours in a star graph, matrix versus adjacency set.
n = 6
matrix = [[0] * n for _ in range(n)]
adj = {i: set() for i in range(n)}
for v in range(1, n): # node 0 joined to 1..5
matrix[0][v] = matrix[v][0] = 1
adj[0].add(v)
adj[v].add(0)
cells_read = 0
found = []
for v in range(n):
cells_read += 1
if matrix[3][v]:
found.append(v)
print("matrix scan:", found, "cells read:", cells_read)
print("adjacency set:", sorted(adj[3]), "cells read:", len(adj[3]))
print("stored:", n * n, "matrix cells vs",
sum(len(s) for s in adj.values()), "adjacency entries")Example explained
Line 1matrix[3] has one 1 in it, but finding it requires reading all n entries of the row: O(V) per node.
Line 2adj[3] holds exactly the neighbours, so iteration costs O(deg(u)) with no wasted reads.
Line 3The last line is the density argument: 36 cells to record 5 edges, versus 10 stored directed entries.
Important notes
A 0/1 matrix cannot represent parallel edges; store an integer count or switch to lists of neighbours if multi-edges matter. A self-loop conventionally adds 2 to an undirected degree but appears as a single set element.
Sets are unordered, so neighbour iteration order is not insertion order and can vary between node types; sort neighbours when you need reproducible traversal output or stable tests.
Common mistakes
Building the adjacency dict from the edge list only: nodes with no outgoing edges never get a key, and the first adj[v] during a traversal raises KeyError.
Storing an undirected edge in one direction only (adj[u].add(v) but not adj[v].add(u)): nothing raises, but BFS/DFS reports a smaller connected component and shortest paths silently come out too long.
Using defaultdict(set) and probing adj[u] for a node that may not exist: the read inserts an empty entry, inflating len(adj) and degree counts, and mutating the dict mid-iteration raises RuntimeError: dictionary changed size during iteration.
Try it yourself
Change, predict, then run
Given edges = [(0,1),(1,2),(2,0),(3,4)] and nodes 0 through 5, build an undirected adjacency dict of sets, print each node with its degree in numeric order, and assert that the total of all degrees equals 2 * len(edges).
Open the Python workspaceCheck your understanding
You need to store 100,000 accounts with 400,000 follow relations and frequently ask both "does u follow v?" and "who does u follow?". Which representation fits best?
- A dict mapping each account to a set of the accounts it follows
- A 100,000 x 100,000 adjacency matrix, because edge lookup must be constant time
- A flat list of (follower, followee) tuples, because it stores the least data
- A dict mapping each account to a list of the accounts it follows, because lists index faster than sets
Show answer
A dict of sets uses about 4x10^5 entries and gives average O(1) for `v in adj[u]` plus O(deg(u)) neighbour iteration. The matrix is tempting because indexing is constant time, but it would allocate 10^10 cells to record 4x10^5 edges — the set already gives constant-time lookup without that cost. The edge list forces an O(E) scan for every question, and a list of neighbours makes the membership test O(deg(u)) instead of O(1).