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

1. 图论专题3从基础到实战的算法精讲作为一名参加过多次算法训练营的老兵我深知图论在算法竞赛和面试中的重要性。代码随想录的图论专题3可以说是整个训练营中最硬核的部分之一这里不仅有经典算法的深度解析更有大量来自真实场景的变种题目。今天我就带大家完整拆解这个专题的核心内容分享我在刷题过程中积累的实战经验。图论问题之所以让很多人头疼关键在于它抽象性强、变种多。比如同样的深度优先搜索DFS在二叉树和图结构中的实现就有本质区别。专题3聚焦的是图论中最经典的几个问题最小生成树、最短路径、拓扑排序以及它们的工程应用场景。我会结合LeetCode和ACM真题讲解如何从暴力解法一步步优化到最优解。提示建议先掌握图的两种表示方法邻接矩阵和邻接表以及基础的DFS/BFS遍历这是理解后续内容的前提条件。2. 专题核心内容解析2.1 最小生成树算法对比与实现最小生成树MST是图论中最实用的算法之一在网络布线、交通规划等领域有广泛应用。专题3重点讲解了两种经典算法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(keylambda 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 resPrim算法- 基于优先队列的实现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(EVlogV)踩坑记录在实现Kruskal时忘记初始化并查集的parent数组导致死循环。务必记得每个节点的父节点初始应为自身。2.2 最短路径算法全家桶专题3对最短路径算法的讲解非常系统从单源到多源从正权到负权都有覆盖算法名称适用场景时间复杂度空间复杂度Dijkstra无负权边的单源最短路径O((VE)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常见错误排查负权边使用Dijkstra会导致错误结果Bellman-Ford检测负权环时需要额外进行第V次松弛操作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应用题要求连接平面上的所有点使得总费用最小。这道题完美展示了如何将实际问题抽象为图论模型。解题步骤构建完全图每个点与其他所有点相连边权为曼哈顿距离应用Prim或Kruskal算法求解MST累加所有选中边的权重优化技巧对于Kruskal算法可以先计算所有可能的边然后排序对于Prim算法使用邻接矩阵存储可以简化实现def minCostConnectPoints(points): n len(points) edges [] for i in range(n): for j in range(i1, n): dist abs(points[i][0]-points[j][0]) abs(points[i][1]-points[j][1]) edges.append((i, j, dist)) edges.sort(keylambda 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 res3.2 最短路径变种受限路径计数LeetCode 1786是一道最短路径与动态规划结合的题目要求统计从起点到终点的受限路径数量。这类题目在专题3中被归为图论与DP结合的典型。解题思路使用Dijkstra计算每个节点到终点的最短距离按照到终点的距离升序排序所有节点使用动态规划统计路径数dp[u] sum(dp[v])其中distanceToLastNode[v] distanceToLastNode[u]def countRestrictedPaths(n, edges): graph [[] for _ in range(n1)] for u, v, w in edges: graph[u].append((v, w)) graph[v].append((u, w)) # Dijkstra计算到n的最短距离 dist [float(inf)] * (n1) 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, n1), keylambda x: dist[x]) dp [0] * (n1) 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 拓扑排序应用课程表IIILeetCode 630是一道进阶的拓扑排序题目加入了贪心算法的思想。专题3中这类题目被标记为必须掌握的面试高频题。解题关键按照截止时间升序排序课程使用最大堆维护已选课程当总时间超过当前课程截止时间时替换掉持续时间最长的课程def scheduleCourse(courses): courses.sort(keylambda 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 787K站中转内最便宜的航班就需要使用分层图来记录剩余的转机次数。实现模板def findCheapestPrice(n, flights, src, dst, k): # 构建分层图dp[i][j]表示经过i次转机到达j的最小费用 dp [[float(inf)] * n for _ in range(k2)] dp[0][src] 0 for i in range(1, k2): 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(k2)) return res if res ! float(inf) else -14.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 学习路线规划根据我的刷题经验建议按以下顺序攻克图论专题掌握图的表示方法邻接表、邻接矩阵熟练实现DFS/BFS遍历学习连通分量相关算法Union-Find掌握拓扑排序及其应用攻克最短路径算法Dijkstra, Bellman-Ford, Floyd学习最小生成树算法Prim, Kruskal研究网络流等高级主题5.2 常见错误与调试技巧易错点汇总邻接表初始化时忘记处理无向图的双向边Dijkstra算法中未处理重复节点导致错误并查集实现时路径压缩或按秩合并缺失拓扑排序中环检测逻辑错误边界条件处理不当空图、单节点图等调试建议对于复杂算法先在小规模测试用例上手动模拟使用可视化工具如Graphviz绘制图结构添加详细的日志输出跟踪算法执行过程对特殊输入如负权边、自环边等单独测试5.3 面试准备策略根据专题3的总结和我的面试经验图论问题在技术面试中常考以下几类基础遍历应用岛屿数量、课程表最短路径问题及其变种拓扑排序在任务调度中的应用并查集解决连通性问题贪心算法在图中的应用如MST准备建议每个算法至少手写实现3遍总结同类问题的解题模板记录错题本分析错误原因参加模拟面试练习白板编码我在准备面试时会把每个算法的关键步骤写在便签上贴在墙上每天早晨花10分钟快速回顾。这种方法对巩固图论算法特别有效因为图论问题往往有固定的解决模式记住这些模式能大大提升解题速度。