克鲁斯卡尔算法

1、最小生成树-克鲁斯卡尔算法克鲁斯卡其尔算法的时间复杂度为O(eloge)(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=(V,E),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,d),图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。例如图为依照克鲁斯卡尔算法构造一棵最小生成树的过程。代价分别为1,2,3,4的四条边由于满足上述条件，则

2、先后被加入到T中，代价为5的两条边(1,4)和(3,4)被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入T中，则会使T中产生回路，而下一条代价(=5)最小的边(2,3)联结两个连通分量，则可加入To因此，构造成一棵最小生成树。上述算法至多对e条边各扫描一次，假若以“堆”来存放网中的边，则每次选择最小代价的边仅需O(loge)的时间(第一次需O(e)。又生成树T的每个连通分量可看成是一个等价类，则构造T加入新的过程类似于求等价类的过程，由此可以以“树与等价类”中介绍的mfsettp类型来描述T,使构造T的过程仅需用O(eloge)的时间，由此，克鲁斯卡尔算法的时间复杂度为O(eloge)

3、。programkruskal;label10;constmax=6;s:array1.max,1.maxofbyte=(0,6,1,5,0,0),(0,0,5,0,3,0),(0,0,0,5,6,4),(0,0,0,0,0,2),(0,0,0,0,0,6),(0,0,0,0,0,0);varp:array1.(max*(max-1)div2),0.2ofbyte;存所有边数(存权、两端点)f:array1.max,1.maxofinteger;q:array1.max,1.2ofinteger;i,j,l,m,n,zs:integer;beginfori:=1tomaxdoqi,2:=0;l

4、:=0;fori:=1tomaxdoforj:=1tomaxdoifsi,j0thenbeginl:=l+1;pl,0:=si,j;pl,1:=i;pl,2:=jend;fori:=1tol-1doforj:=i+1toldoifpi,0pj,0thenbeginzs:=pi,0;pi,0:=pj,0;pj,0:=zs;zs:=pi,1;pi,1:=pj,1;pj,1:=zs;zs:=pi,2;pi,2:=pj,2;pj,2:=zs;end;fp1,1,p1,2:=p1,0;qp1,1,1:=p1,1;qp1,1,2:=-p1,1;qp1,2,1:=p1,2;qp1,2,2:=p1,1;i:=

5、1;j:=0;I:所选边的序号，j生成树邻接表生成树链表链表指针清零找出所有边边按权升序排序第一条边加入生成树邻接表端点加入链表，根节点链指针为负:当前要选的边数repeati:=i+1;m:=pi,1;n:=pi,2;repeatifm0thenm:=qm,2untilm0thenn:=qn,2untiln=0;if(m0)and(m=n)thengoto10;若为同一根，则重选fpi,1,pi,2:=pi,0;当前边加入生成树邻接表ifm=nthen当前边两端点均不在树中，则新建一棵树beginqpi,1,1:=pi,1;qpi,1,2:=-pi,1;若一端点在某棵树中，则加入qpi,2,1:=pi,2;qpi,2,2:=pi,1end;if(m0)and(n=0)thenbeginqpi,2,1:=pi,2;qpi,2,2:=pi,1若另一端点在某棵树中，则加入end;if(n0)and(m=0)thenbeginqpi,1,1:=pi,1;qpi,1,2:=pi,2;end;边接两棵树