All chapters in this track
Chapter 11 of 15
11. Graphs
Key Insight
Every graph problem is one of: reachability (BFS/DFS), shortest path (Dijkstra/Bellman-Ford/BFS for unweighted), connectivity (Union-Find), or ordering (topological sort). Pick the right primitive and the solution follows.
Representations
from collections import defaultdict
# Adjacency list (most common)
graph: dict[int, list[int]] = defaultdict(list)
graph[u].append(v) # directed; add both for undirected
# Weighted adjacency list
wgraph: dict[int, list[tuple[int,int]]] = defaultdict(list)
wgraph[u].append((v, weight))
# Adjacency matrix (dense graphs, small n)
n = 5
adj = [[float("inf")] * n for _ in range(n)]
for i in range(n): adj[i][i] = 0
adj[u][v] = w
# Grid as implicit graph: 4-directional neighbors
DIRS = [(0,1),(0,-1),(1,0),(-1,0)]
def neighbors(r, c, rows, cols):
return [(r+dr, c+dc) for dr,dc in DIRS if 0<=r+dr<rows and 0<=c+dc<cols]
11.1 DFS & BFS Templates
from collections import deque
# --- Iterative DFS ---
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited: continue
visited.add(node)
for nb in graph[node]:
if nb not in visited:
stack.append(nb)
return visited
# --- Recursive DFS ---
def dfs_rec(graph, node, visited=None):
if visited is None: visited = set()
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs_rec(graph, nb, visited)
return visited
# --- BFS (shortest path in unweighted graph) ---
def bfs_shortest(graph, start, end):
if start == end: return 0
visited = {start}
q = deque([(start, 0)])
while q:
node, dist = q.popleft()
for nb in graph[node]:
if nb == end: return dist + 1
if nb not in visited:
visited.add(nb)
q.append((nb, dist + 1))
return -1 # unreachable
# --- Count connected components ---
def count_components(n: int, edges: list[list[int]]) -> int:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v); graph[v].append(u)
visited = set()
count = 0
for node in range(n):
if node not in visited:
dfs(graph, node) # or any traversal
count += 1
return count
11.2 Topological Sort
Use when: DAG ordering, course prerequisites, build dependencies.
# --- Kahn's Algorithm (BFS-based) --- O(V+E)
def topo_sort_kahn(n: int, prereqs: list[list[int]]) -> list[int]:
indegree = [0] * n
graph = defaultdict(list)
for a, b in prereqs: # b must come before a
graph[b].append(a)
indegree[a] += 1
q = deque(node for node in range(n) if indegree[node] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for nb in graph[node]:
indegree[nb] -= 1
if indegree[nb] == 0:
q.append(nb)
return order if len(order) == n else [] # [] if cycle detected
# --- DFS-based topological sort ---
def topo_sort_dfs(n: int, graph) -> list[int]:
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
order = []
has_cycle = [False]
def dfs(u):
if has_cycle[0]: return
color[u] = GRAY
for v in graph[u]:
if color[v] == GRAY:
has_cycle[0] = True; return
if color[v] == WHITE:
dfs(v)
color[u] = BLACK
order.append(u)
for i in range(n):
if color[i] == WHITE:
dfs(i)
return [] if has_cycle[0] else order[::-1]
11.3 Shortest Paths
import heapq
# --- Dijkstra (non-negative weights) --- O((V+E) log V)
def dijkstra(graph, src: int, n: int) -> list[int]:
dist = [float("inf")] * n
dist[src] = 0
heap = [(0, src)] # (distance, node)
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue # stale entry
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
# --- Bellman-Ford (handles negative weights) --- O(VE)
def bellman_ford(n: int, edges: list[tuple], src: int) -> list[float]:
dist = [float("inf")] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Detect negative cycle
for u, v, w in edges:
if dist[u] + w < dist[v]:
return [] # negative cycle exists
return dist
# --- Floyd-Warshall (all-pairs) --- O(V³)
def floyd_warshall(dist: list[list[float]], n: int) -> list[list[float]]:
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# --- 0-1 BFS (edge weights 0 or 1) --- O(V+E)
from collections import deque
def bfs_01(graph, src: int, n: int) -> list[int]:
dist = [float("inf")] * n
dist[src] = 0
dq = deque([src])
while dq:
u = dq.popleft()
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
if w == 0:
dq.appendleft(v) # 0-cost: priority
else:
dq.append(v)
return dist
11.4 Union-Find (Disjoint Set Union)
Use when: dynamic connectivity, cycle detection in undirected graphs, Kruskal's MST.
class UnionFind:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
self.size = [1] * n
self.components = n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x: int, y: int) -> bool:
px, py = self.find(x), self.find(y)
if px == py: return False # already connected
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.components -= 1
return True
def connected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)
def component_size(self, x: int) -> int:
return self.size[self.find(x)]
11.5 Minimum Spanning Tree (Kruskal's)
def kruskal(n: int, edges: list[tuple]) -> int:
"""Returns total weight of MST. edges: [(weight, u, v)]"""
edges.sort()
uf = UnionFind(n)
mst_weight = 0
for w, u, v in edges:
if uf.union(u, v):
mst_weight += w
return mst_weight
11.6 Key CP Patterns
| Problem | Algorithm | Complexity |
|---|---|---|
| Unweighted shortest path | BFS | |
| Weighted shortest path (≥0) | Dijkstra | |
| Negative weights | Bellman-Ford | |
| All-pairs shortest | Floyd-Warshall | |
| 0/1 weights | 0-1 BFS | |
| Dynamic connectivity | Union-Find | |
| MST | Kruskal's / Prim's | |
| Topological order / cycle | Kahn's / DFS coloring | |
| Strongly connected components | Tarjan's / Kosaraju's |