形式陈述

Prim 算法在连通无向带权图中维护已纳入顶点集合 $S$，每次选择跨越割 $(S,V\setminus S)$ 的最小权边，把其外端点加入。割性质保证该安全边可属于某棵最小生成树。用邻接表和二叉堆维护每个外部顶点连接 $S$ 的最小键，时间 $O(|E|\log |V|)$；稠密图用数组可为 $O(|V{|}^2)$。图不连通时从每个分量重启得到最小生成森林。

直觉

从一个点向外生长，每次用最便宜的边连接一个新点。因为当前树与外界之间总要跨过某条边，割上最轻边不会比任何替代连接更差。

例子与边界

三角形边权 1、2、10 时，从任意点生长都会选权 1 和 2 的两边。相同权重可产生多棵 MST，算法输出取决于平局。Prim 选择的是连接当前树到新顶点的最小边，不是全图未选边中最小且不成环的边；后者是 Kruskal。负权不影响割性质。若堆中保留过期键，弹出时需检查或使用 decrease-key。

推论与应用

Prim 用于网络设计、聚类与几何 MST，展示了割性质如何把局部最小选择提升为全局最优。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。