形式陈述

对连通无向带权图 $G=(V,E,w)$，最小生成树（MST）是覆盖全部顶点且总权重 $\sum _{e\in T}w(e)$ 最小的生成树。割性质：对任意尊重当前已选森林的割，跨割的轻边是安全边；环性质：一个环中的严格最重边不属于任何 MST。Kruskal 按边权递增、在不成环时加入边；Prim 从一个顶点出发反复加入跨当前割的轻边。两者都由割性质证明正确。

直觉

用恰好 $|V|-1$ 条边把所有点连起来，并在每次连接两个尚未合并的部分时选择不会牺牲全局最优性的最便宜桥梁。

例子与边界

若所有边权互异，MST 唯一；反过来不成立，含相同权边的图仍可能只有一棵 MST。负权边没有问题，只要比较总和即可。MST 最小化整棵连接网络的边权总和，不保证任意两点之间的树路径是原图最短路；最短路径树也不一定是 MST。图不连通时对应对象是每个分量的最小生成森林。

推论与应用

MST 用于网络布线、聚类、近似算法和图像分割。Kruskal 配合并查集，Prim 配合优先队列，分别适合不同图密度。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 21, minimum spanning trees and cut property。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 4, Kruskal, Prim, and exchange arguments。