> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/10.-graph/introduction/zui-xiao-sheng-cheng-shu-minimum-spanning-tree-suan-fa.md).
# 最小生成树（Minimum Spanning Tree）算法
图论中知名度比较高的算法应该就是 [Dijkstra 最短路径算法](https://labuladong.github.io/algo/2/19/41/)， [环检测和拓扑排序](https://labuladong.github.io/algo/2/19/35/)， [二分图判定算法](https://labuladong.github.io/algo/2/19/36/) 以及今天要讲的最小生成树（**Minimum Spanning Tree**）算法了。
最小生成树算法主要有 Prim 算法（普里姆算法）和 Kruskal 算法（克鲁斯卡尔算法）两种，这两种算法虽然都运用了贪心思想，但从实现上来说差异还是蛮大。
### 什么是最小生成树
**先说「树」和「图」的根本区别：树不会包含环，图可以包含环**。
如果一幅图没有环，完全可以拉伸成一棵树的模样。说的专业一点，树就是「无环连通图」。
那么什么是图的「生成树」呢，其实按字面意思也好理解，就是在图中找一棵包含图中的所有节点的树。专业点说，**生成树是含有图中所有顶点的「无环连通子图**」。
容易想到，一幅图可以有很多不同的生成树，比如下面这幅图，红色的边就组成了两棵不同的生成树：
[](https://labuladong.github.io/algo/images/kruskal/1.png)
对于加权图，每条边都有权重，所以每棵生成树都有一个权重和。比如上图，右侧生成树的权重和显然比左侧生成树的权重和要小。
**那么最小生成树很好理解了，所有可能的生成树中，权重和最小的那棵生成树就叫「最小生成树」**。
> PS：一般来说，我们都是在**无向加权图**中计算最小生成树的，所以使用最小生成树算法的现实场景中，图的边权重一般代表成本、距离这样的标量。