1)算法的基本思想:
前面我们学习过Prim算法,他是一种以某个节点出发,按权值递增的次序选择合适的边来构造最小生成树的方法,他的时间复杂度为O(n2),与顶点有关,而与边无边,所以适合求边稠密的图的生成树。
算法构造一颗最小生成树的过程如下(母图基于Prim算法部分的无向图):
2)算法的描述:
在图中任取一个顶点K作为开始点,令U={k},W=V-U,其中V为图中所有顶点集,然后找一个顶点在U中,另一个顶点在W中的边中最短的一条,找到后,将该边作为最小生成树的树边保存起来,并将该边顶点全部加入U集合中,并从W中删去这些顶点,然后重新调整U中顶点到W中顶点的距离,使之保持最小,再重复此过程,直到W为空集止。
假设G=(V,E)是一个具有n个顶点的带权无向连通图,T=(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则构造最小生成树的过程如下:
(1)置U的初值等于V,TE的初值为空集;
(2)按权值从小到大的顺序依次选取图G中的边,若选取的边未使生成树T形成回路,则加入TE;若选取的边使生成树T形成回路,则将其舍弃。循环执行(2),直到TE中包含(n-1)条边为止。
3)C语言描述:
为实现克鲁斯卡尔算法需要设置一维辅助数组E,按权值从小到大的顺序存放图的边,数组的下标取值从0到e-1(e为图G边的数目)。
假设数组E存放图G中的所有边,且边已按权值从小到大的顺序排列。n为图G的顶点个数,e为图G的边数。克鲁斯卡尔算法如下:
#defineMAXE<最大边数>
#defineMAXV<最大顶点数>
typedefstruct
{
intvex1;//边的起始顶点
intvex2;//边的终止顶点
intweight;//边的权值
}Edge;
Voidkruskal(EdgeE[],intn,inte)
{inti,j,m1,m2,sn1,sn2,k;
intvset[MAXV];
for(i=0;i<n;i++)//初始化辅助数组
vset[i]=i;
k=1;//表示当前构造最小生成树的第k条边,初值为1
j=0;//E中边的下标,初值为0
while(k<e)//生成的边数小于e时继续循环
{ml=E[j].vex1;m2=E[j].vex2;//取一条边的两个邻接点
sn1=vset[m1];sn2=vset[m2];
//分别得到两个顶点所属的集合编号
if(sn1!=sn2)
//两顶点分属于不同的集合,该边是最小生成树的一条边
{printf(“(m1,m2):%d\n”,E[j].weight);
k++;//生成边数增l
for(i=0;i<n;i++)//两个集合统一编号
if(vset[i]=sn2)//集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++;//扫描下一条边
}
}
4)C语言完整实现
#defineMAXE11
#defineMAXV10
#include"stdio.h"
typedefstruct
{
intvex1;//边的起始顶点
intvex2;//边的终止顶点
intweight;//边的权值
}Edge;
voidkruskal(EdgeE[],intn,inte)
{inti,j,m1,m2,sn1,sn2,k;
intvset[MAXV];
for(i=1;i<=n;i++)//初始化辅助数组
vset[i]=i;
k=1;//表示当前构造最小生成树的第k条边,初值为1
j=0;//E中边的下标,初值为0
while(k<e)//生成的边数小于e时继续循环
{
m1=E[j].vex1;
m2=E[j].vex2;//取一条边的两个邻接点
sn1=vset[m1];
sn2=vset[m2];
//分别得到两个顶点所属的集合编号
if(sn1!=sn2)
//两顶点分属于不同的集合,该边是最小生成树的一条边
{
printf("(v%d,v%d):%d\n",m1,m2,E[j].weight);
k++;//生成边数增l
if(k>=6)break;
for(i=1;i<=n;i++)//两个集合统一编号
if(vset[i]==sn2)//集合编号为sn2的改为sn1
vset[i]=sn1;
}//if
j++;//扫描下一条边
}//while
}//kruskal
intmain()
{
EdgeE[MAXE];
intnume,numn;
//printf("输入边数和顶数:\n");
//scanf("%d%d",&nume,&numn);
nume=10;
numn=6;
printf("请输入各边及对应的的权值(起始顶点终止顶点权值)\n");
/*
for(inti=0;i<nume;i++)
scanf("%d%d%d",E[i].vex1,E[i].vex2,E[i].weight);
*/
//在这里对输入的数据进行排序,达到假设的要求,即:假设数组E存放图G中的
//所有边,且边已按权值从小到大的顺序排列
E[9].vex1=1;
E[9].vex2=2;
E[9].weight=6;
E[0].vex1=1;
E[0].vex2=3;
E[0].weight=1;
E[4].vex1=1;
E[4].vex2=4;
E[4].weight=5;
E[6].vex1=2;
E[6].vex2=3;
E[6].weight=5;
E[2].vex1=2;
E[2].vex2=5;
E[2].weight=3;
E[8].vex1=1;
E[8].vex2=2;
E[8].weight=6;
E[5].vex1=3;
E[5].vex2=4;
E[5].weight=5;
E[7].vex1=3;
E[7].vex2=5;
E[7].weight=6;
E[3].vex1=3;
E[3].vex2=6;
E[3].weight=4;
E[1].vex1=4;
E[1].vex2=6;
E[1].weight=2;
kruskal(E,numn,nume);
}
5)以上我们只是作抛砖引玉。比如节点的数量,边的数量,都可以根据实际情况来增减。
最小生成树在实际生活中主要用来解决生活中的优化问题。比如在几个大城市间修建路,如何修才能省时省力等。