简介：最小生成树算法一共有两种，分别是kruskal算法和prim算法。也属于贪心算法，它的目的就是给定无向图、权值以及顶点，求联通所有边的权值和最小。
kruskal算法：
先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。
这个算法实现就是先利用快排把从小到大排序，贪心算法取最优边，然后利用并查集判断两边是否已经在一个集合中。
核心代码：
for(i=1;i<=m;i++)//开始从小到大枚举每一条边 { if(merge(e[i].u,e[i].v))//利用并查集判断两个边是否已经在一个集合中 { count++; sum=sum+e[i].w; } if(count==n-1)//到n-1条边后退出循环 break; }
prim算法：
算法流程：
1、从任意一个顶点构造生成树，然后用book[]数组记录标记的点。
2、用dis[]数组记录生成树到各个顶点的距离
3、从dis[]数组中选出离生成树最近的顶点加入生成树中，如果dis[k]>e[j][k]，则重新更新dis[k]。
4、重复第三步，直到count==n.
核心代码：
book[1]=1;//将1号顶点加入生成树 count++; while(count<n) { min=inf; for(i=1;i<=n;i++) { if(book[i]==0&&dis[i]<min) { min=dis[i]; j=i; } } book[j]=1; count++; sum+=dis[j]; for(k=1;k<=n;k++)//扫描当前j所在的顶点，再以j为中间点，更新生成树到每一个非树顶点的位置 { if(book[k]==0&&dis[k]>e[j][k]) dis[k]=e[j][k]; } }
