Graph Adjacency List in Python
An adjacency list represents a graph as 'for each node, the nodes it connects to'. In Python the right shape is `defaultdict(list)`: insertion is one line, traversal is one nested loop, and you do not pay for the V*V matrix. This entry covers building the list, walking it with DFS, and the directed vs undirected detail that bites every newcomer.
736 views
9
from collections import defaultdict
def build_graph(edges, *, directed=False):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u)
return graph
edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
undirected = build_graph(edges)
for node in sorted(undirected):
print(node, '->', sorted(undirected[node]))
# 1 -> [2, 3]
# 2 -> [1, 4]
# 3 -> [1, 4]
# 4 -> [2, 3, 5]
# 5 -> [4]
directed = build_graph(edges, directed=True)
print()
for node in sorted(directed):
print(node, '->', directed[node])
# 1 -> [2, 3]
# 2 -> [4]
# 3 -> [4]
# 4 -> [5]defaultdict(list) removes the boilerplate of 'check if the key exists, create an empty list if not, then append'. For undirected graphs, every edge (u, v) is added twice (u -> v and v -> u) so both endpoints can find each other. The directed=True switch flips that off. The space cost is O(V + E), not O(V^2) like an adjacency matrix, which is why adjacency lists are the default representation for sparse graphs. Sorting the neighbor lists is purely for readable output; in production you keep insertion order so traversal is deterministic.
from collections import defaultdict
def build_weighted(edges, *, directed=False):
"""edges = list of (u, v, weight) tuples."""
graph = defaultdict(list)
for u, v, w in edges:
graph[u].append((v, w))
if not directed:
graph[v].append((u, w))
return graph
edges = [
('A', 'B', 4),
('A', 'C', 1),
('B', 'C', 2),
('B', 'D', 5),
('C', 'D', 8),
('A', 'B', 7), # parallel edge: another A-B with a different weight
]
graph = build_weighted(edges)
for node in sorted(graph):
for nbr, w in graph[node]:
print(f'{node} --{w}-- {nbr}')
print('total edges (each direction counted):',
sum(len(adj) for adj in graph.values()))For weighted graphs the neighbor list holds tuples of (neighbor, weight) instead of bare neighbors. Adjacency lists naturally handle parallel edges: just append both, and the consumer (Dijkstra, Bellman-Ford, MST) can use whichever weight wins for its question. The same shape extends to multi-attribute edges ((neighbor, weight, capacity, edge_id)) by widening the tuple. If you ever find yourself fighting the data structure, switch to a dict-of-dicts (graph[u][v] = weight) for O(1) lookup of a specific edge, at the cost of losing parallel edges.
from collections import defaultdict
def build_graph(edges, *, directed=False):
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
if not directed:
g[v].append(u)
return g
def dfs(graph, start):
"""Pre-order DFS. Returns the visit order."""
visited = set()
order = []
def visit(node):
if node in visited:
return
visited.add(node)
order.append(node)
for nbr in graph[node]:
visit(nbr)
visit(start)
return order
edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
g = build_graph(edges)
print(dfs(g, 1)) # e.g. [1, 2, 4, 3, 5]
# Disconnected components: run DFS from every unvisited node.
edges2 = [(1, 2), (3, 4)]
g2 = build_graph(edges2)
components = []
seen = set()
for node in g2:
if node not in seen:
comp = dfs(g2, node)
seen.update(comp)
components.append(comp)
print(components) # [[1, 2], [3, 4]]Recursive DFS is the most natural traversal once you have an adjacency list: visit the node, mark it seen, recurse into every unseen neighbor. The visited set is mandatory; without it the function loops forever on any cycle. To handle disconnected graphs, restart DFS from every unvisited node and record the components separately. Recursion is fine up to a few thousand nodes; for deep graphs use the iterative-stack version (covered in the DFS-templates entry) to avoid RecursionError.