http://www.51nod.com/
Kruskal算法的高效實作需要一種稱作并查集的結構。我們在這裡不介紹并查集，隻介紹Kruskal算法的基本思想和證明，實作留在以後讨論。
Kruskal算法的過程：
（1） 将全部邊按照權值由小到大排序。
（2） 按順序（邊權由小到大的順序）考慮每條邊，隻要這條邊和我們已經選擇的邊不構成圈，就保留這條邊，否則放棄這條邊。
算法 成功選擇(n-1)條邊後，形成一個棵最小生成樹，當然如果算法無法選擇出(n-1)條邊，則 說明原圖不連通。
以下圖為例：
邊排序後為：
1 AF 1 2 DE 4 3 BD 5 4 BC 6 5 CD 10 6 BF 11 7 DF 14 8 AE 16 9 AB 17 10 EF 33
算法處理過程如下：
處理邊AF，點A與點F不在同一個集合裡，選中AF。
處理邊DE，點D與點E不在同一個集合裡，選中DE
處理邊BD，點B與點D不在同一個集合裡，選中BD
處理邊BC，點B與點C不在同一個集合裡，選中BC
處理邊CD，點C與點D在同一個集合裡，放棄CD。
處理邊BF，點B與點F不在同一個集合裡，選中BF。
至此，所有的點都連在了一起，剩下的邊DF，AE，AB，EF不用繼續處理了，算法執行結束。
Kruskal算法的證明。假設圖連通，我們證明Krusal算法得到一棵最小生成樹。我們假設Kruskal算法得到的樹是K (注意我們已經假設Kruskal算法一定可以得到生成樹)。假設T是一棵最小生成樹，并且K ≠T, K中顯然至少有一條邊。我們找到在K中，而不在T中最小權值的邊e。
把e加入T中，則形成一個圈，删掉這個圈中不在K中的邊f,得到新的生成樹T’。
f的存在性，如果全裡面所有的邊都在K中，則K包含圈，沖突。
考慮邊權值關系：
（1） 若w(f) > w(e), 則T’的權值和小于T的權值和，與T是最小生成樹沖突。
（2） 若w(f) < w(e), 說明Kruskal算法在考慮加入e之前先考慮了邊f，之是以沒加入f是因為f和之前加入的邊形成圈，之前加入的邊權值顯然不超過w(f) (因為加邊是從小到大的順序加入的)，是以之前加入的邊權值一定小于w(e)。而根據e的定義，K中權值小于w(e)的邊都在T中，這說明T中的邊會和f構成圈，沖突。
是以隻能w(f) = w(e)。T’仍然是最小生成樹，而T’和K相同的邊多了一條。
這樣下去有限步之後，最終可以把T變為K，進而K也是最小生成樹。
最後，我們來提供輸入輸出資料，由你來寫一段程式，實作這個算法，隻有寫出了正确的程式，才能繼續後面的課程。
輸入
第1行：2個數N,M中間用空格分隔，N為點的數量，M為邊的數量。（2 <= N <= 1000, 1 <= M <= 50000)
第2 - M + 1行：每行3個數S E W，分别表示M條邊的2個頂點及權值。(1 <= S, E <= N，1 <= W <= 10000) 輸出
輸出最小生成樹的所有邊的權值之和。 輸入示例
9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8 輸出示例
37 請選取你熟悉的語言，并在下面的代碼框中完成你的程式，注意資料範圍，最終結果會造成Int32溢出，這樣會輸出錯誤的答案。 不同語言如何處理輸入輸出，請檢視下面的語言說明。 使用并查集和貪心思想。适合稀疏圖。
Kruskal算法實作：
[cpp]view plain copy print ?
- #include <iostream>
- #include <stdio.h>
- #include <stdlib.h>
- using namespace std;
- int parent[10];
- int n,m;
- int i,j;
- struct edge{
- int u,v,w; //邊的頂點，權值
- }edges[10];
- //初始化并查集
- void UFset(){
- for(i=1; i<=n; i++) parent[i] = -1;
- }
- //查找i的跟
- int find(int i){
- int temp;
- //查找位置
- for(temp = i; parent[temp] >= 0; temp = parent[temp]);
- //壓縮路徑
- while(temp != i){
- int t = parent[i];
- parent[i] = temp;
- i = t;
- }
- return temp;
- }
- //合并兩個元素a,b
- void merge(int a,int b){
- int r1 = find(a);
- int r2 = find(b);
- int tmp = parent[r1] + parent[r2]; //兩個集合節點數的和
- if(parent[r1] > parent[r2]){
- parent[r1] = r2;
- parent[r2] = tmp;
- }else{
- parent[r2] = r1;
- parent[r1] = tmp;
- }
- }
- void kruskal(){
- int sumWeight = 0;
- int num = 0;
- int u,v;
- UFset();
- for(int i=0; i<m; i++)
- {
- u = edges[i].u;
- v = edges[i].v;
- if(find(u) != find(v)){ //u和v不在一個集合
- printf(”加入邊：%d %d,權值： %d\n”, u,v,edges[i].w);
- sumWeight += edges[i].w;
- num ++;
- merge(u, v); //把這兩個邊加入一個集合。
- }
- }
- printf(”weight of MST is %d \n”, sumWeight);
- }
- //比較函數，使用者排序
- int cmp(const void * a, const void * b){
- edge * e1 = (edge *)a;
- edge * e2 = (edge *)b;
- return e1->w - e2->w;
- }
- int main() {
- scanf(”%d %d”, &n, &m);
- for(i=0; i<m; i++){
- scanf(”%d %d %d”, &edges[i].u, &edges[i].v, &edges[i].w);
- }
- qsort(edges, m, sizeof(edge), cmp);
- kruskal();
- return 0;
- }
#include <iostream>
#include <stdio.h> #include <stdlib.h> using namespace std; int parent[10]; int n,m; int i,j; struct edge{ int u,v,w; //邊的頂點，權值 }edges[10]; //初始化并查集 void UFset(){ for(i=1; i<=n; i++) parent[i] = -1; } //查找i的跟 int find(int i){ int temp; //查找位置 for(temp = i; parent[temp] >= 0; temp = parent[temp]); //壓縮路徑 while(temp != i){ int t = parent[i]; parent[i] = temp; i = t; } return temp; } //合并兩個元素a,b void merge(int a,int b){ int r1 = find(a); int r2 = find(b); int tmp = parent[r1] + parent[r2]; //兩個集合節點數的和 if(parent[r1] > parent[r2]){ parent[r1] = r2; parent[r2] = tmp; }else{ parent[r2] = r1; parent[r1] = tmp; } } void kruskal(){ int sumWeight = 0; int num = 0; int u,v; UFset(); for(int i=0; i<m; i++) { u = edges[i].u; v = edges[i].v; if(find(u) != find(v)){ //u和v不在一個集合 printf("加入邊：%d %d,權值： %d\n", u,v,edges[i].w); sumWeight += edges[i].w; num ++; merge(u, v); //把這兩個邊加入一個集合。 } } printf("weight of MST is %d \n", sumWeight); } //比較函數，使用者排序 int cmp(const void * a, const void * b){ edge * e1 = (edge *)a; edge * e2 = (edge *)b; return e1->w - e2->w; } int main() { scanf("%d %d", &n, &m); for(i=0; i<m; i++){ scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w); } qsort(edges, m, sizeof(edge), cmp); kruskal(); return 0; }