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)，总权值为 1+2+3+2+1=9。

解题思路

方法：Prim 算法

思路：

• Prim 算法的核心思想是从一个顶点开始，逐步扩展最小生成树，每次选择连接当前生成树和剩余顶点的最小权值边。
• 具体步骤：
  1. 选择一个起始顶点，将其加入生成树。
  2. 初始化一个优先队列，用于存储连接当前生成树和剩余顶点的边。
  3. 从优先队列中取出权值最小的边，如果边的目标顶点不在生成树中，则将其加入生成树，并将与该顶点相关的边加入优先队列。
  4. 重复步骤 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(f"Total 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 算法的原理和实现，对于理解和解决图论相关问题非常重要。