图论算法模板
图论原理与复杂度证明见 图论算法详解。本文是背模板速查手册：六张可直接套用的模板，配合适用场景与选型决策，面试现场「识别题型 → 背模板 → 改条件」。
一、图遍历模板：DFS / BFS
邻接表构建（通用第一步）
from collections import defaultdict, deque
def build_graph(edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # 无向图加反向；有向图去掉这行
return graph
DFS 模板（递归 + visited）
def dfs_template(graph, start, n):
visited = [False] * n
def dfs(node):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(neighbor)
dfs(start)
BFS 模板（队列，求最短步数/层数）
def bfs_template(graph, start, n):
visited = [False] * n
queue = deque([start])
visited[start] = True
dist = 0
while queue:
for _ in range(len(queue)): # 按层处理
node = queue.popleft()
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
dist += 1
return dist
网格图套路（岛屿问题 LC 200）
网格图也是一种图：每个格子有 4 个邻居（上下左右），用方向数组遍历。
void dfs(int[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length
|| grid[r][c] == '0') return;
grid[r][c] = '0'; // 原地标记，省 visited
int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) dfs(grid, r + dr[i], c + dc[i]);
}
选型：求最短路径/层数用 BFS（无权图）；求连通分量/路径存在性/回溯用 DFS；网格题默认 DFS + 原地标记。
二、Dijkstra 模板（堆优化）
单源最短路径，无负权边时最优。
import heapq
def dijkstra(graph, start, n):
dist = [float('inf')] * n
dist[start] = 0
heap = [(0, start)] # (当前距离, 节点)
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]: # 过期记录，跳过
continue
for neighbor, weight in graph[node]:
nd = d + weight
if nd < dist[neighbor]:
dist[neighbor] = nd
heapq.heappush(heap, (nd, neighbor))
return dist
复杂度：O((V + E) log V)。
高频变体：
- 网格 Dijkstra（LC 743 网络延迟、LC 1514 概率路径）：把网格格点当作节点，代价换成边权/概率。
- 多源 Dijkstra：初始时把多个源点一起入堆，求「离所有源点的最近距离」（LC 542 01 矩阵）。
- 方案数：额外维护
ways[node]，当nd == dist[neighbor]时累加。
注意事项：Dijkstra 不支持负权边——有负权用 Bellman-Ford/SPFA；若担心堆中大量过期记录，加 d > dist[node] 跳过即可。
三、拓扑排序模板（Kahn + 判环）
拓扑排序针对有向无环图（DAG），按入度从 0 的节点开始逐层剥离。
def topo_sort(num_nodes, edges):
graph = defaultdict(list)
in_degree = [0] * num_nodes
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque([i for i in range(num_nodes) if in_degree[i] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# 有环则长度 < num_nodes
return order if len(order) == num_nodes else []
复杂度：O(V + E)。
适用场景：课程表（LC 207/210）、编译依赖、任务调度、字典序排序（LC 269 外星词典——先把字符关系建成边再做拓扑）。
判环技巧：拓扑完成后检查 len(order) != num_nodes 即有环；DFS 版用三色标记（0 未访问/1 访问中/2 已访问），遇到 1 即有环。
四、并查集模板（路径压缩 + 按秩合并）
并查集解决动态连通性：合并、查是否连通、统计连通分量数。
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = n # 连通分量数
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路径压缩
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]: # 按秩合并
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.count -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
均摊复杂度：O(α(N))，几乎常数。
适用场景：
- 判连通分量（LC 200 岛屿、LC 547 省份数量）。
- 冗余连接（LC 684）：加入的边若已连通则成环。
- 账户合并（LC 721）、Kruskal 最小生成树。
注意事项：涉及坐标的二维网格可把 (r, c) 映射为 r * cols + c 的一维下标。
五、最小生成树模板
Kruskal（按边排序，配并查集，适合稀疏图）
def kruskal(edges, n):
uf = UnionFind(n)
edges.sort(key=lambda x: x[2]) # 按边权升序
mst, total = [], 0
for u, v, w in edges:
if uf.union(u, v): # 不成环才选
mst.append((u, v, w))
total += w
if len(mst) == n - 1:
break
return mst, total
Prim（从点出发 + 堆，适合稠密图）
def prim(graph, n, start=0):
visited = [False] * n
visited[start] = True
heap = [(w, start, v) for v, w in graph[start]]
heapq.heapify(heap)
mst, total = [], 0
while heap and len(mst) < n - 1:
w, u, v = heapq.heappop(heap)
if visited[v]:
continue
visited[v] = True
mst.append((u, v, w))
total += w
for nxt, nw in graph[v]:
if not visited[nxt]:
heapq.heappush(heap, (nw, v, nxt))
return mst, total
复杂度：Kruskal O(E log E)，Prim O((V + E) log V)。
选型：稀疏图（E ≈ V）用 Kruskal；稠密图（E ≈ V²）用 Prim 邻接矩阵版 O(V²)；边已经有序时 Kruskal 天然占优。
六、图算法选型速查
| 问题类型 | 算法 | 复杂度 |
|---|---|---|
| 遍历 / 连通分量 | DFS / BFS | O(V + E) |
| 无权图最短步数 | BFS | O(V + E) |
| 单源最短（无负权） | Dijkstra | O((V + E) log V) |
| 单源最短（有负权） | Bellman-Ford / SPFA | O(V·E) |
| 全源最短 | Floyd-Warshall | O(V³) |
| 拓扑排序 / 判环 | Kahn / DFS 三色 | O(V + E) |
| 动态连通性 | 并查集 | O(α(N)) |
| 最小生成树 | Kruskal / Prim | O(E log E) / O((V+E) log V) |
七、常见问题
Q: 面试时图题的「一上来先做什么」？
先问三点：有向还是无向？加权还是无权？稀疏还是稠密？回答后立刻决定邻接表/矩阵与算法，边说边建图。
Q: DFS 与 BFS 怎么快速取舍？
要求最短路/最少步数 → BFS；递归回溯、路径列举 → DFS；只求连通性 → 两者都行，DFS 写起来短。
Q: 并查集的路径压缩和按秩合并都要吗？
路径压缩必须（否则可能退化成链）；按秩合并是额外保险。面试写全加分，忘掉按秩合并不影响正确性。
Q: 模板直接背下来，遇到变体怎么改？
模板是骨架，变体改三处：图的构建（边/网格/隐式图）、状态定义（距离/概率/路径数）、合并条件（如 Kruskal 的边权阈值）。
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。