Kruskal算法又被稱為“加邊法”，這種算法會(huì)將加權(quán)連通圖的最小生成樹看成具有V-1條邊的無環(huán)子圖，且邊的權(quán)重和最小。算法開始時(shí)，會(huì)按照權(quán)重的非遞減順序?qū)D中的邊排序，之后迭代的以貪婪的方式添加邊。

下面以下圖為例來講解Kruskal算法的過程：

Input:

6 10
1 2 3
1 5 6
1 6 5
2 6 5
2 3 1
3 6 4
3 4 6
4 6 5
4 5 8

5 6 2

Output:

15

完整代碼如下：

import java.util.Scanner;class edge {int u, v, w;edge(int u, int v, int w) {this.u = u;this.v = v;this.w = w;} } public class Main {static edge[] e = new edge[11];static int n, m;static int[] f = new int[7];static int sum = 0;static int count = 0;static Scanner input = new Scanner(System.in);public static void main(String[] args) {n = input.nextInt();m = input.nextInt();for (int i = 1; i <= m; i++) {int a = input.nextInt();int b = input.nextInt();int c = input.nextInt();e[i] = new edge(a, b, c);}/*** 按權(quán)值排序* */quicksort(e, 1, m);for (int i = 1; i <= n; i++) {f[i] = i;}kruskal();System.out.println(sum);}private static void kruskal() {/*** 從小到大枚舉每一條邊* */for (int i = 1; i <= m; i++) {/*** 檢查一條邊的兩個(gè)頂點(diǎn)是否已經(jīng)連通，即判斷是否在同一個(gè)集合中* */if (merge(e[i].u, e[i].v)) {count++;sum = sum + e[i].w;}/*** 選到n-1邊之后，退出循環(huán)* */if (count == n - 1) {break;}}}public static int partition(edge[] a, int p, int q) {int x = a[p].w;int i = p;for (int j = p+1; j <= q; j++) {if (a[j].w <= x) {i += 1;edge temp = a[i];a[i] = a[j];a[j] = temp;}}edge temp = a[p];a[p] = a[i];a[i] = temp;return i;}public static void quicksort(edge[] a,int p, int q) {if (p < q) {int r = partition(a ,p ,q);quicksort(a, p, r - 1);quicksort(a, r + 1, q);}}private static int getf(int v) {if (f[v] == v) {return v;} else {/*** 壓縮路徑，每次函數(shù)返回時(shí)，將該位置的編號(hào)轉(zhuǎn)成祖宗編號(hào)* */f[v] = getf(f[v]);return f[v];}}private static boolean merge(int v, int u) {int t1 = getf(v);int t2 = getf(u);/*** 判斷祖先是否相同* */if (t1 != t2) {/*** 靠左原則* */f[t2] = t1;return true;}return false;} }Kruskal算法的時(shí)間復(fù)雜度主要取決于對(duì)圖中的邊進(jìn)行權(quán)值排序，如果排序算法效率比較高，那么Kruskal算法的時(shí)間復(fù)雜度為O(nlogn)

總結(jié)

以上是生活随笔為你收集整理的贪婪算法在求解最小生成树中的应用（JAVA）--Kruskal算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。