kruskal算法的时间复杂度主要由排序方法决定，其排序算法只与带权边的个数有关，与图中顶点的个数无关，当使用时间复杂度为O（eloge）的排序算法时，克鲁斯卡算法的时间复杂度即为O（eloge），因此当带权图的顶点个数较多而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果最好！
克鲁斯卡尔算法
假设 WN=(V,{E})是一个含有 n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n棵树的一个森林。之后，从网的边集 E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
普里姆算法
假设 WN=(V,{E})是一个含有 n个顶点的连通网，TV是 WN上最小生成树中顶点的集合，TE是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而 TE是 E的一个子集。在算法开始执行时，TE为空集，TV中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止。
--以上传自http://hi.baidu.com/valyanprogramming/blog/item/1bc960e6095f9726b93820d9.html
1.Kruskal
//题目地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1258
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node
{
int v1;
int v2;
int len;
}e[10000];//定义边集
int cmp(const void*a,const void*b)//快排比较函数
{
return((node*)a)->len-((node*)b)->len;
}
int v[100],a[100][100];//v为点集
void makeset(int n)
{
for(int i=0;i<n;i++)
v[i]=i;
}
int find(int x)
{
int h=x;
while(h!=v[h])
h=v[h];
return h;
}
int main()
{
int n,i,j,r1,r2,p,total;
while(scanf("%d",&n)!=EOF)
{
p=0;
total=0;
makeset(n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
e[p].v1=i;
e[p].v2=j;
e[p].len=a[i][j];
p++;
}
}
qsort(e,p,sizeof(e[0]),cmp);
for(i=0;i<p;i++)
{
r1=find(e[i].v1);
r2=find(e[i].v2);
if(r1!=r2)
{
total+=e[i].len;
v[r1]=r2;
}
}
printf("%d\n",total);
}
system("pause");
return 0;
}
2.Prim
//题目地址同上
#include<iostream>
using namespace std;
#define M 101
#define maxnum 100001
int dis[M][M];
int prim(int n)
{
bool used[M]={};
int d[M],i,j,k;
for(i=1; i<=n; i++)
d[i]= dis[1][i];
used[1]= true;
int sum=0;
for(i=1; i<n; i++){
int temp=maxnum;
for(j=1; j<=n; j++){
if(!used[j]&& d[j]<temp){
temp= d[j];
k= j;
}
}
used[k]= true;
sum+= d[k];
for(j=1; j<=n; j++){
if(!used[j]&& dis[k][j]<d[j])
d[j]= dis[k][j];//与Dijksta算法的差别之处
}
}
return sum;
}
int main()
{
int n,i,j;
while( cin>>n){
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d",&dis[i][j]);
if(!dis[i][j])
dis[i][j]= maxnum;
}
}
cout<<prim(n)<<endl;
}
return 0;
}
代码来自网络
Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(N log N)。
kruskal算法：
求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的
具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e步，其中e
是网络中边的数目。按耗费递增的顺序来考虑这e
条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
假设WN=(V,{E})是一个含有 n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的
过程为：先构造一个只含 n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n
棵树的一个森林。之后，从网的边集 E
中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶
点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
适用于场合如下：
1、样本服从非正态分布的情况，如果样本不满足正态分布假设，那么使用这两个检验方法可以避免样本数据的均值和方差的误差，同时确保数据分析结果的准确性。
2、样本独立或相关的情况，这两个检验方法都适用于独立或相关样本的比较，可以用来比较两个或多个样本之间的差异。