第12章：图算法精选
图是最能体现关系复杂性的数据结构。在 LeetCode 中，图题目往往让人望而生畏，但其实大多数图算法都有固定的模式。本章将从图的基础表示开始，逐步深入到经典的图算法，帮助你建立处理图问题的系统性思维。关键在于识别问题的图结构本质，选择合适的算法框架。
12.1 图的表示：邻接表vs邻接矩阵
核心概念
图的表示方式直接影响算法的实现和效率。选择合适的表示方式，往往能让代码更加简洁。
邻接表：稀疏图的首选
邻接表适合边数远小于 $V^2$ 的稀疏图，空间复杂度为 $O(V + E)$。
图结构示例：
0 --> [1, 2]
1 --> [2, 3]
2 --> [3]
3 --> []
Python 实现模式：
# 使用字典 + 列表
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # 无向图
# 使用字典 + 集合（去重）
graph = defaultdict(set)
for u, v in edges:
graph[u].add(v)
graph[v].add(u)
C++ 实现模式：
vector<vector<int>> graph(n);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]); // 无向图
}
邻接矩阵：稠密图与快速查询
邻接矩阵适合边数接近 $V^2$ 的稠密图，或需要 $O(1)$ 判断边是否存在的场景。
矩阵表示：
0 1 2 3
0 [ 0 1 1 0 ]
1 [ 0 0 1 1 ]
2 [ 0 0 0 1 ]
3 [ 0 0 0 0 ]
实战例题：克隆图 (#133)
克隆图的关键是处理节点的引用关系，避免重复创建：
def cloneGraph(node):
if not node:
return None
visited = {} # 原节点 -> 克隆节点的映射
def dfs(node):
if node in visited:
return visited[node]
# 创建克隆节点
clone = Node(node.val)
visited[node] = clone
# 递归克隆邻居
for neighbor in node.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)
实战例题：最小高度树 (#310)
找到最小高度树的根节点，本质是找图的中心：
def findMinHeightTrees(n, edges):
if n <= 2:
return list(range(n))
# 构建邻接表
graph = [set() for _ in range(n)]
for u, v in edges:
graph[u].add(v)
graph[v].add(u)
# 从叶子节点开始剥离
leaves = [i for i in range(n) if len(graph[i]) == 1]
remaining = n
while remaining > 2:
remaining -= len(leaves)
new_leaves = []
for leaf in leaves:
# 移除叶子节点
neighbor = graph[leaf].pop()
graph[neighbor].remove(leaf)
if len(graph[neighbor]) == 1:
new_leaves.append(neighbor)
leaves = new_leaves
return leaves
关键洞察：树的中心最多有两个节点，通过逐层剥离叶子节点可以找到。
12.2 最短路径：Dijkstra、Bellman-Ford
Dijkstra算法：非负权重的最优选择
Dijkstra算法基于贪心思想，每次选择距离最短的未访问节点进行松弛操作。
算法框架：
def dijkstra(graph, start):
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
# 优先队列：(距离, 节点)
pq = [(0, start)]
while pq:
d, u = heappop(pq)
if d > dist[u]: # 已经有更短路径
continue
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heappush(pq, (dist[v], v))
return dist
实战例题：网络延迟时间 (#743)
def networkDelayTime(times, n, k):
# 构建邻接表
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
# Dijkstra算法
dist = {i: float('inf') for i in range(1, n + 1)}
dist[k] = 0
pq = [(0, k)]
while pq:
d, u = heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heappush(pq, (dist[v], v))
max_dist = max(dist.values())
return max_dist if max_dist < float('inf') else -1
Bellman-Ford算法：处理负权边
Bellman-Ford可以检测负权环，通过 $V-1$ 轮松弛操作保证找到最短路径。
算法框架：
def bellmanFord(edges, n, start):
dist = [float('inf')] * n
dist[start] = 0
# V-1轮松弛
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] != float('inf'):
dist[v] = min(dist[v], dist[u] + w)
# 检测负权环
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # 存在负权环
return dist
实战例题：K站中转内最便宜的航班 (#787)
这题需要限制路径长度，适合用 Bellman-Ford 的变体：
def findCheapestPrice(n, flights, src, dst, k):
# 最多 k+1 条边
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1):
# 复制当前距离数组
new_dist = dist[:]
for u, v, price in flights:
if dist[u] != float('inf'):
new_dist[v] = min(new_dist[v], dist[u] + price)
dist = new_dist
return dist[dst] if dist[dst] != float('inf') else -1
关键技巧：使用临时数组避免在同一轮中使用更新后的值。
12.3 最小生成树：Kruskal、Prim
Kruskal算法：基于边的贪心
Kruskal算法按边权重排序，使用并查集判断是否形成环。
算法框架：
def kruskal(edges, n):
# 并查集
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
parent[px] = py
return True
# 按权重排序
edges.sort(key=lambda x: x[2])
mst_weight = 0
mst_edges = []
for u, v, w in edges:
if union(u, v):
mst_weight += w
mst_edges.append((u, v, w))
if len(mst_edges) == n - 1:
break
return mst_weight, mst_edges
实战例题：连接所有点的最小费用 (#1584)
def minCostConnectPoints(points):
n = len(points)
# 计算所有边的权重（曼哈顿距离）
edges = []
for i in range(n):
for j in range(i + 1, n):
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.append((dist, i, j))
# Kruskal算法
edges.sort()
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
cost = 0
edges_used = 0
for dist, u, v in edges:
pu, pv = find(u), find(v)
if pu != pv:
parent[pu] = pv
cost += dist
edges_used += 1
if edges_used == n - 1:
break
return cost
Prim算法：基于点的贪心
Prim算法从一个点开始，逐步扩展最小生成树。
算法框架：
def prim(graph, n):
visited = [False] * n
min_heap = [(0, 0)] # (权重, 节点)
mst_weight = 0
while min_heap:
weight, u = heappop(min_heap)
if visited[u]:
continue
visited[u] = True
mst_weight += weight
for v, w in graph[u]:
if not visited[v]:
heappush(min_heap, (w, v))
return mst_weight
实战例题：水资源分配优化 (#1168)
这题需要巧妙地将打井成本转化为虚拟节点：
def minCostToSupplyWater(n, wells, pipes):
# 添加虚拟节点0，连接到所有房子
edges = []
# 打井相当于从虚拟节点0连边
for i in range(n):
edges.append((wells[i], 0, i + 1))
# 添加管道
for house1, house2, cost in pipes:
edges.append((cost, house1, house2))
# Kruskal算法
edges.sort()
parent = list(range(n + 2))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
total_cost = 0
edges_used = 0
for cost, u, v in edges:
pu, pv = find(u), find(v)
if pu != pv:
parent[pu] = pv
total_cost += cost
edges_used += 1
if edges_used == n:
break
return total_cost
关键洞察：通过虚拟节点统一处理两种不同的连接方式。
12.4 并查集：连通性与等价类
核心思想
并查集（Union-Find）是处理动态连通性问题的利器。它支持两个核心操作：
- Find：查找元素所属的集合
- Union：合并两个集合
标准实现模板
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]:
self.parent[px] = py
elif self.rank[px] > self.rank[py]:
self.parent[py] = px
else:
self.parent[py] = px
self.rank[px] += 1
self.count -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
时间复杂度分析：
- 路径压缩 + 按秩合并：每次操作接近 $O(\alpha(n))$，其中 $\alpha$ 是反阿克曼函数
- 实际应用中可以认为是 $O(1)$
实战例题：冗余连接 (#684)
找到形成环的最后一条边：
def findRedundantConnection(edges):
n = len(edges)
parent = list(range(n + 1))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
pu, pv = find(u), find(v)
if pu == pv:
# 这条边形成了环
return [u, v]
parent[pu] = pv
return []
关键洞察：树有 $n-1$ 条边，第 $n$ 条边必然形成环。
实战例题：账户合并 (#721)
合并拥有相同邮箱的账户：
def accountsMerge(accounts):
# 邮箱到索引的映射
email_to_id = {}
email_to_name = {}
# 给每个邮箱分配唯一ID
for account in accounts:
name = account[0]
for email in account[1:]:
if email not in email_to_id:
email_to_id[email] = len(email_to_id)
email_to_name[email] = name
# 并查集
uf = UnionFind(len(email_to_id))
# 合并同一账户的邮箱
for account in accounts:
first_email = account[1]
for email in account[2:]:
uf.union(email_to_id[first_email], email_to_id[email])
# 收集结果
id_to_emails = defaultdict(list)
for email, email_id in email_to_id.items():
root_id = uf.find(email_id)
id_to_emails[root_id].append(email)
# 格式化输出
result = []
for emails in id_to_emails.values():
name = email_to_name[emails[0]]
result.append([name] + sorted(emails))
return result
高级技巧：带权并查集
带权并查集可以维护节点到根的关系（如距离、比例等）：
class WeightedUnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.weight = [1.0] * n # 到父节点的权重
def find(self, x):
if self.parent[x] != x:
root = self.find(self.parent[x])
# 路径压缩时更新权重
self.weight[x] *= self.weight[self.parent[x]]
self.parent[x] = root
return self.parent[x]
def union(self, x, y, value):
# x / y = value
px, py = self.find(x), self.find(y)
if px == py:
return
# weight[x] * ? = weight[y] * value
self.parent[px] = py
self.weight[px] = self.weight[y] * value / self.weight[x]
实战例题：除法求值 (#399)
def calcEquation(equations, values, queries):
# 变量到索引的映射
var_to_id = {}
def get_id(var):
if var not in var_to_id:
var_to_id[var] = len(var_to_id)
return var_to_id[var]
# 带权并查集
uf = WeightedUnionFind(len(equations) * 2)
# 建立等式关系
for (a, b), value in zip(equations, values):
id_a, id_b = get_id(a), get_id(b)
uf.union(id_a, id_b, value)
# 处理查询
result = []
for c, d in queries:
if c not in var_to_id or d not in var_to_id:
result.append(-1.0)
continue
id_c, id_d = get_id(c), get_id(d)
if uf.find(id_c) != uf.find(id_d):
result.append(-1.0)
else:
# c / d = weight[c] / weight[d]
uf.find(id_c) # 确保权重更新
uf.find(id_d)
result.append(uf.weight[id_c] / uf.weight[id_d])
return result
本章小结
图算法的核心在于选择合适的数据结构和算法框架：
-
图的表示： - 稀疏图用邻接表（空间 $O(V+E)$） - 稠密图用邻接矩阵（空间 $O(V^2)$） - 根据需求选择列表或集合存储邻居
-
最短路径算法选择： - 非负权重：Dijkstra（$O((V+E)\log V)$） - 有负权重：Bellman-Ford（$O(VE)$） - 限制路径长度：Bellman-Ford变体 - 所有点对：Floyd-Warshall（$O(V^3)$）
-
最小生成树算法选择： - 稀疏图：Kruskal + 并查集（$O(E\log E)$） - 稠密图：Prim + 优先队列（$O(E\log V)$）
-
并查集的应用场景： - 动态连通性判断 - 等价类划分 - 环检测 - 带权关系维护
常见陷阱与错误
1. 图的遍历陷阱
错误：忘记标记访问过的节点导致死循环
# 错误示例
def dfs(graph, node):
for neighbor in graph[node]:
dfs(graph, neighbor) # 可能死循环！
# 正确示例
def dfs(graph, node, visited):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
2. Dijkstra算法陷阱
错误：对负权边使用Dijkstra
# Dijkstra不能处理负权边！
# 如果有负权边，必须使用Bellman-Ford
错误：重复处理已确定最短路径的节点
# 错误：没有跳过已处理的节点
while pq:
d, u = heappop(pq)
for v, w in graph[u]:
# 可能重复处理！
# 正确：检查是否已有更短路径
while pq:
d, u = heappop(pq)
if d > dist[u]: # 关键检查
continue
for v, w in graph[u]:
...
3. 并查集陷阱
错误：忘记路径压缩导致性能退化
# 错误：没有路径压缩
def find(x):
while parent[x] != x:
x = parent[x]
return x
# 正确：带路径压缩
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # 路径压缩
return parent[x]
错误：Union操作后继续使用旧的根节点
# 错误示例
root_a = find(a)
root_b = find(b)
union(a, b)
# root_a和root_b可能已经过时！
# 正确：union后重新find
union(a, b)
root = find(a) # 重新查找
4. 边界条件
错误：空图或单节点图的特殊处理
# 始终检查边界条件
if not edges or n <= 1:
return special_case_result
错误：节点编号从0还是从1开始
# LeetCode题目可能从0或1开始编号
# 仔细阅读题目，必要时做偏移
parent = list(range(n + 1)) # 1-indexed
parent = list(range(n)) # 0-indexed
调试技巧
- 可视化图结构：打印邻接表帮助理解
- 跟踪算法过程：记录每步的距离更新或合并操作
- 验证不变量：检查MST是否恰好n-1条边
- 测试特殊图：完全图、链、星形图、环
记住：图算法的关键是理解问题的图结构本质，然后套用合适的算法模板。大多数图题都是经典算法的直接应用或简单变体。