最小生成树Minimum spanning tree
在无向连通图中，用总边权最小的 V−1 条边连接所有顶点。Kruskal 按边合并分量，Prim 从一个顶点逐步扩展树。
怎样选择#
- V 为顶点数，E 为边数。边权可以为负，也可以重复；不连通图的对应目标是最小生成森林。
- 最小生成树优化所选边的总权重，并不保证树中任意两点之间的路径最短。
- 输入已经是边列表时，Kruskal 的排序与并查集组合直接；邻接矩阵上的稠密图可考虑 O(V²) 的 Prim。
算法对照#
| 具体算法 | 问题与前提 | 时间复杂度 | 辅助空间 | 选择与取舍 |
|---|---|---|---|---|
| Kruskal | 无向加权图；按边权全局处理 | ，另计 初始化 | ，包括排序所需的边副本 | 排序后用并查集跳过成环边；容易得到各连通分量的最小生成森林。 |
| Prim | 无向加权图；从树与树外的割扩展 | 索引二叉堆 ；矩阵 | 索引堆版 ，不含输入图 | 每个树外顶点只维护到当前树的最轻连接；不连通时需对各分量重新启动。 |
左右滑动查看完整对照。点击算法名称，查看原理、约束和实现。