最小生成樹的kruskal演算法

『壹』 kruskal演算法Kruskal演算法

克魯斯卡爾演算法是一種用於構建最小生成樹的常用演算法，當處理含有 n 個頂點的連通網 WN=(V,{E}) 時，其步驟如下：

首先，從一個初始狀態開始，構建一個僅包含 n 個頂點且邊集為空的子圖，視每個頂點為獨立的樹根，形成一個由 n 棵樹組成的森林。接著，從所有邊 E 中挑選權值最小的邊，如果這條邊連接的兩個頂點在不同的樹中，就將其添加到子圖中，合並兩棵樹；若兩個頂點已屬於同一棵樹，則跳過該邊，繼續尋找下一條權值最小的邊。這個過程一直持續到森林中只剩下一棵樹，即子圖的邊數達到 n-1 條，此時的子圖即為最小生成樹。

舉個例子，我們可以這樣操作：首先對所有的邊按權值排序，如圖所示，從AD開始連接，逐步構建。然後在剩下的邊中，避免選擇已形成連通的邊，如BC或EF，盡管它們可能是最短的。最終，通過這種方式選擇邊，直到所有頂點連通，形成最小生成樹。

最後的結構如下圖所示，所有頂點已通過邊連通，完成了最小生成樹的構建。

K r u s k a l演算法每次選擇n- 1條邊，所使用的貪婪准則是：從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。K r u s k a l演算法分e 步，其中e 是網路中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。

『貳』 Kruskal 演算法

最小生成樹，是在含有n個頂點的連通圖中，挑選n-1條邊構成的樹結構，這棵樹的全部邊的權重之和最小。

Kruskal演算法，專用於生成最小生成樹。

它的核心思路是，從權值最小的邊開始，依次選取連通圖中的邊，確保所選邊不會形成環路，直至得到n-1條邊。

開始時，將所有頂點獨立成森林，即每個頂點為一棵樹。然後按照邊的權重從小到大順序，將邊逐一加入森林中。加入時檢查，若加入後不會形成環路，則繼續加入。直至森林合並為一棵樹，即得到了最小生成樹。

圖中雖未描繪森林狀態，但每條邊的加入實際是將森林中的樹進行連接。例如，選取權值為7的邊時，不選擇權值為6的邊，原因是避免形成環路。