Graph Terms and Adjacency Lists
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Many problems hide a graph: cities and roads, users and friends, tasks and prerequisites. Before any search, you must store the links so that a node can find its neighbours fast. Python makes this short with defaultdict.
Nodes and edges
A graph is a set of nodes, also called vertices, joined by edges. An edge connects two nodes. Graphs model any set of things and the links between them.
A road map has towns and roads between them. A graph is the same idea: points joined by lines. Friend lists, maps, networks and course prerequisites are all graphs.
Words to know
A path is a sequence of nodes where each next node is joined to the one before by an edge. The length of a path is its number of edges, not its number of nodes.
An edge is undirected, like a two-way road, or directed, like a one-way street. The neighbours of a node are the nodes one edge away. Its degree is the number of edges that touch it.
Example 1 · Adjacency matrix: the space-hungry way
n = 5edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]matrix = [[0] * n for _ in range(n)]for a, b in edges: matrix[a][b] = matrix[b][a] = 1print(matrix[3])print(matrix[0][4])[0, 1, 1, 0, 1] 0
What this code does
- A matrix keeps one cell for every pair of nodes, so it needs O(n squared) space. Checking one edge is fast, but listing neighbours scans a whole row.
- For 100000 nodes that is ten billion cells, so graph problems use adjacency lists instead.
From edge list to adjacency list
An adjacency list stores, for every node, the list of nodes it is joined to. It uses space proportional to the nodes plus the edges and lists neighbours quickly.
Input usually arrives as an edge list, one pair per line. A search needs the neighbours of a node at once, so store a dictionary from each node to the list of its neighbours.
from collections import defaultdict
edges = [(0, 1), (0, 2), (1, 3)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)print(dict(graph))Example 2 · Undirected graph from an edge list
from collections import defaultdict
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)print(dict(graph)){0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}What this code does
- Each pair is added in both directions, so node 3 lists 1, 2 and 4.
- Building takes O(n + m) time for n nodes and m edges.
Example 3 · Neighbours and degree
from collections import defaultdict
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]graph = defaultdict(list)for a, b in edges: graph[a].append(b) graph[b].append(a)for node in sorted(graph): print(node, graph[node], len(graph[node]))0 [1, 2] 2 1 [0, 3] 2 2 [0, 3] 2 3 [1, 2, 4] 3 4 [3] 1
What this code does
- The degree of a node is the length of its list.
- Node 3 has degree 3. The degrees add up to twice the number of edges, 10 here.
defaultdict(list) makes an empty list the first time a key is used, so no "if key not in graph" check is needed. An undirected edge is stored twice, once for each end.
Directed edges and missing keys
A one-way edge goes into one list only. A node that never starts an edge is not a key, and merely reading a missing key from a defaultdict creates it.
from collections import defaultdict
graph = defaultdict(list)for a, b in [(1, 2), (2, 3)]: graph[a].append(b)print(3 in graph)print(graph[3], 3 in graph)Example 4 · Directed graph
from collections import defaultdict
links = [(0, 1), (0, 2), (2, 1), (3, 2)]graph = defaultdict(list)for a, b in links: graph[a].append(b)print(dict(graph))print(graph.get(1, [])){0: [1, 2], 2: [1], 3: [2]}
[]What this code does
- Only the start of each edge gets an entry. Node 1 has no outgoing edges, so it is not a key.
graph.get(1, [])reads it safely and does not add it.
Example 5 · A defaultdict creates keys when read
from collections import defaultdict
graph = defaultdict(list)graph[0].append(1)print(len(graph))print(graph[7])print(len(graph), 7 in graph)1 [] 2 True
What this code does
- Reading
graph[7]stored an empty list under 7, so the dictionary grew from 1 key to 2. - This can quietly change loops such as
for node in graph. Use.getorinwhen you only want to look.
Looping over range(n) visits every node, including those without edges. Use graph.get(node, []) when you want to read without creating a key.
Next step
Check your understanding
10 quick questions