最小生成树 - 定义¶
提示
这里是最小生成树的定义，如果您想要学习最小生成树的算法，请转到下面的 Kruskal 或 Prim 算法。
对于一个连通图，如果有一个子图（点集相同，边集被包含）满足树形结构，那么这个子图就是这个图的一棵生成树(1)。生成树的大小定义为所有边的权值之和，最小生成树就是所有生成树的权值之和当中最小的那一棵树。
- 英文名为 Spanning Tree。最小生成树的英文名为 Minimum Spanning Tree，简称 MST。
如果这个图不联通，那么我们可以对每一个联通块（强连通分量）分别求出最小生成树之后合并成一个最小生成森林。