1、Kruskal 算法算法K r u s k a l 算法每次選擇 n- 1 條邊，所使用的貪婪準則是：從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。K r u s k a l 算法分e 步，其中 e 是網絡中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。初始時沒有任何邊被選擇。邊（ 1 , 6）是最先選入的邊，它被加入到欲構建的生成樹中，得到圖 1 3 - 1 2 c。下一步選擇邊（ 3，4）并將其加入樹中（如圖 1 3

2、- 1 2 d 所示）。然后考慮邊( 2，7 ，將它加入樹中并不會產生環路，于是便得到圖 1 3 - 1 2 e。下一步考慮邊（ 2，3）并將其加入樹中（如圖 1 3 - 1 2 f 所示）。在其余還未考慮的邊中，（7， 4）具有最小耗費，因此先考慮它，將它加入正在創建的樹中會產生環路，所以將其丟棄。此后將邊（ 5，4）加入樹中，得到的樹如圖 13-12g 所示。下一步考慮邊（ 7，5），由于會產生環路，將其丟棄。最后考慮邊（ 6，5）并將其加入樹中，產生了一棵生成樹，其耗費為 9 9。圖 1 - 1 3 給出了 K r u s k a l 算法的偽代碼。（2）pascal 代碼最小生成樹的

3、Kruskal 算法。Kruskal 算法基本：每次選不屬于同一連通分量(保證不生成圈)且邊權值最小的頂點，將邊加入 MST，并將所在的 2 個連通分量合并，直到只剩通分量排序使用 Quicksort(O(eloge)檢查是否在同一連通分量用 Union-Find，每次 Find 和 union 運算近似常數Union-Find 使用 r啟發式合并和路徑壓縮總復雜度 O(eloge)=O(elogv) (因為 en(n-1)/2)constmaxn=100;maxe=maxn*maxn;typeedge=recorda,b:eger;/邊的 2 個頂點len:eger;/邊的長度end;var

4、edges:array0.maxeofedge;/保存所有邊的信息p,r:array0.maxnofeger;/pi保存 i 的父親節點，r 用來實現Union-Find 的 r啟發式n,e:eger;/n 為頂點數，e 為邊數procedure swap(a,b:eger);/交換beginedges0:=edgesa;edgesa:=edges;edges:=edges0;end;procedure quicksort(l,r:eger);/快速排序varx,i,j :eger;beginx:=edgesrandom(r-l+1)+l.len;i:=l;j:=r;repeatwhile e

5、dgesi.lenx do dec(j);if ij;if ljthen quicksort(l,j);if irthen quicksort(i,r);end;procedureinit;vari:eger;beginassign(input,g.in);reset(input);readln(n,e);for i:=1 to e do的信息readln(edgesi.a,edgesi.b,edgesi.len);/從文件讀入圖for i:=1 to n dopi:=i;/初始化并查集randomize;quicksort(1,e);/使用快速排序將邊按權值從小到大排列end;functio

6、n find(x:eger):eger;/并查集的 Find，用來判斷 2 個頂點是否屬于通分量beginif xpx thenpx:=find(px);find:=pxend;procedure union(a,b:通分量eger);/如果不屬于且權值最小則將2 個頂點合并到vart:eger;begina:=find(a);b:=find(b);if rar then beg:=a;a:=b;b:=tend;if ra=rthen inc(r);pa:=b;end;procedurekruskal;/主過程varen:eger;/en 為當前邊的count:eger;/統計進行了幾次合并。n-1 次合并后就得到最小生成樹tot:eger;/統計最小生成樹的邊權總和begincount:=0;en:=0; tot:=0;while countn-1 dobegininc(en);with edgesen dobeginif find(a)find(b) thenbeginunion(a,b);wrin(a