下午-克魯斯卡爾算法

最小生成樹—算卡其爾算法的時間復(fù)雜度為O（eloge）(e為網(wǎng)中邊的數(shù)目)，因此它相對算法從另一途徑求網(wǎng)的最小生成樹。假設(shè)連通網(wǎng)（，{E}小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T（{∮}成通分量在E中選擇代價最小的邊若該邊依附的頂點落在T中不同的連通量上，則將此邊加入到T至T中所有頂點都在同一連通分量上為止。例如圖為依照算法構(gòu)造一棵最小生成樹的過程。代價分別為1，2，3，4的四條邊由于滿足上述條件，則先后被加入到T中，代價為5的兩條邊（1，4）和（3，4）被舍去。因為它們依附的兩頂點在同一連通分量上，它們?nèi)艏覶中，則會使T中產(chǎn)生回路，而下一條代價（=5）最小的邊（2，3）聯(lián)結(jié)兩個連通分量，則可加入T。因上述算法至多對e小代價的邊僅需（log（第一次需（eT的每個連通分量可看成是一個等價類，則構(gòu)造Tmfsettp類型來描述TT的過程僅需用（elog此，算法的時間復(fù)雜度為（eloge ③3 ① ③

2 2③ 2⑥ ⑥②513③②513③223 223③ programkruskal;label10;constmax=6;s:array[1..max,1..max]ofvarp:array[1..(max*(max-1)div2),0..2]ofbyte;存所有邊數(shù)（存權(quán)、兩端點）f:array[1..max,1..max]ofinteger; q:array[1..max,1..2]ofinteger; fori:=1tomaxdo 鏈表指針清fori:=1tomax 找出所有forj:=1tomaxdoifs[i,j]<>0thenfori:=1tol-1 邊按權(quán)升序排forj:=i+1tolifp[i,0]>p[j,0]then 第一條邊加入生成樹鄰接q[p[1,1],1]:=p[1,1];q[p[1,1],2]:=-p[1,1];端點加入鏈表，根節(jié)點鏈指針為 i:=i+1;m:=p[i,1];n:=p[i,2];取當前選中邊的兩端點序 分別查找兩端點的ifm>0thenm:=q[m,2]untilm<=0;ifn>0thenn:=q[n,2]untiln<=0;ifm<0andm=nthengoto10;若為同一根，則f[p[i,1],p[i,2]]:=p[i,0];當前邊加入生成樹鄰接ifm=n 當前邊兩端點均不在樹中，則新建一棵q[p[i,1],1]:=p[i,1];q[p[i,1],2]:=-ifm<0andn=0 若一端點在某棵樹中，則加ifn<0andm=0 若另一端點在某棵樹中，則加ifm<0andn<0thenq[-n,2]:=-m;邊接兩棵10