15、最小生成树之kruskal算法

　　最小生成树两个重要的算法：Prim 和 Kruskal。

　　Prim：时间复杂度O(n^2)，适用于边稠密的网络。

　　Kruskal：时间复杂度为O(e*log(e))，适用于边稀疏的网络。

　　kruskal算法的时间复杂度主要由排序方法决定，其排序算法只与带权边的个数有关，与图中顶点的个数无关，当使用时间复杂度为O(eloge)的排序算法时，克鲁斯卡算法的时间复杂度即为O(eloge)，因此当带权图的顶点个数较多而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果最好!Kruskal

　　从所有边中找到一个最小的边，且将改变放入后不会生成圈，重复n-1次后求出最小生成树。我们首先将所有边排序，然后从小到大判断，如果不产生圈就加入树中，当加入n-1条边时停止。为了判断是否组成圈，我们要用到并查集，相关知识可以在本站或任一本竞赛书中找到，这里不赘述。算法复杂度是(eloge+eα)，α是做一次并查集的复杂度，可以认为是常数。

　　/*

　　并查集的一个特性:

　　用一个数组p[]表示每一个元素的父级元素

　　最父级的元素的父级元素是一个负数,这个负数的绝对值是这个集合下的元素的个数

　　*/

　　#include

　　#include

　　usingnamespace std;

　　constint N=1001; //定义能处理的最大点的个数

　　template

　　structEdge

　　{

　　int from;

　　int to;

　　T cost;

　　};

　　template

　　booloperator <(const Edge & a,const Edge & b)

　　{

　　return a.cost

　　}

　　/* [NextPage] 

　　找到x所在集合的最父级代表元素

　　如果这个集合只有x自己,那么最父级代表元素当然就是它自己

　　*/

　　intFindSet(int * p,int x)

　　{

　　int tmp,px=x;

　　while(p[px]>=0) //找到x所在集合的代表元素

　　px=p[px];

　　/*

　　路径压缩,可选,如果需要频繁查询,压缩之后可以提高速度

　　即把从x到代表元素路径上的所有的元素的父节点都表示为代表元素

　　*/

　　while(p[x]>=0)

　　{

　　tmp=p[x];

　　p[x]=px;

　　x=tmp;

　　}

　　return px; //x元素所在集合的代表元素

　　}

　　/*

　　合并x和y所在的集合.

　　*/

　　voidUnionSet(int * p,int x,int y)

　　{

　　int tmp;

　　x=FindSet(p,x);

　　y=FindSet(p,y);

　　if(x==y)

　　return ;

　　tmp=p[x]+p[y];

　　if(p[x]>p[y]) //将小树合并到大树下

　　{

　　p[y]=tmp;

　　p[x]=y;

　　}

　　else

　　{

　　p[x]=tmp;

　　p[y]=x;

　　}

　　return ;

　　}

　　/*

 [NextPage]

　　最小生成树算法之Kruskal算法:

　　算法思想:每次找最小的边,如果在已有的森林中加入该边后会形成回路,则舍弃,否则加入然后合并森林

　　n:点的个数;

　　edge_cnt:边的个数

　　edge[]:保存边的数组

　　edge_arr:保存选择边的数组,可选功能

　　*/

　　template

　　TMST_Kruskal(const int & n, const int & edge_cnt,Edge edge[], Edge* edge_arr = NULL)

　　{

　　T ans=0;

　　int i,x,y,p[N],cnt=0;

　　memset(p,-1,sizeof(p));

　　sort(edge,edge+edge_cnt);

　　for(i=0;i

　　{

　　x=FindSet(p,edge[i].from);

　　y=FindSet(p,edge[i].to);

　　if(x!=y)

　　{

　　UnionSet(p,x,y);

　　ans+=edge[i].cost;

　　if(edge_arr)

　　edge_arr[cnt]=edge[i];

　　cnt++;

　　if(cnt==n-1)

　　return ans;

　　}

　　}

　　return -1;

　　}