数据结构(6.4_1)——最小生成树
生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图(边要尽可能的少，但要保持连通)
若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
最小生成树(最小代价树)
对于一个带权连通无向图G=(V,E),生成树不同，每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则称T为G的最小生成树(Minimum-Spanning-Tree，MST)
- 最小生成树可能有多个，但边的权值之和总是唯一且最小的
- 最小生成树的边数=顶点数-1。砍掉一条则不连通，增加一条边则会出现回路
- 如果一个连通图本身就是一棵树，则其最小生成树就是它本身
- 只有连通图才有生成树，非连通图只有生成森林
例：
修路问题：
普通方案：
Prim算法(普里姆)
从某一个顶点开始构建生成树；
每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
注：同一个图可能会有不同的最小生成树
Kruskal算法（克鲁斯卡尔）
每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选），直到所有顶点连通
两种算法的对比
Prim算法的实现思想
1、
2、
3、
4、
5、
6、
总：
Kruskal算法的实现思想
1、
2、
3、
4、
5、
6、
7、
总：
总结
