最小生成树
1概述：
在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。
处理的是无向图。
2求最小生成树的两种算法：
1Kruskal
方法:将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树.(n为顶点数)
1如果题目要求一定要选择某些边，那就是应该提前把这些边的点合并到同一个集合，然后事先求出这些边的长度
模板：
2Prime
Prime算法:
1算法描述：
普利姆算法求最小生成树时候，和边数无关，只和定点的数量相关，所以适合求稠密网的最小生成树，时间复杂度为O（n*n）。
2算法过程：
1.将一个图的顶点分为两部分，一部分是最小生成树中的结点（A集合），另一部分是未处理的结点（B集合）。
2.首先选择一个结点，将这个结点加入A中，然后，对集合A中的顶点遍历，找出A中顶点关联的边权值最小的那个（设为v），将此顶点从B中删除，加入集合A中。
3.递归重复步骤2，直到B集合中的结点为空，结束此过程。
4.A集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤2的结点连接这些顶点，得到的就是这个图的最小生成树。
3算法实现具体过程：
1.将第一个点放入最小生成树的集合中（标记visit[i]=1意思就是最小生成树集合）。
2.初始化lowcost[i]为跟1点相连（仅仅相连）的边的权值（lowcost[i]不是这个点的最小权值！在以后会逐步更新）。
3.枚举n个顶点
4.将找出来的最小权值的边的顶点加入最小生成树的集合中（标记visit[i]=
1），权值想加。
5.更新lowcost[j]集合。
关键步骤：实质就是每在最小生成树集合中加入一个点就需要把这个点与集合外的点比较，不断的寻找两个集合之间最小的边
6.循环上述步骤，指导将全部顶点加入到最小生成树集合为止。
三、Kruskal和Prim对比
1）过程简单对比
Kruskal算法：所有的顶点放那，每次从所有的边中找一条代价最小的；
Prim:算法：在U，（V – U）之间的边，每次找一条代价最小的
2）效率对比
效率上，稠密图 Prim > Kruskal；稀疏图 Kruskal > Prim
Prim适合稠密图，因此通常使用邻接矩阵储存，而Kruskal多用邻接表。
3）空间对比
解决最小生成树题目的时候，要根据给出数据的情况，来决定使用哪种算法，比如：
1）当点少边多的时候，如1000个点500000条边，这样BT的数据，用prim做就要开一个1000 * 1000的二维数组，而用kruskal做只须开一个500000的数组，500000跟1000*1000比较相差一半。
2）当点多边少的时候，如1000000个点2000条边，像这种数据就是为卡内存而存在的，如果用prim做，你想开一个1000000 * 1000000的二维数组，内存绝对爆掉，而用kruskal只须开一个2000的数组就可以了。
次小生成树
step 1. 先用prim求出最小生成树T.
在prim的同时，用一个矩阵max[u][v] 记录 在T中连结任意两点u,v的唯一的
路中权值最大的那条边的权值. (注意这里).
这是很容易做到的，因为prim是每次增加一个结点s, 而设已经标号了的结点
集合为W, 则W中所有的结点到s的路中的最大权值的边就是当前加入的这条边.
step 1 用时 O(V^2).
step 2. 枚举所有不在T中的边uv, 加入边uv则必然替换权为max[u][v]的边。
举例poj 1679