Kruskal算法
1.初始时所有节点属于孤立的集合。
2.按照边权递增顺序遍历所有的边，若遍历到的边两个顶点属于不同的集合（该边即为连通这两个集合的边中权值最小的边）则确定该边为最小生成树上的一条边，并将这两个顶点分属的集合合并.
3.遍历完所有边后，原图上所有节点属于同一个集合则被选取的边和原图中所有节点构成最小生成树；否则原图不联通，最小生成树不存在.
在这个算法中用到了并查集的思想，下面介绍一下并查集的代码。
并查集
int findRoot(int x)//并查集寻找根节点
{
if(Tree[x]==-1)
return x;
else
{
int temp=findRoot(Tree[x]);
Tree[x]=temp;
return temp;
}
}
并查集的题目有很多，浙江大学的畅通工程系列基本都是这个，这里就不再赘述了，下面看最小生成树的题目
在迪克·范·戴克节目的一集中，小里奇把他爸爸背上的雀斑连接起来，形成了一张自由钟的照片。
唉，其中一个雀斑原来是一个疤痕，所以他和雷普利的订婚就这样结束了。
把迪克的背想象成一架在不同地点有雀斑的飞机。你的工作是告诉里奇如何连接点，以尽量减少墨水使用量
。里奇通过在两条线之间画直线来连接圆点，
可能在两条线之间提起笔。当Richie完成后，必须有一系列从雀斑到其他雀斑的连接线。
第一行包含0<n<=100，迪克背上的雀斑数量。对于每个雀斑，后面都有一行；
下面的每一行包含两个实数，指示雀斑的（x，y）坐标。
您的程序将一个实数打印到两个小数位：可以连接所有雀斑的墨线的最小总长度。
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int Tree[101];
int findRoot(int x)//并查集寻找根节点
{
if(Tree[x]==-1)
return x;
else
{
int temp=findRoot(Tree[x]);
Tree[x]=temp;
return temp;
}
}
struct Edge
{
int a,b;
double cost;
bool operator <(const Edge&A)const
{
return cost<A.cost;
}
}edge[6000];
struct Point
{
double x,y;
double getDistance(Point A)
{
double temp=(x-A.x)*(x-A.x)+(y-A.y)*(y-A.y);
return sqrt(temp);
}
}list[101];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&list[i].x,&list[i].y);
}
int size=0;
//所有的边数
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
edge[size].a=i;
edge[size].b=j;
edge[size].cost=list[i].getDistance(list[j]);
size++;
}
}
//按边的权值升序排列
sort(edge,edge+size);
for(int i=1;i<=n;i++)
Tree[i]=-1;
double ans=0;
//建立最小生成树
for(int i=0;i<size;i++)
{
int a=findRoot(edge[i].a);
int b=findRoot(edge[i].b);
if(a!=b)
{
Tree[a]=b;
ans=ans+edge[i].cost;
}
}
printf("%.2lf\n",ans);
}
return 0;
}
但行好事，莫问前程
