快捷導(dǎo)航

Java實(shí)現(xiàn)Kruskal算法的示例代碼

更新時(shí)間：2022年07月11日 10:18:59 作者：chengqiuming

Kruskal算法是一種用來(lái)尋找最小生成樹的算法，由Joseph Kruskal在1956年發(fā)表。用來(lái)解決同樣問(wèn)題的還有Prim算法和Boruvka算法等。本文將介紹用Java語(yǔ)言實(shí)現(xiàn)Kruskal算法的示例代碼，需要的可以參考一下

介紹

構(gòu)造最小生成樹還有一種算法，即 Kruskal 算法：設(shè)圖 G=（V，E）是無(wú)向連通帶權(quán)圖，V={1,2，...n};設(shè)最小生成樹 T=(V，TE)，該樹的初始狀態(tài)只有 n 個(gè)節(jié)點(diǎn)而無(wú)邊的非連通圖T=(V,{}),Kruskal 算法將這n 個(gè)節(jié)點(diǎn)看成 n 個(gè)孤立的連通分支。它首先將所有邊都按權(quán)值從小到大排序，然后值要在 T 中選的邊數(shù)不到 n-1,就做這樣貪心選擇：在邊集 E 中選擇權(quán)值最小的邊(i,j),如果將邊(i,j)加入集合 TE 中不產(chǎn)生回路，則將邊(i,j)加入邊集 TE 中，即用邊(i，j)將這兩個(gè)分支合并成一個(gè)連通分支；否則繼續(xù)選擇下一條最短邊。把邊(i,j)從集合 E 中刪去，繼續(xù)上面的貪心選擇，直到 T 中的所有節(jié)點(diǎn)都在同一個(gè)連通分支上為止。此時(shí)，選取的 n-1 條邊恰好構(gòu)成圖 G 的一棵最小生成樹 T。

Kruskal 算法用一種非常聰明的方法，就是運(yùn)用集合避圈；如果所選擇加入邊的起點(diǎn)和終點(diǎn)都在 T 集合中，就可以斷定會(huì)形成回路，變的兩個(gè)節(jié)點(diǎn)不能屬于同一個(gè)集合。

算法步驟

1 初始化。將所有邊都按權(quán)值從小到大排序，將每個(gè)節(jié)點(diǎn)集合號(hào)都初始化為自身編號(hào)。

2 按排序后的順序選擇權(quán)值最小的邊（u,v）。

3 如果節(jié)點(diǎn) u 和 v 屬于兩個(gè)不同的連通分支，則將邊(u,v)加入邊集 TE 中，并將兩個(gè)連通分支合并。

4 如果選取的邊數(shù)小于 n-1,則轉(zhuǎn)向步驟2，否則算法結(jié)束。

一、構(gòu)建后的圖

二、代碼

package graph.kruskal;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Kruskal {
    static final int N = 100;
    static int fa[] = new int[N];
    static int n;
    static int m;
 
    static Edge e[] = new Edge[N * N];
    static List<Edge> edgeList = new ArrayList();
 
    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }
 
    // 初始化集合號(hào)為自身
    static void Init(int n) {
        for (int i = 1; i <= n; i++)
            fa[i] = i;
    }
 
    // 合并
    static int Merge(int a, int b) {
        int p = fa[a];
        int q = fa[b];
        if (p == q) return 0;
        for (int i = 1; i <= n; i++) { // 檢查所有結(jié)點(diǎn)，把集合號(hào)是 q 的改為 p
            if (fa[i] == q)
                fa[i] = p; // a 的集合號(hào)賦值給 b 集合號(hào)
        }
        return 1;
    }
 
    // 求最小生成樹
    static int Kruskal(int n) {
        int ans = 0;
        Collections.sort(edgeList);
        for (int i = 0; i < m; i++)
            if (Merge(edgeList.get(i).u, edgeList.get(i).v) == 1) {
                ans += edgeList.get(i).w;
                n--;
                if (n == 1)//n-1次合并算法結(jié)束
                    return ans;
            }
        return 0;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        Init(n);
        for (int i = 1; i <= m; i++) {
            e[i].u = scanner.nextInt();
            e[i].v = scanner.nextInt();
            e[i].w = scanner.nextInt();
            edgeList.add(e[i]);
        }
        System.out.println("最小的花費(fèi)是：" + Kruskal(n));
    }
}
 
class Edge implements Comparable {
    int u;
    int w;
    int v;
 
    @Override
    public int compareTo(Object o) {
        if (this.w > ((Edge) o).w) {
            return 1;
        } else if (this.w == ((Edge) o).w) {
            return 0;
        } else {
            return -1;
        }
    }
}