图论算法精讲：最小生成树与最短路径实战

1. 图论专题3：从基础到实战的算法精讲

作为一名参加过多次算法训练营的老兵，我深知图论在算法竞赛和面试中的重要性。代码随想录的图论专题3可以说是整个训练营中最硬核的部分之一，这里不仅有经典算法的深度解析，更有大量来自真实场景的变种题目。今天我就带大家完整拆解这个专题的核心内容，分享我在刷题过程中积累的实战经验。

图论问题之所以让很多人头疼，关键在于它抽象性强、变种多。比如同样的深度优先搜索（DFS），在二叉树和图结构中的实现就有本质区别。专题3聚焦的是图论中最经典的几个问题：最小生成树、最短路径、拓扑排序，以及它们的工程应用场景。我会结合LeetCode和ACM真题，讲解如何从暴力解法一步步优化到最优解。

提示：建议先掌握图的两种表示方法（邻接矩阵和邻接表）以及基础的DFS/BFS遍历，这是理解后续内容的前提条件。

2. 专题核心内容解析

2.1 最小生成树算法对比与实现

最小生成树（MST）是图论中最实用的算法之一，在网络布线、交通规划等领域有广泛应用。专题3重点讲解了两种经典算法：

  1. Kruskal算法- 基于并查集的贪心实现
class UnionFind: def __init__(self, size): self.parent = list(range(size)) def find(self, x): while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] # 路径压缩 x = self.parent[x] return x def union(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX != rootY: self.parent[rootX] = rootY def kruskal(n, edges): uf = UnionFind(n) edges.sort(key=lambda x: x[2]) # 按权重排序 res = 0 for u, v, w in edges: if uf.find(u) != uf.find(v): uf.union(u, v) res += w return res
  1. Prim算法- 基于优先队列的实现
import heapq def prim(n, edges): graph = [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w)) graph[v].append((u, w)) heap = [] visited = [False] * n heapq.heappush(heap, (0, 0)) res = 0 while heap: weight, u = heapq.heappop(heap) if visited[u]: continue visited[u] = True res += weight for v, w in graph[u]: if not visited[v]: heapq.heappush(heap, (w, v)) return res

算法选择指南：

  • 稀疏图（边数E≈顶点数V）：优先选择Kruskal，时间复杂度O(ElogE)
  • 稠密图（E≈V²）：Prim算法更优，使用斐波那契堆可实现O(E+VlogV)

踩坑记录：在实现Kruskal时，忘记初始化并查集的parent数组导致死循环。务必记得每个节点的父节点初始应为自身。

2.2 最短路径算法全家桶

专题3对最短路径算法的讲解非常系统，从单源到多源，从正权到负权都有覆盖：

算法名称适用场景时间复杂度空间复杂度
Dijkstra无负权边的单源最短路径O((V+E)logV)O(V)
Bellman-Ford含负权边的单源最短路径O(VE)O(V)
SPFABellman-Ford的优化版本平均O(E)O(V)
Floyd-Warshall多源最短路径O(V³)O(V²)

Dijkstra的优先级队列实现技巧：

def dijkstra(n, edges, start): graph = [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w)) dist = [float('inf')] * n dist[start] = 0 heap = [(0, start)] while heap: current_dist, u = heapq.heappop(heap) if current_dist > dist[u]: continue # 已经找到更短路径 for v, w in graph[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w heapq.heappush(heap, (dist[v], v)) return dist

常见错误排查：

  1. 负权边使用Dijkstra会导致错误结果
  2. Bellman-Ford检测负权环时，需要额外进行第V次松弛操作
  3. SPFA最坏情况下会退化为O(VE)，遇到刻意构造的数据会超时

2.3 拓扑排序的工程实践

专题3中关于拓扑排序的讲解让我印象最深的是它在实际工程中的应用。除了经典的课程表问题（LeetCode 207），它在编译器的依赖解析、任务调度系统中都有广泛应用。

Kahn算法实现：

def topological_sort(n, edges): in_degree = [0] * n graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) in_degree[v] += 1 queue = [i for i in range(n) if in_degree[i] == 0] result = [] while queue: u = queue.pop(0) result.append(u) for v in graph[u]: in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v) return result if len(result) == n else [] # 存在环则返回空

DFS实现版本：

def topological_sort_dfs(n, edges): graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) visited = [0] * n # 0未访问 1访问中 2已完成 result = [] def dfs(u): if visited[u] == 1: return False # 存在环 if visited[u] == 2: return True visited[u] = 1 for v in graph[u]: if not dfs(v): return False visited[u] = 2 result.append(u) return True for i in range(n): if visited[i] == 0 and not dfs(i): return [] return result[::-1]

工程经验：在微服务启动顺序控制中，我们使用拓扑排序来确定服务依赖关系。曾经因为漏掉了循环依赖检测，导致系统启动死锁，这个教训让我深刻理解了拓扑排序中环检测的重要性。

3. 专题中的经典题目剖析

3.1 最小生成树实战：连接所有点的最小费用

LeetCode 1584是一道典型的MST应用题，要求连接平面上的所有点，使得总费用最小。这道题完美展示了如何将实际问题抽象为图论模型。

解题步骤：

  1. 构建完全图：每个点与其他所有点相连，边权为曼哈顿距离
  2. 应用Prim或Kruskal算法求解MST
  3. 累加所有选中边的权重

优化技巧：

  • 对于Kruskal算法，可以先计算所有可能的边然后排序
  • 对于Prim算法，使用邻接矩阵存储可以简化实现
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((i, j, dist)) edges.sort(key=lambda x: x[2]) uf = UnionFind(n) res = 0 count = 0 for u, v, w in edges: if uf.find(u) != uf.find(v): uf.union(u, v) res += w count += 1 if count == n - 1: break return res

3.2 最短路径变种：受限路径计数

LeetCode 1786是一道最短路径与动态规划结合的题目，要求统计从起点到终点的受限路径数量。这类题目在专题3中被归为"图论与DP结合"的典型。

解题思路：

  1. 使用Dijkstra计算每个节点到终点的最短距离
  2. 按照到终点的距离升序排序所有节点
  3. 使用动态规划统计路径数：dp[u] = sum(dp[v])，其中distanceToLastNode[v] < distanceToLastNode[u]
def countRestrictedPaths(n, edges): graph = [[] for _ in range(n+1)] for u, v, w in edges: graph[u].append((v, w)) graph[v].append((u, w)) # Dijkstra计算到n的最短距离 dist = [float('inf')] * (n+1) dist[n] = 0 heap = [(0, n)] while heap: d, u = heapq.heappop(heap) if d > dist[u]: continue for v, w in graph[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w heapq.heappush(heap, (dist[v], v)) # 动态规划统计路径数 nodes = sorted(range(1, n+1), key=lambda x: dist[x]) dp = [0] * (n+1) dp[1] = 1 for u in nodes: for v, _ in graph[u]: if dist[v] < dist[u]: dp[u] += dp[v] return dp[n] % (10**9 + 7)

3.3 拓扑排序应用：课程表III

LeetCode 630是一道进阶的拓扑排序题目，加入了贪心算法的思想。专题3中这类题目被标记为"必须掌握"的面试高频题。

解题关键：

  1. 按照截止时间升序排序课程
  2. 使用最大堆维护已选课程
  3. 当总时间超过当前课程截止时间时，替换掉持续时间最长的课程
def scheduleCourse(courses): courses.sort(key=lambda x: x[1]) # 按截止时间排序 heap = [] time = 0 for duration, end in courses: if time + duration <= end: heapq.heappush(heap, -duration) time += duration elif heap and -heap[0] > duration: time += duration + heapq.heappop(heap) heapq.heappush(heap, -duration) return len(heap)

4. 图论专题的进阶技巧

4.1 分层图的应用场景

专题3中提到的分层图技巧在处理"有状态"的图论问题时非常有用。比如LeetCode 787"K站中转内最便宜的航班"，就需要使用分层图来记录剩余的转机次数。

实现模板：

def findCheapestPrice(n, flights, src, dst, k): # 构建分层图：dp[i][j]表示经过i次转机到达j的最小费用 dp = [[float('inf')] * n for _ in range(k+2)] dp[0][src] = 0 for i in range(1, k+2): for u, v, w in flights: if dp[i-1][u] != float('inf'): dp[i][v] = min(dp[i][v], dp[i-1][u] + w) res = min(dp[i][dst] for i in range(k+2)) return res if res != float('inf') else -1

4.2 双向BFS优化技巧

对于无权图的最短路径问题，当起点和终点都已知时，双向BFS可以显著提高搜索效率。专题3中特别强调了这种优化方法。

实现对比：

  • 普通BFS：时间复杂度O(b^d)，其中b是分支因子，d是解深度
  • 双向BFS：时间复杂度O(b^(d/2))，空间复杂度也相应降低
def bidirectional_bfs(graph, start, end): if start == end: return 0 # 初始化两个队列和访问记录 queue_start = deque([start]) visited_start = {start: 0} queue_end = deque([end]) visited_end = {end: 0} while queue_start and queue_end: # 从起点方向扩展 for _ in range(len(queue_start)): node = queue_start.popleft() for neighbor in graph[node]: if neighbor in visited_end: return visited_start[node] + 1 + visited_end[neighbor] if neighbor not in visited_start: visited_start[neighbor] = visited_start[node] + 1 queue_start.append(neighbor) # 从终点方向扩展 for _ in range(len(queue_end)): node = queue_end.popleft() for neighbor in graph[node]: if neighbor in visited_start: return visited_end[node] + 1 + visited_start[neighbor] if neighbor not in visited_end: visited_end[neighbor] = visited_end[node] + 1 queue_end.append(neighbor) return -1 # 未连通

4.3 欧拉回路与哈密尔顿回路

专题3中对这两种特殊路径问题做了对比讲解：

特性欧拉回路哈密尔顿回路
定义经过每条边恰好一次经过每个顶点恰好一次
判定条件所有顶点度数为偶数NP完全问题，无通用条件
应用场景邮路问题、DNA测序旅行商问题、路线规划
算法复杂度O(E)O(N!)
经典算法Hierholzer算法回溯法

欧拉回路实现示例：

def find_eulerian_circuit(graph): circuit = [] stack = [next(iter(graph))] while stack: current = stack[-1] if graph[current]: next_node = graph[current].pop() stack.append(next_node) else: circuit.append(stack.pop()) return circuit[::-1]

5. 专题学习建议与避坑指南

5.1 学习路线规划

根据我的刷题经验，建议按以下顺序攻克图论专题：

  1. 掌握图的表示方法（邻接表、邻接矩阵）
  2. 熟练实现DFS/BFS遍历
  3. 学习连通分量相关算法（Union-Find）
  4. 掌握拓扑排序及其应用
  5. 攻克最短路径算法（Dijkstra, Bellman-Ford, Floyd）
  6. 学习最小生成树算法（Prim, Kruskal）
  7. 研究网络流等高级主题

5.2 常见错误与调试技巧

易错点汇总：

  1. 邻接表初始化时忘记处理无向图的双向边
  2. Dijkstra算法中未处理重复节点导致错误
  3. 并查集实现时路径压缩或按秩合并缺失
  4. 拓扑排序中环检测逻辑错误
  5. 边界条件处理不当（空图、单节点图等）

调试建议：

  • 对于复杂算法，先在小规模测试用例上手动模拟
  • 使用可视化工具（如Graphviz）绘制图结构
  • 添加详细的日志输出，跟踪算法执行过程
  • 对特殊输入（如负权边、自环边等）单独测试

5.3 面试准备策略

根据专题3的总结和我的面试经验，图论问题在技术面试中常考以下几类：

  1. 基础遍历应用（岛屿数量、课程表）
  2. 最短路径问题及其变种
  3. 拓扑排序在任务调度中的应用
  4. 并查集解决连通性问题
  5. 贪心算法在图中的应用（如MST）

准备建议：

  • 每个算法至少手写实现3遍
  • 总结同类问题的解题模板
  • 记录错题本，分析错误原因
  • 参加模拟面试，练习白板编码

我在准备面试时，会把每个算法的关键步骤写在便签上贴在墙上，每天早晨花10分钟快速回顾。这种方法对巩固图论算法特别有效，因为图论问题往往有固定的解决模式，记住这些模式能大大提升解题速度。