8.8、最小生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图；若图中顶点数为n，则它的生成树含有\(n-1\)条边。
最小生成树
对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为图G的所有生产树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree，MST）。
注意：
- 最小生成树可能有多个，但边的权值之和总是唯一最小的
- 最小生成树的边数=顶点数 - 1
- 如果一个连通图本身就是一棵树，则其最小生成树就是它本身
- 只有连通图才有生成树，非连通图只有生成森林
Prim算法（普里姆）
从某个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止
Prim算法实现思想：
Kruskal算法（ 克鲁斯卡尔）
每次选择一条权值最小的边，使得这条边的两头连通（原本已经连通的就不选）；直到所有的结点都连通
Kruskal算法实现思想：
时间复杂度
Prim算法（普里姆）时间复杂度：\(O(|V|^2)\)；适用于稠密图
Kruskal算法（克鲁斯卡尔）时间复杂度：\(O(|E|log_2|E|)\)；适用于稀疏图
标签：连通,Prim,Kruskal,最小,生成,算法 From： https://www.cnblogs.com/shuisanya/p/16865736.html