1、最小生成樹-克魯斯卡爾算法克魯斯卡其爾算法的時間復(fù)雜度為O(eloge)(e為網(wǎng)中邊的數(shù)目)，因此它相對于普里姆算法而言，適合于求邊稀疏的網(wǎng)的最小生成樹?？唆斔箍査惴◤牧硪煌緩角缶W(wǎng)的最小生成樹。假設(shè)連通網(wǎng)N=(V,E),則令最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V,d),圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。依次類推，直至T中所有頂點都在同一連通分量上為止。例如圖為依照克魯斯卡爾算法構(gòu)造一棵最小生成樹的過程。代價分別為1,2,3,4的四條邊由于滿足上述條件，則

2、先后被加入到T中，代價為5的兩條邊(1,4)和(3,4)被舍去。因為它們依附的兩頂點在同一連通分量上，它們?nèi)艏尤隩中，則會使T中產(chǎn)生回路，而下一條代價(=5)最小的邊(2,3)聯(lián)結(jié)兩個連通分量，則可加入To因此，構(gòu)造成一棵最小生成樹。上述算法至多對e條邊各掃描一次，假若以“堆”來存放網(wǎng)中的邊，則每次選擇最小代價的邊僅需O(loge)的時間(第一次需O(e)。又生成樹T的每個連通分量可看成是一個等價類，則構(gòu)造T加入新的過程類似于求等價類的過程，由此可以以“樹與等價類”中介紹的mfsettp類型來描述T,使構(gòu)造T的過程僅需用O(eloge)的時間，由此，克魯斯卡爾算法的時間復(fù)雜度為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;存所有邊數(shù)(存權(quán)、兩端點)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生成樹鄰接表生成樹鏈表鏈表指針清零找出所有邊邊按權(quán)升序排序第一條邊加入生成樹鄰接表端點加入鏈表，根節(jié)點鏈指針為負:當前要選的邊數(shù)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;邊接兩棵樹