什么是Prim算法Prim算法是一种用于寻找图中最小生成树（Minimum Spanning Tree, MST）的贪心算法。它由Viktor Y. Prim在1957年提出，广泛应用于网络设计、电路优化等领域。该算法的核心想法是通过逐步扩展已选节点集合，找到连接所有节点且总权重最小的边。
一、Prim算法概述
| 项目 | 内容 |
| 中文名称 | 普里姆算法 |
| 英文名称 | Prim’s Algorithm |
| 提出时刻 | 1957年 |
| 提出者 | Viktor Y. Prim |
| 应用场景 | 最小生成树、网络设计、路径规划等 |
| 算法类型 | 贪心算法 |
| 输入 | 带权无向图 |
| 输出 | 最小生成树（MST） |
二、Prim算法原理
Prim算法的基本步骤如下：
1. 初始化：选择一个起始节点，将其加入已选集合。
2. 循环扩展：从当前已选集合出发，查找与未选节点相连的最短边。
3. 更新集合：将新找到的节点加入已选集合，并将对应的边加入最小生成树。
4. 终止条件：当所有节点都被包含在已选集合中时，算法结束。
该算法的关键在于维护一个“已选节点”和“未选节点”的划分，并不断选择连接两部分的最短边。
三、Prim算法特点
| 特点 | 描述 |
| 贪心策略 | 每一步都选择当前最优的边，以保证整体最优 |
| 时刻复杂度 | O(E log V) 或 O(V2)，取决于实现方式 |
| 适用性 | 适用于稠密图和稀疏图 |
| 非负权值要求 | 图中的边权值必须为非负数 |
| 唯一性 | 若存在多条相同权重的边，结局可能不唯一 |
四、Prim算法与Kruskal算法对比
| 对比项 | Prim算法 | Kruskal算法 |
| 核心想法 | 从单个节点出发，逐步扩展 | 从所有边中选择最小的边，逐步构建 |
| 数据结构 | 邻接矩阵或优先队列 | 边列表 + 并查集 |
| 适合场景 | 稠密图 | 稀疏图 |
| 处理方式 | 逐个节点扩展 | 逐条边筛选 |
| 实现难度 | 相对复杂 | 相对简单 |
五、拓展资料
Prim算法是一种高效且实用的求解最小生成树的算法，尤其适合处理带权无向图的难题。它通过贪心策略逐步构建生成树，确保每一步都选择当前最优的边，从而最终得到全局最优解。虽然其具体实现可能因数据结构不同而有所差异，但其核心想法始终不变。在实际应用中，根据图的密度选择合适的算法可以显著提升效率。
