前言
Kruskal是在一個圖（圖論）中生成最小生成樹的算法之一。（另外還有Prim算法，之後會涉及到）這就牽扯到了最小生成樹的概念，其實就是總權值最小的一個連通無回路的子圖。（結合下文的示意圖不難了解）這裡的代碼并沒有用圖的存儲結構（如：矩陣，鄰接連結清單等）來處理和運用這個算法，而是最簡單的三元組輸入，這樣會使得這個過程簡化很多，至于圖的存儲方式，在之後總結圖資料結構的時候會具體讨論。
Kruskal算法的思想與過程
（1）思想：其實這個算法的本質還是一個貪心算法的過程。其實我們可以這樣想，一個圖中，我們要想讓生成的子圖（更确切的說是樹）總權值最小，那麼隻要依次選擇圖中權值最小的邊、權值次小的邊、……，這樣自然就保證了生成的圖總權值最小。但是别忘了一點，我們要求的生成的子圖還得是一棵樹（樹的定義：一個連通無回路的圖），這就帶來了一個問題，我們在權值從小到大選擇邊的時候，可能會使生成的子圖産生了回路，這就不符合概念了，是以我們不僅需要權值從小到大選擇邊還應該保證這些邊組成的子圖構不成回路！這個過程不就是貪心選擇的過程嗎。
過程（标準定義）：
任給一個有n個頂點的連通網絡N = {V, E}，首先構造一個由這n個頂點組成、不含任何邊的圖T = {V, 空集}，其中每個頂點自成一個連通分量。不斷從E中取出權值最小的一條邊（若有多條，任取其一），若該邊的兩個端點來自不同的連通分量，則将此邊加入T中。如此重複，直到所有頂點在同一個連通分量上為止。
為何用并查集與最小堆實作Kruskal算法？
這個問題最根本的解答在上面Kruskal算法的實作過程當中，過程中涉及到兩個重要的步驟：
(1)每次取得權值最小的邊
(2)判斷加入的邊的兩個端點是否來自同一連通分量（實質就是保證加入邊後不會産生回路）
而最小堆可以實作每次取得一組資料中關鍵碼（這裡可以代表權值大小）最小的資料；并查集可以将不同的集合（這裡可以代表點集合）Union起來并且可以判斷不同集合是否有交集（這裡可以判斷兩個點是否同屬于一個集合，進而判斷加入邊後是否會出現回路！）。沒錯！這簡直就是Kruskal算法實作的标配，下面Kruskal算法的實作過程圖也展現了這一點！（注：之前的博文對最小堆和并查集都有總結，對這兩個資料結構概念不清的話可以看看）
Kruskal算法生成最小生成樹的一個執行個體：
程式輸入資料（三元組格式）：
7 9 //圖的頂點數量、圖的邊的數量
0 1 28 //下面每行都存儲了一個邊的資訊
0 5 10 //依次表示：邊的端點1、邊的端點2、邊的權值
1 2 16
1 6 14
2 3 12
3 4 22
3 6 18
4 5 25
4 6 24
圖表示：
節點中的數字表示節點的序号或者是編号，邊上的數字代表每條邊的權值，你不要糾結于每條邊的權值與其在圖上的比例并不協調！因為現實環境中權值的意義有很多，比如花費、代價、重要程度等等。
Kruskal實作過程圖解：
很清晰易懂的圖解！
代碼實作過程中結構注意點！
（1）對邊結構體的構造：
這裡必須對此結構變量的大于、大于等于、小于運算符做重載（隻通過邊的權值比較即可），應為在最小堆中會直接對此變量進行比較！
（2）Kruskal算法實作函數：
尤其注意的應該是并查集建立的時候，其構造函數為何傳遞了頂點數量多1，否則這會導緻一個嚴重的錯誤（或者說是隐患）！下面會通過另一個文章着重解釋。
（3）關于輸出：
這裡隻是對最小生成樹的總權重這個名額進行了輸出，其他的名額都可以通過那個儲存最小生成樹的所有邊的全局數組得到。
Kruskal.cpp代碼
/*
*運用并查集及最小堆實作Kruskal算法
*/
#include "UFSets.h"
#include "heap.h"
using namespace std;
struct WEDGE { //權重邊結構定義
int vertex1, vertex2; //決定邊的兩個頂點
int weights; //邊的權重
//構造函數
WEDGE(int v1 = -, int v2 = -, int w = ) {
vertex1 = v1;
vertex2 = v2;
weights = w;
}
bool operator >(WEDGE& WE); //重載邊的大于比較
bool operator <(WEDGE& WE); //重載邊的小于比較
bool operator >=(WEDGE& WE); //重載大于等于比較
};
WEDGE minTreeEdges[]; //存儲最小生成樹的邊集
void Kruskal(WEDGE* we, int edg_amou, int vex_amou);
int main()
{
int vertexsAmount{ }, edgesAmount{ }; //輸入的點數與邊數
WEDGE wedge[]; //初始化20條邊
cin >> vertexsAmount >> edgesAmount;
for (int i = ; i < edgesAmount; i ++) { //循環輸入邊的頂點及權重
cin >> wedge[i].vertex1 >> wedge[i].vertex2
>> wedge[i].weights;
}
Kruskal(wedge, edgesAmount, vertexsAmount);
//輸出最小生成樹的總權重
int sumWeights{ };
for (int j = ; j < vertexsAmount; j ++) {
sumWeights += minTreeEdges[j].weights;
}
cout << sumWeights << endl;
system("pause");
return ;
}
void Kruskal(WEDGE* we, int edg_amou, int vex_amou) {
//Kruskal算法實作函數，參數分别是：一組邊集合、邊數、頂點數
MinHeap<WEDGE> minheap(we, edg_amou); //建立最小堆
UFSets uf_set(vex_amou + ); //建立并查集
WEDGE edge;
int vex_1{ }, vex_2{ };
int count{ }; //最小生成樹加入邊數計數
while (count < vex_amou){ //選入總邊數-1條邊即可
minheap.removeMin(edge); //删除并傳回堆頂元素
vex_1 = uf_set.Find(edge.vertex1);
vex_2 = uf_set.Find(edge.vertex2);
if (vex_1 != vex_2) { //兩個頂點不在同一連通分量中
minTreeEdges[count] = edge; //選入
uf_set.Union(vex_1, vex_2); //将兩個頂點連通
count++;
}
}
}
//重載運算符定義
bool WEDGE::operator >(WEDGE& WE) {
if (weights > WE.weights) {
return true;
}
else {
return false;
}
}
bool WEDGE::operator<(WEDGE& WE) {
if (weights < WE.weights) {
return true;
}
else {
return false;
}
}
bool WEDGE::operator>=(WEDGE& WE) {
if (weights >= WE.weights) {
return true;
}
else {
return false;
}
}
這個檔案中代碼的運作需要依靠兩個資料結構的頭檔案——最小堆和并查集.h。這裡就不在貼出來了，需要的話可以在文章末的連結下載下傳，也可以看之前對這兩個資料結構總結時候所貼的代碼。下面用這段代碼測試一下我們上面的執行個體！
嗯，他表現的不錯，在我們的過程圖中，最終的權值和：10+12+14+16+22+25 = 99。
另類的測試！！！
不過這隻是組測試資料，我們應該再找一組程式完全陌生的資料試試，看下面的題目：（題目是在網站中摘下來的~）
資料結構實驗之圖論六：村村通公路
Time Limit : 1000MS Memory Limit : 65536KB
Submit Statistic
Problem Description
目前農村公路建設正如火如荼的展開，某鄉鎮政府決定實作村村通公路，工程師現有各個村落之間的原始道路統計資料表，
表中列出了各村之間可以建設公路的若幹條道路的成本，你的任務是根據給出的資料表，求使得每個村都有公路連通所需要的最低成本。
Input
連續多組資料輸入，每組資料包括村落數目N(N <= 1000)和可供選擇的道路數目M(M <= 3000)，随後M行對應M條道路，
每行給出3個正整數，分别是該條道路直接連通的兩個村莊的編号和修建該道路的預算成本，村莊從1～N編号。
Output
輸出使每個村莊都有公路連通所需要的最低成本，如果輸入資料不能使所有村莊暢通，則輸出 - 1，表示有些村莊之間沒有路連通。
Example Input
5 8
1 2 12
1 3 9
1 4 11
1 5 3
3 2 6
2 4 9
3 4 4
5 4 6
Example Output
19
Author
xam
這是一個典型的應用題，看看下面的測試結果！
Oh! No!問題似乎很嚴重！程式崩潰了！這是我們的程式有問題嗎？還是其他的bug？也許不是，你可以看看這兩組輸入資料的微妙差别，也許會受到啟發！（其實上文中我已經做了提示）我保證這個Kruskal算法的實作是沒有問題的，下篇博文會揭開這一隐患的謎底。
頭檔案下載下傳連結：
連結：https://pan.baidu.com/s/1eROKT3c 密碼：9613