1. 简介
在本篇文章中，我们将围绕无向图，使用 Prim 算法提取其最小生成树（Minimum Spanning Tree, MST）。Prim 算法是图论中的经典算法之一，在计算机科学中具有重要地位。常见的图论算法还包括 Dijkstra 最短路径算法、Kruskal 算法、以及各类图搜索算法。
2. 核心概念
在计算机科学中，很多问题都可以用图来建模。图由节点（也称为顶点或点）和连接这些节点的边（也称为链接或线）组成。
如果图中的边没有方向，我们称之为无向图。无向图的一个典型应用场景是计算机网络。
但图的应用远不止于此。它们广泛出现在语言学与自然语言处理、物流、几何、神经科学、社会学、化学等多个领域。例如：
- 分子结构可以用图来表示
- 几何图形可以用图建模
- 单词之间的关系可以用图表达
- 货物运输路线可以用图描述
因此，图领域中存在大量被数学家和计算机科学家深入研究的经典问题。
其中一个典型问题就是：如何找到连接所有节点且总权重最小的子图。这个子图被称为最小生成树（MST）。
Prim 算法是解决这个问题的常用方法之一。它是一种贪心算法，即每一步都选择当前最优解，以期最终得到全局最优解。
3. 算法实现
Prim 算法的实现可以分为以下几个主要步骤：
- 从图中任意选取一个起始节点作为生成树的起点。
- 遍历所有连接当前生成树节点的边，选择权重最小的那条边，将对应的新节点加入到生成树中。
- 重复第 2 步，直到所有节点都被包含进生成树中。
✅ 本质上，Prim 算法是“贪心”的，因为它每一步都选择当前看来最优的边。
下面是该算法的伪代码实现：
algorithm PrimsAlgorithm(G):
// INPUT
// G(E,V) = the initial graph
// OUTPUT
// F = minimal spanning tree
F <- make a tree with a random node as the root
Q <- the queue with all the nodes not in the current tree F
while Q is not empty:
// For each vertex in Q, find the vertex with the minimum cost C(vertex) to F
for vertex in Q:
Find the vertex having minimum cost C(vertex) to F
Find the connecting edge E(F, vertex) giving the minimum cost C(vertex)
Add this vertex to F and remove it from Q
Add the connecting edge E(F, vertex) to F
return F
该算法的执行过程可以通过以下动画直观理解：
4. 时间复杂度分析
Prim 算法的时间复杂度取决于你使用的数据结构：
| 数据结构组合 | 时间复杂度 |
|---|---|
| 二叉堆 + 邻接表 | O(E * log V) |
| 斐波那契堆 + 邻接表 | O(E + V * log V) |
| 邻接矩阵 | O(V^2) |
⚠️ 通常情况下，如果图是稠密图（边数接近于节点数平方），使用邻接矩阵实现更高效；而稀疏图（边数远小于节点数平方）则更适合使用堆结构优化。
5. 小结
本文我们介绍了 Prim 算法的基本思想、实现步骤及其时间复杂度分析。Prim 是一种贪心算法，用于求解无向图的最小生成树问题，广泛应用于网络设计、路径优化等多个领域。
✅ 与其他 MST 算法（如 Kruskal）相比，Prim 更适合稠密图，并且可以通过不同数据结构优化性能。
❌ 但需要注意的是，Prim 仅适用于无向图，且实现相对复杂，尤其在使用堆结构时需要额外维护节点权重信息。
如果你在实际项目中遇到需要构建最小生成树的问题，Prim 是一个值得考虑的算法选择。