数据结构笔记分享——克鲁斯卡尔算法(Kruskal)

1、基本思想:设无向连通网为G=(V, E),令G的最小生成树为T=(U,
TE),其初态为U=V,TE={
},然后,按照边的权值由小到大的顺序,考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量,则将此边作为最小生成树的边加入到T中,同时把两个连通分量连接为一个连通分量;若被考察边的两个顶点属于同一个连通分量,则舍去此边,以免造成回路,如此下去,当T中的连通分量个数为1时,此连通分量便为G的一棵最小生成树。2、示例:

3、代码实现如下:

[cpp]view plaincopy

#includestdio.h

#includestdlib.h

structedge

{

intm;

intn;

intd;

}a[5010];

intcmp(constvoid*a,constvoid*b)//按升序排列

{

return((structedge*)a)-d((structedge*)b)-d;

}

intmain(void)

{

inti,n,t,num,min,k,g,x[100];

printf(请输入顶点的个数:);

scanf(%d,n);

t=n*(n-1)/2;

for(i=1;i=n;i++)

x[i]=i;

printf(请输入每条边的起始端点、权值:/n);

for(i=0;it;i++)

scanf(%d%d%d,a[i].m,a[i].n,a[i].d);//输入每条边的权值

qsort(a,t,sizeof(a[0]),cmp);

min=num=0;

for(i=0;itnumn-1;i++)

{

for(k=a[i].m;x[k]!=k;k=x[k])//判断线段的起始点所在的集合

x[k]=x[x[k]];

for(g=a[i].n;x[g]!=g;g=x[g])//判断线段的终点所在的集合

x[g]=x[x[g]];

if(k!=g)//如果线段的两个端点所在的集合不一样

{

澳门新葡亰3522平台游戏,x[g]=k;

min+=a[i].d;

num++;

printf(最小生成树中加入边:%d%d/n,a[i].m,a[i].n);

}

}

printf(最小生成树的权值为:%d/n,min);

system(pause);

return0;

}