1 問題描述
何為Kruskal算法？
該算法功能：求取加權連通圖的最小生成樹。假設加權連通圖有n個頂點，那么其最小生成樹有且僅有n - 1條邊。
該算法核心思想：從給定加權連通圖中，選擇當前未被選擇的，不能形成回路且權值最小的邊，加入到當前正在構造的最小生成樹中。
2 解決方案
2.1 構造最小生成樹示例
下面請看一個具體示例：
給定一個加權連通圖，其包含5個頂點，分別為：1,2,3,4,5。包含7條邊，按照從小到大排序依次為：
1-2,5
2-3,5
3-5,6
2-4,12
4-5,12
2-5,15
3-4,17
那么可知，使用kruskal算法構造該加權連通圖的最小生成樹，則需要選擇出這7條邊中滿足定義的4條邊。
(1)原始圖
(2)添加第1條邊
此時未選中任何一條邊，那么直接選擇7條邊中最小的一條邊，2-3,5。（PS：當權值最小的邊有多個時，只要滿足定義，可以隨意選擇一條邊即可。例如，此處也可以選擇1-2,5）
(2)添加第2條邊
此時，從剩余的6條邊中選擇最小權值的邊，可以輕易知道為1-2,5。加入此邊后，檢查此時的正在構造的最小生成樹，沒有回路，符合定義，即可以確認加入。
(3)添加第3條邊
此時，從剩余的5條邊中選擇最小權值且不會生成環(huán)的邊，輕易可知，3-5,6符合要求。
(4)添加第4條邊（PS：此時也是最小生成樹的最后一條邊）
從剩余的4條邊中選擇最小權值且不會生成回環(huán)的邊，發(fā)現(xiàn)2-4,12、4-5,12均符合要求，此時，任意選擇其中一條邊即可。這里，我選擇的是4-5,12。
(5)最小生成樹以及構造完畢，結束構造。
2.2 偽碼及時間效率分析
該算法在開始的時候，會將給定連通圖所有邊的權值進行從小到大排列。然后，從一個空子圖開始，它會掃描這個這個有序列表，并試圖把列表中的下一條邊加入到當前正在構造的子圖（或者說是最小生成樹）中。當前，這種添加不能形成一個回路，如果產(chǎn)生了回路，則把這條邊跳過。
Kruskal(G) { //構造最小生成樹的Kruskal算法 //輸入：加權連通圖G = <V, E>，其中V為頂點數(shù)，E為具體邊集合 //其中E中邊已經(jīng)經(jīng)過處理，按照權值從小到大排列 //輸出：Et，組成G的最小生成樹的邊的集合
Et = 空集； int count = 0; //用于計算進行已構造的邊的總數(shù)
int k = 0; //表示從E中第一條邊序號
while(count <= V - 1) {
k = k + 1; if (Et U {ek}) { //集合Et加入第k條邊不產(chǎn)生回路
Et = Et U {ek};
count++;
}
} return Et;
}
通過以上的偽碼，可以知道，Kruskal算法的時間效率取決于兩點：
（1）對給定連通圖所有邊權值進行排序的時間效率；
（2）對新加入邊，進行是否形成回路判斷的時間效率。
首先，談談（1）的時間效率。對于排序算法，一般的時間效率分為O(n^2)（例如，選擇排序和冒泡排序）和O(nlogn)（例如，合并排序和快速排序）。由于合并排序，相對于快速排序要穩(wěn)定，所以，此處我們可以選擇合并排序來處理問題（1），即時間效率為O(nlogn)，其中n為頂點總數(shù)。
其次，談談（2）的時間效率。對于問題（2）中要實現(xiàn)的功能，有一些高效的算法可以實現(xiàn)這種功能，這些算法的核心就是對兩個頂點是否屬于同一棵樹的關鍵性檢查，它們被稱為并查算法，而該算法能夠達到的最優(yōu)時間效率為O(eloge)，其中e為具體邊總數(shù)。
最后，我們來探討一下使用并查算法實現(xiàn)（2）中要求的功能。
使用并查算法實現(xiàn)檢查回環(huán)問題，這里涉及的是一種抽象數(shù)據(jù)類型，這種數(shù)據(jù)類型是由某個有限集的一系列不相交子集以及下面這些操作構成的。
id(x)生成一個單元集合{x}。假設這個操作對集合S的每一個元素只能應用一次。
find(x)返回一個包含x的子集。
union(x, y)構造分別包含x和y的不相交子集Sx和Sy的并集，并把它添加到子集的集合中，以代替被刪除后的Sx和Sy。
例如，其中S = {1， 2， 3， 4， 5， 6}。首先使用id(x)，初始化結果：{1}，{2}，{3}，{4}，{5}，{6}。
現(xiàn)在執(zhí)行union(1,4)得到{1,4}，執(zhí)行union(4,5)得到{1,4,5}，此時集合結果：{1,4,5}，{2}，{3}，{6}。
那么此時執(zhí)行find(1)或者find(4)或者find(5)返回子集{1,4,5}，執(zhí)行find(3)返回子集{3}。
上面就是并查算法的應用思想，那么影響并查算法的時間效率，就是id(x)和union(x)函數(shù)的具體實現(xiàn)來決定。
此處對于id(x)和union(x)的實現(xiàn)，我采用樹的性質來實現(xiàn)，把已經(jīng)構造的邊形成一棵樹，當有新增的邊時，且新增的邊所在樹的層數(shù)或者所有節(jié)點總數(shù)小于當前構造的樹，那么我們就把新增的邊所在樹的根節(jié)點改變成當前正在構造的樹的根節(jié)點的直接子節(jié)點。
例如合并子集{1,4,5,2}（PS：該子集構成的樹根節(jié)點為1）}和{3,6}（PS：該子集構成的樹的根節(jié)點為3），那么可以把根節(jié)點3直接轉換為1的一個直接子節(jié)點即可。具體如下圖所示：
講完上面的定義及思想，下面就來具體看看對于2.1中示例圖實現(xiàn)的編碼應用。
首先，是初始化id(x)，這里我首先令每一個單節(jié)點樹的id(x)值為-1。
for(int i = 0;i < n;i++) id[i] = -1; //初始化id(x)，令所有頂點的id值為-1，即表示為根節(jié)點
然后，是find(x)的實現(xiàn)：
//獲取節(jié)點a的根節(jié)點編號
public int find(int[] id, int a) { int i, root, k;
root = a; while(id[root] >= 0) root = id[root]; //此處，若id[root] >= 0，說明此時的a不是根節(jié)點，因為唯有根節(jié)點的值小于0
k = a; while(k != root) { //將a節(jié)點所在樹的所有節(jié)點，都變成root的直接子節(jié)點
i = id[k];
id[k] = root;
k = i;
} return root;
}
最后，是union(x)的實現(xiàn):
//判斷頂點a和頂點b的根節(jié)點大小，根節(jié)點值越小，代表其對應樹的節(jié)點越多，將節(jié)點少的樹的根節(jié)點作為節(jié)點多的樹的根節(jié)點的直接子節(jié)點
public void union(int[] id, int a, int b) { int ida = find(id, a); //得到頂點a的根節(jié)點
int idb = find(id, b); //得到頂點b的根節(jié)點
int num = id[ida] + id[idb]; //由于根節(jié)點值必定小于0，此處num值必定小于零
if(id[ida] < id[idb]) {
id[idb] = ida; //將頂點b的根節(jié)點作為頂點a的直接子節(jié)點
id[ida] = num; //更新根節(jié)點的id值
} else {
id[ida] = idb; //將頂點a的根節(jié)點作為頂點b的直接子節(jié)點
id[idb] = num; //更新根節(jié)點的id值 }
}
到這里后，看一下，構造樹型id(x)值的具體圖：
首先頂點1到5的id(x) = {-1, -1, -1, -1, -1}，即表示剛開始，所有頂點均為根節(jié)點。(PS:后面示例id(x)、find(x)和union(x, y)中對于數(shù)組中元素均為1開始，不是0開始計算數(shù)組中元素，這樣是方面描述，請大家不要見怪喲。注意，下面圖中id = 2表示根節(jié)點為頂點3)
（1）選擇第1條邊，2-3，5
此時id(2) = -1，find(2) = 2根節(jié)點為2。id(3) = -1，find(3) = 3根節(jié)點為3。根據(jù)union(x)函數(shù)可知，由于id(find(2)) >= id(find(3))，所以id(find(2)) = idb = 2，id(find(3)) = num = -2
此時id(x) = {-1, 2, -2, -1, -1 }
（2）選擇第2條邊，1-2,5
此時，id(1) = -1，find(1) = 1根節(jié)點為1。Id(2) = 2，find(2) = 3根節(jié)點為3。根據(jù)union(x)函數(shù)可知，由于id(find(1)) > id(find(2))，所以id(find(1)) = idb = 2，id(find(2)) = num = -3
此時id(x) = {2, 2, -3, -1, -1 }
（3）選擇第3條邊，3-5,6
此時，id(3) = -3，find(3) = 3根節(jié)點為3。Id(5) = -1，find(5) = 5根節(jié)點為5。根據(jù)union(x)函數(shù)可知，由于id(find(3)) < id(find(5))，所以id(find(5)) = ida = 2，id(find(3)) = num = -4
此時id(x) = {2, 2, -4, -1, 2}
（4）選擇第4條邊，4-5,12（此處也是最小生成樹的最后一條邊）
此時，id(4) = -1，find(4) = 4根節(jié)點為4。Id(5) = 2，find(5) = 3根節(jié)點為3。根據(jù)union(x)函數(shù)可知，由于id(find(4)) > id(find(5))，所以id(find(4)) = idb = 2，id(find(5)) = num = -5
此時id(x) = {2, 2, -5, 2, 2 }
2.3 具體編碼（最佳時間效率）
具體代碼如下：
package com.liuzhen.systemExe;import java.util.ArrayList;import java.util.Scanner;public class Kruskal { //內(nèi)部類，其對象表示連通圖中一條邊
class edge { public int a; // 開始頂點
public int b; //結束頂點
public int value; //權值
edge(int a, int b, int value) { this.a = a; this.b = b; this.value = value;
}
} //使用合并排序，把數(shù)組A按照其value值進行從小到大排序
public void edgeSort(edge[] A){ if(A.length > 1) {
edge[] leftA = getHalfEdge(A, 0);
edge[] rightA = getHalfEdge(A, 1);
edgeSort(leftA);
edgeSort(rightA);
mergeEdgeArray(A, leftA, rightA);
}
} //judge = 0返回數(shù)組A的左半邊元素，否則返回右半邊元素
public edge[] getHalfEdge(edge[] A, int judge) {
edge[] half; if(judge == 0) {
half = new edge[A.length / 2]; for(int i = 0;i < A.length / 2;i++)
half[i] = A[i];
} else {
half = new edge[A.length - A.length / 2]; for(int i = 0;i < A.length - A.length / 2;i++)
half[i] = A[A.length / 2 + i];
} return half;
} //合并leftA和rightA，并按照從小到大順序排列
public void mergeEdgeArray(edge[] A, edge[] leftA, edge[] rightA) { int i = 0; int j = 0; int len = 0; while(i < leftA.length && j < rightA.length) { if(leftA[i].value < rightA[j].value) {
A[len++] = leftA[i++];
} else {
A[len++] = rightA[j++];
}
} while(i < leftA.length) A[len++] = leftA[i++]; while(j < rightA.length) A[len++] = rightA[j++];
}
//獲取節(jié)點a的根節(jié)點編號
public int find(int[] id, int a) { int i, root, k;
root = a; while(id[root] >= 0) root = id[root]; //此處，若id[root] >= 0，說明此時的a不是根節(jié)點，因為唯有根節(jié)點的值小于0
k = a; while(k != root) { //將a節(jié)點所在樹的所有節(jié)點，都變成root的直接子節(jié)點
i = id[k];
id[k] = root;
k = i;
} return root;
} //判斷頂點a和頂點b的根節(jié)點大小，根節(jié)點值越小，代表其對應樹的節(jié)點越多，將節(jié)點少的樹的節(jié)點添加到節(jié)點多的樹上
public void union(int[] id, int a, int b) { int ida = find(id, a); //得到頂點a的根節(jié)點
int idb = find(id, b); //得到頂點b的根節(jié)點
int num = id[ida] + id[idb]; //由于根節(jié)點值必定小于0，此處num值必定小于零
if(id[ida] < id[idb]) {
id[idb] = ida; //將頂點b作為頂點a的直接子節(jié)點
id[ida] = num; //更新根節(jié)點的id值
} else {
id[ida] = idb; //將頂點a作為頂點b的直接子節(jié)點
id[idb] = num; //更新根節(jié)點的id值 }
} //獲取圖A的最小生成樹
public ArrayList<edge> getMinSpanTree(int n, edge[] A) {
ArrayList<edge> list = new ArrayList<edge>(); int[] id = new int[n]; for(int i = 0;i < n;i++)
id[i] = -1; //初始化id(x)，令所有頂點的id值為-1，即表示為根節(jié)點
edgeSort(A); //使用合并排序，對于圖中所有邊權值進行從小到大排序
int count = 0; for(int i = 0;i < A.length;i++) { int a = A[i].a; int b = A[i].b; int ida = find(id, a - 1); int idb = find(id, b - 1); if(ida != idb) {
list.add(A[i]);
count++;
union(id, a - 1, b - 1);
} //輸出每一次添加完一條邊后的所有頂點id值
for(int j = 0;j < id.length;j++)
System.out.print(id[j]+" ");
System.out.println();
if(count >= n - 1) break;
} return list;
}
public static void main(String[] args){
Kruskal test = new Kruskal();
Scanner in = new Scanner(System.in);
System.out.println("請輸入頂點數(shù)a和具體邊數(shù)p："); int n = in.nextInt(); int p = in.nextInt();
edge[] A = new edge[p];
System.out.println("請依次輸入具體邊對于的頂點和權值："); for(int i = 0;i < p;i++) { int a = in.nextInt(); int b = in.nextInt(); int value = in.nextInt();
A[i] = test.new edge(a, b, value);
}
ArrayList<edge> list = test.getMinSpanTree(n, A);
System.out.println("使用Kruskal算法得到的最小生成樹具體邊和權值分別為："); for(int i = 0;i < list.size();i++) {
System.out.println(list.get(i).a+"——>"+list.get(i).b+", "+list.get(i).value);
}
}
}
運行結果：
請輸入頂點數(shù)a和具體邊數(shù)p：5 7請依次輸入具體邊對于的頂點和權值：1 2 5 2 3 5 2 4 12 3 4 17 2 5 15 3 5 6 4 5 12 -1 2 -2 -1 -1 2 2 -3 -1 -1 2 2 -4 -1 2 2 2 -5 2 2 使用Kruskal算法得到的最小生成樹具體邊和權值分別為：2——>3, 5 1——>2, 5 3——>5, 6 4——>5, 12
延伸閱讀
- 珊珊老師——北京IT機構十年一線教學經(jīng)驗 2024-08-28
- 向著Java前進 2023-04-15
- 云筆記 2022-07-13
- 2021年Java程序員的就業(yè)前景如何？ 2022-02-17
- 感謝萬碼，我認識到了java的魅力 2021-05-23
- 今天我成為了Java工程師 2021-05-23
- 我的JAVA生涯 ——解*泉 2020-01-15
- 以java為劍，仗劍走江湖—尚*權 2019-12-22
- 開啟我的java征途——鄭*亮 2019-11-06
- 我想這就是Java工程師的工作——劉*聰 2019-07-05
珊珊老師——北京IT機構十年一線教學經(jīng)驗