在例1-2及1-3中已考察過這個問題。因為具有n 個頂點的無向網絡G的每個生成樹剛好具有n-1條邊，所以問題是用某種方法選擇n-1條邊使它們形成G的最小生成樹。至少可以采用三種不同的貪婪策略來選擇這n-1條邊。這三種求解最小生成樹的貪婪算法策略是： K r u s k a l算法，P r i m算法和S o l l i n算法。
1.Kruskal算法
(1) 算法思想
K r u s k a l算法每次選擇n- 1條邊，所使用的貪婪准則是：從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。K r u s k a l算法分e 步，其中e 是網絡中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。
考察圖1-12a 中的網絡。初始時沒有任何邊被選擇。圖13-12b 顯示了各節點的當前狀態。邊（ 1,6）是最先選入的邊，它被加入到欲構建的生成樹中，得到圖1 3-1 2 c。下一步選擇邊（ 3，4）並將其加入樹中（如圖1 3-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算法的偽代碼。
/ /在一個具有n 個頂點的網絡中找到一棵最小生成樹
令T為所選邊的集合，初始化T=
令E 為網絡中邊的集合
w h i l e(E≠)&&(| T |≠n- 1) {
令(u,v)為E中代價最小的邊 E=E- {(u,v)} / /從E中刪除邊
i f( (u,v)加入T中不會產生環路)將（ u,v）加入T
}
i f(| T |==n-1) T是最小耗費生成樹
e l s e 網絡不是互連的，不能找到生成樹
圖13-13 Kruskao算法的偽代碼
(2) 正確性證明
利用前述裝載問題所用的轉化技術可以證明圖1 3-1 3的貪婪算法總能建立一棵最小耗費生成樹。需要證明以下兩點： 1) 只要存在生成樹，K r u s k a l算法總能產生一棵生成樹； 2) 產生的生成樹具有最小耗費。令G為任意加權無向圖（即G是一個無向網絡）。從1 2 .11 .3節可知當且僅當一個無向圖連通時它有生成樹。而且在Kruskal 算法中被拒絕（丟棄）的邊是那些會產生環路的邊。刪除連通圖環路中的一條邊所形成的圖仍是連通圖，因此如果G在開始時是連通的，則T與E中的邊總能形成一個連通圖。也就是若G開始時是連通的，算法不會終止於E= 和| T |< n- 1。
現在來證明所建立的生成樹T具有最小耗費。由於G具有有限棵生成樹，所以它至少具有一棵最小生成樹。令U為這樣的一棵最小生成樹， T與U都剛好有n- 1條邊。如果T=U, 則T就具有最小耗費，那麼不必再證明下去。因此假設T≠U，令k(k >0) 為在T中而不在U中的邊的個數，當然k 也是在U中而不在T中的邊的數目。 通過把U變換為T來證明U與T具有相同的耗費，這種轉化可在k 步內完成。每一步使在T而不在U中的邊的數目剛好減1。而且U的耗費不會因為轉化而改變。經過k 步的轉化得到的U將與原來的U具有相同的耗費，且轉化後U中的邊就是T中的邊。由此可知， T具有最小耗費。每步轉化包括從T中移一條邊e 到U中，並從U中移出一條邊f。邊e 與f 的選取按如下方式進行：
1) 令e 是在T中而不在U中的具有最小耗費的邊。由於k >0，這條邊肯定存在。
2) 當把e加入U時，則會形成唯一的一條環路。令f 為這條環路上不在T中的任意一條邊。
由於T中不含環路，因此所形成的環路中至少有一條邊不在T中。
從e 與f 的選擇方法中可以看出， V=U+ {e}-{f} 是一棵生成樹，且T中恰有k- 1條邊不在V中出現。現在來證明V的耗費與U的相同。顯然，V的耗費等於U的耗費加上邊e 的耗費再減去邊f 的耗費。若e 的耗費比f 的小，則生成樹V的耗費比U的耗費小，這是不可能的。如果e 的耗費高於f，在K r u s k a l算法中f 會在e 之前被考慮。由於f 不在T中，Kruskal 算法在考慮f 能否加入T時已將f 丟棄，因此f 和T中耗費小於或等於f 的邊共同形成環路。通過選擇e，所有這些邊均在U中，因此U肯定含有環路，但是實際上這不可能，因為U是一棵生成樹。e 的代價高於f 的假設將會導致矛盾。剩下的唯一的可能是e 與f 具有相同的耗費，由此可知V與U的耗費相同。
(3) 數據結構的選擇及復雜性分析
為了按耗費非遞減的順序選擇邊，可以建立最小堆並根據需要從堆中一條一條地取出各邊。當圖中有e 條邊時，需花(e) 的時間初始化堆及O ( l o ge) 的時間來選取每一條邊。邊的集合T與G中的頂點一起定義了一個由至多n 個連通子圖構成的圖。用頂點集合來描述每個子圖，這些頂點集合沒有公共頂點。為了確定邊（ u,v）是否會產生環路，僅需檢查u,v 是否在同一個頂點集中（即處於同一子圖）。如果是，則會形成一個環路；如果不是，則不會產生環路。因此對於頂點集使用兩個F i n d操作就足夠了。當一條邊包含在T中時，2個子圖將被合並成一個子圖，即對兩個集合執行U n i o n操作。集合的F i n d和U n i o n操作可利用8 .1 0 .2節的樹（以及加權規則和路徑壓縮）來高效地執行。F i n d操作的次數最多為2e，Un i o n操作的次數最多為n- 1（若網絡是連通的，則剛好是n- 1次）。加上樹的初始化時間，算法中這部分的復雜性只比O (n+e) 稍大一點。
對集合T所執行的唯一操作是向T中添加一條新邊。T可用數組t 來實現。添加操作在數組
的一端進行，因為最多可在T中加入n- 1條邊，因此對T的操作總時間為O (n)。
總結上述各個部分的執行時間，可得圖1 3-1 3算法的漸進復雜性為O (n+el o ge)。
(4) 實現
利用上述數據結構，圖1-1 3可用C + +代碼來實現。首先定義E d g e N o d e類（見程序1 3-6)，它是最小堆的元素及生成樹數組t 的數據類型。
程序13-6 Kruskal算法所需要的數據類型
template
class EdgeNode {
p u b l i c :
operator T() const {return weight;}
p r i v a t e :
T weight;//邊的高度
int u, v;//邊的端點
} ;
為了更簡單地使用8 .1 0 .2節的查找和合並策略，定義了U n i o n F i n d類，它的構造函數是程序8-1 6的初始化函數，U n i o n是程序8-1 6的加權合並函數，F i n d是程序8-1 7的路徑壓縮搜索函數。
為了編寫與網絡描述無關的代碼，還定義了一個新的類U N e t Wo r k，它包含了應用於無向網絡的所有函數。這個類與U n d i r e c t e d類的差別在於U n d i r e c t e d類中的函數不要求加權邊，而U N e t Wo r k要求邊必須帶有權值。U N e t Wo r k中的成員需要利用N e t w o r k類中定義的諸如B e g i n和N e x t Ve r t e x的遍歷函數。不過，新的遍歷函數不僅需要返回下一個鄰接的頂點，而且要返回到達這個頂點的邊的權值。這些遍歷函數以及有向和無向加權網絡的其他函數一起構成了W N e t w o r k類（見程序1 3-7）。
程序13-7 WNetwork類
template
class WNetwork : virtual public Network
{
public :
virtual void First(int i, int& j, T& c)=0;
virtual void Next(int i, int& j, T& c)=0;
} ;
象B e g i n和N e x t Ve r t e x一樣，可在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h類中加入函數F i r s t與N e x t。現在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h類都需要從W N e t Wo r k中派生而來。由於A d j a c e n c y W G r a p h類和L i n k e d W G r a p h類需要訪問U N e t w o r k的成員，所以這兩個類還必須從U N e t Wo r k中派生而來。U N e t Wo r k : : K r u s k a l的代碼見程序1 3-8，它要求將Edges() 定義為N e t Work 類的虛成員，並且把U N e t Wo r k定義為E d g e N o d e的友元）。如果沒有生成樹，函數返回f a l s e，否則返回t r u e。注意當返回true 時，在數組t 中返回最小耗費生成樹。
程序13-8 Kr u s k a l算法的C + +代碼
template
bool UNetwork::Kruskal(EdgeNode t[])
{// 使用K r u s k a l算法尋找最小耗費生成樹
// 如果不連通則返回false
// 如果連通，則在t [ 0 : n-2 ]中返回最小生成樹
int n=Ve r t i c e s () ;
int e=Edges();
/ /設置網絡邊的數組
InitializePos(); // 圖遍歷器
EdgeNode *E=new EdgeNode [e+1];
int k=0; // E的游標
for (int i=1; i <= n; i++) {// 使所有邊附屬於i
int j;
T c;
First(i, j, c);
while (j) {// j 鄰接自i
if (i < j) {// 添加到達E的邊
E[++k].weight=c;
E[k].u=i;
E[k].v=j;}
Next(i, j, c);
}
}
// 把邊放入最小堆
MinHeap > H(1);
H.Initialize(E, e, e);
UnionFind U(n); // 合並/搜索結構
// 根據耗費的次序來抽取邊
k=0; // 此時作為t的游標
while (e && k < n-1) {
// 生成樹未完成，尚有剩余邊
EdgeNode x;
H.DeleteMin(x); // 最小耗費邊
e-- ;
int a=U.Find(x.u);
int b=U.Find(x.v);
if (a != b) {// 選擇邊
t[k++]=x;
U .U n i o n ( a,b) ;}
}
D e a c t i v a t e P o s () ;
H .D e a c t i v a t e () ;
return (k== n-1);
}
2.Prim算法
與Kr u s k a l算法類似，P r i m算法通過每次選擇多條邊來創建最小生成樹。選擇下一條邊的貪婪准則是：從剩余的邊中，選擇一條耗費最小的邊，並且它的加入應使所有入選的邊仍是一棵樹。最終，在所有步驟中選擇的邊形成一棵樹。相反，在Kruskal 算法中所有入選的邊集合最終形成一個森林。
P r i m算法從具有一個單一頂點的樹T開始，這個頂點可以是原圖中任意一個頂點。然後往T中加入一條代價最小的邊（ u,v）使Tè{(u,v)}仍是一棵樹，這種加邊的步驟反復循環直到T中包含n- 1條邊。注意對於邊（ u,v），u、v 中正好有一個頂點位於T中。P r i m算法的偽代碼如圖1 -1 4所示。在偽代碼中也包含了所輸入的圖不是連通圖的可能，在這種情況下沒有生成樹。圖1-1 5顯示了對圖1-12a 使用P r i m算法的過程。把圖1-1 4的偽代碼細化為C + +程序及其正確性的證明留作練習（練習3 1）。
/ /假設網絡中至少具有一個頂點
設T為所選擇的邊的集合，初始化T=
設T V為已在樹中的頂點的集合，置T V= {1}
令E為網絡中邊的集合
w h i l e(E< >) & & (| T | < > n-1) {
令（u,v）為最小代價邊，其中u T V, v T V
i f（沒有這種邊） b re a k
E=E- {(u,v)} / /從E中刪除此邊
在T中加入邊（ u,v）
}
if (| T |==n- 1) T是一棵最小生成樹
else 網絡是不連通的，沒有最小生成樹
圖13-14 Prim最小生成樹算法
如果根據每個不在T V中的頂點v 選擇一個頂點n e ar (v)，使得n e ar (v) ? TV 且c o st (v, n e ar (v))的值是所有這樣的n e ar (v) 節點中最小的，則實現P r i m算法的時間復雜性為O (n2)。下一條添加到T中的邊是這樣的邊：其cost (v, near (v)) 最小，且v T V。
3.Sollin算法
S o l l i n算法每步選擇若干條邊。在每步開始時，所選擇的邊及圖中的n個頂點形成一個生成樹的森林。在每一步中為森林中的每棵樹選擇一條邊，這條邊剛好有一個頂點在樹中且邊的代價最小。將所選擇的邊加入要創建的生成樹中。注意一個森林中的兩棵樹可選擇同一條邊，因此必須多次復制同一條邊。當有多條邊具有相同的耗費時，兩棵樹可選擇與它們相連的不同的邊，在這種情況下，必須丟棄其中的一條邊。開始時，所選擇的邊的集合為空。若某一步結束時僅剩下一棵樹或沒有剩余的邊可供選擇時算法終止。
圖1-6給出了初始狀態為圖1-12a 時，使用S o l l i n算法的步驟。初始入選邊數為0時的情形如圖13-12a 時,森林中的每棵樹均是單個頂點。頂點1，2，.，7所選擇的邊分別是(1.6), (2,7),(3,4), (4,3), (5,4), (6,1), (7,2)，其中不同的邊是( 1,6)，( 2,7)，(3,4) 和( 5,4)，將這些邊加入入選邊的集合後所得到的結果如圖1 3-1 6 a所示。下一步具有頂點集{1,6}的樹選擇邊( 6,5)，剩下的兩棵樹選擇邊( 2,3)，加入這兩條邊後已形成一棵生成樹，構建好的生成樹見圖1 3-6 b。S o l l i n算法的C + +程序實現及其正確性證明留作練習（練習3 2)。
