最小生成树
最小生成树（MST, Minimum Spanning Tree）
所谓最小生成树，就是一个连通无向带权图的极小连通子图，它包含原图的所有顶点，并且所有边的权值之和尽可能小。
最小生成树需要满足3个条件：
-
是一棵树：树不能有回路，并且个顶点一定有条边。
-
是生成树：包含原图的全部顶点，树的条边都必须在图里，并且如果向生成树中加一条原图中的非树边都一定构成回路。
-
边的权重和最小。
如果最小生成树存在，那么图一定连通，反之亦然。
例如一个带权图，蓝色边可以把所有顶点连接起来，又保证边的权值和最小。
图的最小生成树不是唯一的，同一个图有可能对应多个最小生成树。
最小生成树在现实中有很多用处。假如要在若干个城市之间铺设铁路，而预算又是有限的，那么就需要寻找成本最低的铺设方式。城市之间的交通网就像一个连通图，其实并不需要在每两个城市之间都直接进行连接，只需要一个最小生成树，保证所有的城市都有铁路可以达到即可。
Prim
Prim算法是以图的顶点为基础，从一个初始顶点开始，寻找达到其它顶点权值最小的边，并把该顶点加入到已触达顶点的集合中。当全部顶点都加入到集合时，算法的工作就完成了。Prim算法的本质是基于贪心算法（greedy algorithm）。
Prim算法可以理解为让一棵小树长大，每次找能够向外生长的最小边。
例如使用Prim算法获得一个带权图的最小生成树：
Prim：从已触达集合向外生长
解锁完整互动实验、进阶解析与精选参考答案。
Kruskal
与Prim算法不同，Prim算法是以顶点为关键来获得最小生成树的，而Kruskal算法是以边为关键获得最小生成树的。
Kruskal算法可以理解为将森林合并成树，每次在图中找尚未处理且权值最小的边，只有当它连接两个不同的连通分量时才收录。
例如使用Kruskal算法获得一个带权图的最小生成树：
Kruskal：按边合并森林，拒绝成环
解锁完整互动实验、进阶解析与精选参考答案。
知识测验
知识测验
以最小成本连接四个站点
分别用Prim（从A开始）与Kruskal求最小生成树。每次收录画出已有边；Kruskal还要解释为什么拒绝A—C。给出最终边集、总权重和边数。