LeetCode Prim 算法题解

LeetCode Prim 算法题解题目描述Prim 算法是一种用于构建最小生成树的贪心算法。与 Kruskal 算法不同Prim 算法从一个顶点开始逐步扩展最小生成树每次选择连接当前生成树和剩余顶点的最小权值边。示例对于以下加权图A --(2)-- B --(4)-- C | | | (1) (3) (1) | | | D --(5)-- E --(2)-- F从顶点 A 开始Prim 算法构建的最小生成树的边包括A-D (1), A-B (2), B-E (3), E-F (2), F-C (1)总权值为 123219。解题思路方法Prim 算法思路Prim 算法的核心思想是从一个顶点开始逐步扩展最小生成树每次选择连接当前生成树和剩余顶点的最小权值边。具体步骤选择一个起始顶点将其加入生成树。初始化一个优先队列用于存储连接当前生成树和剩余顶点的边。从优先队列中取出权值最小的边如果边的目标顶点不在生成树中则将其加入生成树并将与该顶点相关的边加入优先队列。重复步骤 3直到生成树包含所有顶点。复杂度分析时间复杂度O(E log V)其中 V 是顶点数E 是边数。每次优先队列操作的时间复杂度为 O(log V)最多处理 E 条边。空间复杂度O(E V)需要存储图的邻接表和优先队列的信息。代码实现方法Prim 算法import heapq # Prim 算法 def prim(graph, start): # 获取所有顶点 vertices set(graph.keys()) # 已加入生成树的顶点 mst_vertices set([start]) # 生成树的边 mst_edges [] # 总权值 total_weight 0 # 优先队列用于存储边权值起始顶点目标顶点 priority_queue [] # 初始化优先队列将起始顶点的所有边加入 for neighbor, weight in graph[start].items(): heapq.heappush(priority_queue, (weight, start, neighbor)) while priority_queue and len(mst_vertices) len(vertices): # 取出权值最小的边 weight, u, v heapq.heappop(priority_queue) # 如果目标顶点不在生成树中 if v not in mst_vertices: # 将目标顶点加入生成树 mst_vertices.add(v) # 将边加入生成树 mst_edges.append((u, v, weight)) # 更新总权值 total_weight weight # 将目标顶点的所有边加入优先队列 for neighbor, weight in graph[v].items(): if neighbor not in mst_vertices: heapq.heappush(priority_queue, (weight, v, neighbor)) return mst_edges, total_weight # 测试 def test_prim(): # 构建图结构邻接表 graph { A: {B: 2, D: 1}, B: {A: 2, C: 4, E: 3}, C: {B: 4, F: 1}, D: {A: 1, E: 5}, E: {B: 3, D: 5, F: 2}, F: {C: 1, E: 2} } # 测试从 A 出发的最小生成树 print(Minimum Spanning Tree edges:) mst_edges, total_weight prim(graph, A) for u, v, weight in mst_edges: print(f{u} - {v}: {weight}) print(fTotal weight: {total_weight}) # 输出 # Minimum Spanning Tree edges: # A - D: 1 # A - B: 2 # B - E: 3 # E - F: 2 # F - C: 1 # Total weight: 9 if __name__ __main__: test_prim()测试用例测试用例最小生成树输入A --(2)-- B --(4)-- C | | | (1) (3) (1) | | | D --(5)-- E --(2)-- F输出Minimum Spanning Tree edges: A - D: 1 A - B: 2 B - E: 3 E - F: 2 F - C: 1 Total weight: 9总结Prim 算法是一种重要的图论算法它可以用于构建最小生成树。通过贪心策略和优先队列Prim 算法可以高效地找到权值之和最小的生成树。Prim 算法的核心思想是从一个顶点开始逐步扩展最小生成树每次选择连接当前生成树和剩余顶点的最小权值边。掌握 Prim 算法的原理和实现对于理解和解决图论相关问题非常重要。