在例 及 中已考察過這個問題因為具有n 個頂點的無向網絡G的每個生成樹剛好具有n條邊所以問題是用某種方法選擇n條邊使它們形成G的最小生成樹至少可以采用三種不同的貪婪策略來選擇這n條邊這三種求解最小生成樹的貪婪算法策略是 K r u s k a l算法P r i m算法和S o l l i n算法
Kruskal算法
() 算法思想
K r u s k a l算法每次選擇n 條邊所使用的貪婪准則是從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中注意到所選取的邊若產生環路則不可能形成一棵生成樹K r u s k a l算法分e 步其中e 是網絡中邊的數目按耗費遞增的順序來考慮這e 條邊每次考慮一條邊當考慮某條邊時若將其加入到已選邊的集合中會出現環路則將其拋棄否則將它選入
考察圖a 中的網絡初始時沒有任何邊被選擇圖b 顯示了各節點的當前狀態邊( )是最先選入的邊它被加入到欲構建的生成樹中得到圖 c下一步選擇邊( )並將其加入樹中(如圖 d所示)然後考慮邊( )將它加入樹中並不會產生環路於是便得到圖 e下一步考慮邊( )並將其加入樹中(如圖 f所示)在其余還未考慮的邊中()具有最小耗費因此先考慮它將它加入正在創建的樹中會產生環路所以將其丟棄此後將邊( )加入樹中得到的樹如圖g 所示下一步考慮邊( )由於會產生環路將其丟棄最後考慮邊( )並將其加入樹中產生了一棵生成樹其耗費為 圖 給出了K r u s k a l算法的偽代碼
/ /在一個具有n 個頂點的網絡中找到一棵最小生成樹
令T為所選邊的集合初始化T=
令E 為網絡中邊的集合
w h i l e(E≠ )&&(| T |≠n ) {
令(uv)為E中代價最小的邊 E=E { (uv) } / /從E中刪除邊
i f( (uv)加入T中不會產生環路)將( uv)加入T
}
i f(| T | = =n) T是最小耗費生成樹
e l s e 網絡不是互連的不能找到生成樹
圖 Kruskao算法的偽代碼
() 正確性證明
利用前述裝載問題所用的轉化技術可以證明圖 的貪婪算法總能建立一棵最小耗費生成樹需要證明以下兩點 ) 只要存在生成樹K r u s k a l算法總能產生一棵生成樹; ) 產生的生成樹具有最小耗費令G為任意加權無向圖(即G是一個無向網絡)從 節可知當且僅當一個無向圖連通時它有生成樹而且在Kruskal 算法中被拒絕(丟棄)的邊是那些會產生環路的邊刪除連通圖環路中的一條邊所形成的圖仍是連通圖因此如果G在開始時是連通的則T與E中的邊總能形成一個連通圖也就是若G開始時是連通的算法不會終止於E= 和| T |< n
現在來證明所建立的生成樹T具有最小耗費由於G具有有限棵生成樹所以它至少具有一棵最小生成樹令U為這樣的一棵最小生成樹 T與U都剛好有n 條邊如果T=U 則T就具有最小耗費那麼不必再證明下去因此假設T≠U令k(k >) 為在T中而不在U中的邊的個數當然k 也是在U中而不在T中的邊的數目 通過把U變換為T來證明U與T具有相同的耗費這種轉化可在k 步內完成每一步使在T而不在U中的邊的數目剛好減而且U的耗費不會因為轉化而改變經過k 步的轉化得到的U將與原來的U具有相同的耗費且轉化後U中的邊就是T中的邊由此可知 T具有最小耗費每步轉化包括從T中移一條邊e 到U中並從U中移出一條邊f邊e 與f 的選取按如下方式進行
) 令e 是在T中而不在U中的具有最小耗費的邊由於k >這條邊肯定存在
) 當把e 加入U時則會形成唯一的一條環路令f 為這條環路上不在T中的任意一條邊
由於T中不含環路因此所形成的環路中至少有一條邊不在T中
從e 與f 的選擇方法中可以看出 V=U+ {e} { f } 是一棵生成樹且T中恰有k 條邊不在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的耗費相同
() 數據結構的選擇及復雜性分析
為了按耗費非遞減的順序選擇邊可以建立最小堆並根據需要從堆中一條一條地取出各邊當圖中有e 條邊時需花(e) 的時間初始化堆及O ( l o ge) 的時間來選取每一條邊邊的集合T與G中的頂點一起定義了一個由至多n 個連通子圖構成的圖用頂點集合來描述每個子圖這些頂點集合沒有公共頂點為了確定邊( uv)是否會產生環路僅需檢查uv 是否在同一個頂點集中(即處於同一子圖)如果是則會形成一個環路;如果不是則不會產生環路因此對於頂點集使用兩個F i n d操作就足夠了當一條邊包含在T中時個子圖將被合並成一個子圖即對兩個集合執行U n i o n操作集合的F i n d和U n i o n操作可利用 節的樹(以及加權規則和路徑壓縮)來高效地執行F i n d操作的次數最多為eUn i o n操作的次數最多為n (若網絡是連通的則剛好是n 次)加上樹的初始化時間算法中這部分的復雜性只比O (n+e) 稍大一點
對集合T所執行的唯一操作是向T中添加一條新邊T可用數組t 來實現添加操作在數組的一端進行因為最多可在T中加入n 條邊因此對T的操作總時間為O (n)
總結上述各個部分的執行時間可得圖 算法的漸進復雜性為O (n+el o ge)
() 實現
利用上述數據結構圖 可用C + +代碼來實現首先定義E d g e N o d e類(見程序 )它是最小堆的元素及生成樹數組t 的數據類型
程序 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;//邊的端點
} ;
為了更簡單地使用 節的查找和合並策略定義了U n i o n F i n d類它的構造函數是程序 的初始化函數U n i o n是程序 的加權合並函數F i n d是程序 的路徑壓縮搜索函數
為了編寫與網絡描述無關的代碼還定義了一個新的類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類(見程序 )
程序 WNetwork類
template
class WNetwork : virtual public Network
{
public :
virtual void First(int i int& j T& c)=;
virtual void Next(int i int& j T& c)=;
} ;
象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的代碼見程序 它要求將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 中返回最小耗費生成樹
程序 Kr u s k a l算法的C + +代碼
template
bool UNetwork ::Kruskal(EdgeNode t[])
{// 使用K r u s k a l算法尋找最小耗費生成樹
// 如果不連通則返回false
// 如果連通則在t [ : n ]中返回最小生成樹
int n = Ve r t i c e s ( ) ;
int e = Edges();
/ /設置網絡邊的數組
InitializePos(); // 圖遍歷器
EdgeNode *E = new EdgeNode [e+];
int k = ; // E的游標
for (int i = ; 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();
HInitialize(E e e);
UnionFind U(n); // 合並/搜索結構
// 根據耗費的次序來抽取<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23589.html
