第十一章：圖論part07

今天在學(xué)習(xí)prim 和 kruskal的同時(shí)确丢，也要清楚這兩個(gè)算法的區(qū)別所在茫多。

prim算法精講

文章講解

思路

• 最小生成樹(shù)模板題
  最小生成樹(shù)是所有節(jié)點(diǎn)的最小連通子圖祈匙， 即：以最小的成本（邊的權(quán)值）將圖中所有節(jié)點(diǎn)鏈接到一起。
  圖中有n個(gè)節(jié)點(diǎn)天揖，那么一定可以用 n - 1 條邊將所有節(jié)點(diǎn)連接到一起夺欲。
  那么如何選擇 這 n-1 條邊 就是 最小生成樹(shù)算法的任務(wù)所在。

• prim算法 是從節(jié)點(diǎn)的角度 采用貪心的策略 每次尋找距離 最小生成樹(shù)最近的節(jié)點(diǎn) 并加入到最小生成樹(shù)中今膊。

• prim算法核心就是三步：
  第一步些阅，選距離生成樹(shù)最近節(jié)點(diǎn)
  第二步，最近節(jié)點(diǎn)加入生成樹(shù)
  第三步斑唬，更新非生成樹(shù)節(jié)點(diǎn)到生成樹(shù)的距離（即更新minDist數(shù)組）

• minDist數(shù)組：minDist數(shù)組 用來(lái)記錄 每一個(gè)節(jié)點(diǎn)距離最小生成樹(shù)的最近距離市埋。 理解這一點(diǎn)非常重要黎泣，這也是 prim算法最核心要點(diǎn)所在（示例中節(jié)點(diǎn)編號(hào)是從1開(kāi)始，minDist數(shù)組下標(biāo)也從 1 開(kāi)始計(jì)數(shù)腰素，下標(biāo)0 就不使用了聘裁，這樣 下標(biāo)和節(jié)點(diǎn)標(biāo)號(hào)就可以對(duì)應(yīng)上了)

1. 初始狀態(tài)

minDist 數(shù)組 里的數(shù)值初始化為 最大數(shù)，因?yàn)楸绢} 節(jié)點(diǎn)距離不會(huì)超過(guò) 10000弓千，所以 初始化最大數(shù)為 10001就可以衡便。
因?yàn)楝F(xiàn)在 還沒(méi)有最小生成樹(shù)，默認(rèn)每個(gè)節(jié)點(diǎn)距離最小生成樹(shù)是最大的洋访，這樣后面我們?cè)诒容^的時(shí)候镣陕，發(fā)現(xiàn)更近的距離，才能更新到 minDist 數(shù)組上姻政。
如圖：

image.png

開(kāi)始構(gòu)造最小生成樹(shù)

2

1呆抑、prim三部曲，第一步：選距離生成樹(shù)最近節(jié)點(diǎn)
選擇距離最小生成樹(shù)最近的節(jié)點(diǎn)汁展，加入到最小生成樹(shù)鹊碍，剛開(kāi)始還沒(méi)有最小生成樹(shù)，所以隨便選一個(gè)節(jié)點(diǎn)加入就好（因?yàn)槊恳粋€(gè)節(jié)點(diǎn)一定會(huì)在最小生成樹(shù)里食绿，所以隨便選一個(gè)就好）侈咕，那我們選擇節(jié)點(diǎn)1 （符合遍歷數(shù)組的習(xí)慣，第一個(gè)遍歷的也是節(jié)點(diǎn)1）

2器紧、prim三部曲耀销，第二步：最近節(jié)點(diǎn)加入生成樹(shù)
此時(shí) 節(jié)點(diǎn)1 已經(jīng)算最小生成樹(shù)的節(jié)點(diǎn)。

3铲汪、prim三部曲熊尉，第三步：更新非生成樹(shù)節(jié)點(diǎn)到生成樹(shù)的距離（即更新minDist數(shù)組）
接下來(lái)，我們要更新所有節(jié)點(diǎn)距離最小生成樹(shù)的距離掌腰，如圖：

image.png

此時(shí)所有非生成樹(shù)的節(jié)點(diǎn)距離 最小生成樹(shù)（節(jié)點(diǎn)1）的距離都已經(jīng)跟新了 。

• 節(jié)點(diǎn)2 與 節(jié)點(diǎn)1 的距離為1士飒，比原先的 距離值10001小，所以更新minDist[2]蔗崎。
• 節(jié)點(diǎn)3 和 節(jié)點(diǎn)1 的距離為1酵幕，比原先的 距離值10001小，所以更新minDist[3]缓苛。
• 節(jié)點(diǎn)5 和 節(jié)點(diǎn)1 的距離為2芳撒，比原先的 距離值10001小邓深，所以更新minDist[5]。

注意圖中標(biāo)記了 minDist數(shù)組里更新的權(quán)值笔刹，是哪兩個(gè)節(jié)點(diǎn)之間的權(quán)值芥备，例如 minDist[2] =1 ，這個(gè) 1 是 節(jié)點(diǎn)1 與 節(jié)點(diǎn)2 之間的連線舌菜，清楚這一點(diǎn)對(duì)最后我們記錄 最小生成樹(shù)的權(quán)值總和很重要萌壳。

3

1、prim三部曲日月，第一步：選距離生成樹(shù)最近節(jié)點(diǎn)
選取一個(gè)距離 最小生成樹(shù)（節(jié)點(diǎn)1） 最近的非生成樹(shù)里的節(jié)點(diǎn)袱瓮，節(jié)點(diǎn)2，3爱咬，5 距離 最小生成樹(shù)（節(jié)點(diǎn)1） 最近尺借，選節(jié)點(diǎn) 2（其實(shí)選 節(jié)點(diǎn)3或者節(jié)點(diǎn)2都可以，距離一樣的）加入最小生成樹(shù)精拟。

2燎斩、prim三部曲，第二步：最近節(jié)點(diǎn)加入生成樹(shù)
此時(shí) 節(jié)點(diǎn)1 和 節(jié)點(diǎn)2蜂绎，已經(jīng)算最小生成樹(shù)的節(jié)點(diǎn)栅表。

3、prim三部曲荡碾，第三步：更新非生成樹(shù)節(jié)點(diǎn)到生成樹(shù)的距離（即更新minDist數(shù)組）
接下來(lái)谨读，我們要更新節(jié)點(diǎn)距離最小生成樹(shù)的距離，如圖：

image.png

• 節(jié)點(diǎn)3 和 節(jié)點(diǎn)2 的距離為2，和原先的距離值1 小拨脉，所以不用更新哆姻。
• 節(jié)點(diǎn)4 和 節(jié)點(diǎn)2 的距離為2，比原先的距離值10001小玫膀，所以更新minDist[4]矛缨。
• 節(jié)點(diǎn)5 和 節(jié)點(diǎn)2 的距離為10001（不連接），所以不用更新帖旨。
• 節(jié)點(diǎn)6 和 節(jié)點(diǎn)2 的距離為1箕昭，比原先的距離值10001小，所以更新minDist[6]解阅。

4

1落竹、prim三部曲，第一步：選距離生成樹(shù)最近節(jié)點(diǎn)
選擇一個(gè)距離 最小生成樹(shù)（節(jié)點(diǎn)1货抄、節(jié)點(diǎn)2） 最近的非生成樹(shù)里的節(jié)點(diǎn)述召，節(jié)點(diǎn)3朱转，6 距離 最小生成樹(shù)（節(jié)點(diǎn)1、節(jié)點(diǎn)2） 最近积暖，選節(jié)點(diǎn)3 （選節(jié)點(diǎn)6也可以藤为，距離一樣）加入最小生成樹(shù)。

2夺刑、prim三部曲缅疟，第二步：最近節(jié)點(diǎn)加入生成樹(shù)
此時(shí) 節(jié)點(diǎn)1 、節(jié)點(diǎn)2 性誉、節(jié)點(diǎn)3 算是最小生成樹(shù)的節(jié)點(diǎn)窿吩。

3、prim三部曲错览，第三步：更新非生成樹(shù)節(jié)點(diǎn)到生成樹(shù)的距離（即更新minDist數(shù)組）
接下來(lái)更新節(jié)點(diǎn)距離最小生成樹(shù)的距離纫雁，如圖：

image.png

• 節(jié)點(diǎn) 4 和 節(jié)點(diǎn) 3的距離為 1，和原先的距離值 2 小羞海，所以更新minDist[3]為1忌愚。

因?yàn)楣?jié)點(diǎn)3加入 最小生成樹(shù)后，非 生成樹(shù)節(jié)點(diǎn) 只有 節(jié)點(diǎn) 4 和 節(jié)點(diǎn)3是鏈接的却邓，所以需要重新更新一下 節(jié)點(diǎn)4距離最小生成樹(shù)的距離硕糊，其他節(jié)點(diǎn)距離最小生成樹(shù)的距離 都不變。

然后重復(fù)這三步腊徙，分別把節(jié)點(diǎn)4简十、5、6加入撬腾，具體看文章
注意： minDist數(shù)組 是記錄了 所有非生成樹(shù)節(jié)點(diǎn)距離生成樹(shù)的最小距離螟蝙。
所以最后，minDist數(shù)組 也就是記錄的是最小生成樹(shù)所有邊的權(quán)值民傻。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int v = scanner.nextInt(); // 頂點(diǎn)數(shù)量
        int e = scanner.nextInt(); // 邊數(shù)量

        int x, y, k;
        // 初始化圖的鄰接矩陣胰默，填一個(gè)默認(rèn)最大值，題目描述val最大為10000
        int[][] grid = new int[v + 1][v + 1];
        for (int i = 1; i <= v; i++) {
            Arrays.fill(grid[i], 10001);
        }

        // 讀取每條邊的信息漓踢，填充鄰接矩陣
        while (e-- > 0) {
            x = scanner.nextInt();
            y = scanner.nextInt();
            k = scanner.nextInt();
            // 因?yàn)槭请p向圖牵署，所以?xún)蓚€(gè)方向都要填上
            grid[x][y] = k;
            grid[y][x] = k;
        }

        // 所有節(jié)點(diǎn)到最小生成樹(shù)的最小距離
        int[] minDist = new int[v + 1];
        Arrays.fill(minDist, 10001);

        // 這個(gè)節(jié)點(diǎn)是否在樹(shù)里
        boolean[] isInTree = new boolean[v + 1];

        // Prim算法：我們只需要循環(huán) v-1 次，建立 v-1 條邊喧半，就可以把 v 個(gè)節(jié)點(diǎn)的圖連在一起
        for (int i = 1; i < v; i++) {

            // 1碟刺、Prim三部曲，第一步：選距離生成樹(shù)最近的節(jié)點(diǎn)
            int cur = -1; // 選中哪個(gè)節(jié)點(diǎn) 加入最小生成樹(shù)
            int minVal = Integer.MAX_VALUE;
            for (int j = 1; j <= v; j++) { // 1 - v薯酝，頂點(diǎn)編號(hào)半沽，這里下標(biāo)從1開(kāi)始
                // 選取最小生成樹(shù)節(jié)點(diǎn)的條件：
                // （1）不在最小生成樹(shù)里
                // （2）距離最小生成樹(shù)最近的節(jié)點(diǎn)
                if (!isInTree[j] && minDist[j] < minVal) {
                    minVal = minDist[j];
                    cur = j;
                }
            }

            // 2、Prim三部曲吴菠，第二步：最近節(jié)點(diǎn)（cur）加入生成樹(shù)
            isInTree[cur] = true;

            // 3者填、Prim三部曲，第三步：更新非生成樹(shù)節(jié)點(diǎn)到生成樹(shù)的距離（即更新minDist數(shù)組）
            for (int j = 1; j <= v; j++) {
                // 更新的條件：
                // （1）節(jié)點(diǎn)是非生成樹(shù)里的節(jié)點(diǎn)
                // （2）與cur相連的某節(jié)點(diǎn)的權(quán)值 比該某節(jié)點(diǎn)距離最小生成樹(shù)的距離小
                if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                    minDist[j] = grid[cur][j];
                }
            }
        }

        // 統(tǒng)計(jì)結(jié)果
        int result = 0;
        for (int i = 2; i <= v; i++) { // 不計(jì)第一個(gè)頂點(diǎn)做葵，因?yàn)榻y(tǒng)計(jì)的是邊的權(quán)值占哟，v個(gè)節(jié)點(diǎn)有 v-1 條邊
            result += minDist[i];
        }
        System.out.println(result);
    }
}

拓展

上面講解的是記錄了最小生成樹(shù) 所有邊的權(quán)值，如果讓打印出來(lái) 最小生成樹(shù)的每條邊呢酿矢？ 或者說(shuō) 要把這個(gè)最小生成樹(shù)畫(huà)出來(lái)呢榨乎？

此時(shí)我們就需要把 最小生成樹(shù)里每一條邊記錄下來(lái)。

此時(shí)有兩個(gè)問(wèn)題：

1瘫筐、用什么結(jié)構(gòu)來(lái)記錄
2蜜暑、如何記錄
如果記錄邊，其實(shí)就是記錄兩個(gè)節(jié)點(diǎn)就可以策肝，兩個(gè)節(jié)點(diǎn)連成一條邊肛捍。

如何記錄兩個(gè)節(jié)點(diǎn)呢？

我們使用一維數(shù)組就可以記錄之众。 parent[節(jié)點(diǎn)編號(hào)] = 節(jié)點(diǎn)編號(hào)拙毫， 這樣就把一條邊記錄下來(lái)了。（當(dāng)然如果節(jié)點(diǎn)編號(hào)非常大棺禾，可以考慮使用map）

使用一維數(shù)組記錄是有向邊缀蹄，不過(guò)我們這里不需要記錄方向，所以只關(guān)注兩條邊是連接的就行膘婶。

根據(jù) minDist數(shù)組：選擇距離 生成樹(shù) 最近的節(jié)點(diǎn) 加入生成樹(shù)缺前，那么 minDist數(shù)組里記錄的其實(shí)也是 最小生成樹(shù)的邊的權(quán)值。

既然 minDist數(shù)組 記錄了 最小生成樹(shù)的邊竣付，所以就是在更新 minDist數(shù)組 的時(shí)候诡延，去更新parent數(shù)組來(lái)記錄一下對(duì)應(yīng)的邊即可。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int v = scanner.nextInt(); // 頂點(diǎn)數(shù)量
        int e = scanner.nextInt(); // 邊數(shù)量

        int x, y, k;
        // 初始化圖的鄰接矩陣古胆，填一個(gè)默認(rèn)最大值肆良，題目描述val最大為10000
        int[][] grid = new int[v + 1][v + 1];
        for (int i = 1; i <= v; i++) {
            Arrays.fill(grid[i], 10001);
        }

        // 讀取每條邊的信息，填充鄰接矩陣
        while (e-- > 0) {
            x = scanner.nextInt();
            y = scanner.nextInt();
            k = scanner.nextInt();
            // 因?yàn)槭请p向圖逸绎，所以?xún)蓚€(gè)方向都要填上
            grid[x][y] = k;
            grid[y][x] = k;
        }

        int[] minDist = new int[v + 1]; // 所有節(jié)點(diǎn)到最小生成樹(shù)的最小距離
        Arrays.fill(minDist, 10001);

        boolean[] isInTree = new boolean[v + 1]; // 這個(gè)節(jié)點(diǎn)是否在樹(shù)里

        int[] parent = new int[v + 1]; // 記錄最小生成樹(shù)的邊
        Arrays.fill(parent, -1); // 初始化 parent 數(shù)組

        // Prim算法：我們只需要循環(huán) v-1 次惹恃，建立 v-1 條邊，就可以把 v 個(gè)節(jié)點(diǎn)的圖連在一起
        for (int i = 1; i < v; i++) {
            int cur = -1; // 選中哪個(gè)節(jié)點(diǎn)加入最小生成樹(shù)
            int minVal = Integer.MAX_VALUE;

            // 選距離生成樹(shù)最近的節(jié)點(diǎn)
            for (int j = 1; j <= v; j++) {
                if (!isInTree[j] && minDist[j] < minVal) {
                    minVal = minDist[j];
                    cur = j;
                }
            }

            isInTree[cur] = true; // 最近節(jié)點(diǎn)（cur）加入生成樹(shù)

            // 更新非生成樹(shù)節(jié)點(diǎn)到生成樹(shù)的距離（即更新minDist數(shù)組）
            for (int j = 1; j <= v; j++) {
                if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                    minDist[j] = grid[cur][j];
                    parent[j] = cur; // 記錄最小生成樹(shù)的邊
                }
            }
        }

        // 輸出最小生成樹(shù)邊的鏈接情況
        for (int i = 1; i <= v; i++) {
            if (parent[i] != -1) { // 跳過(guò)根節(jié)點(diǎn)
                System.out.println(i + " -> " + parent[i]);
            }
        }
    }
}

數(shù)組指向的順序很重要棺牧。 因?yàn)椴簧黉浻言谶@里會(huì)寫(xiě)成這樣： parent[cur] = j 巫糙。

這里估計(jì)大家會(huì)疑惑了，parent[節(jié)點(diǎn)編號(hào)A] = 節(jié)點(diǎn)編號(hào)B颊乘， 就表示A 和 B 相連参淹，我們這里就不用在意方向醉锄，代碼中 為什么 只能 parent[j] = cur 而不能 parent[cur] = j 這么寫(xiě)呢？

如果寫(xiě)成 parent[cur] = j浙值，在 for 循環(huán)中恳不，有多個(gè) j 滿(mǎn)足要求， 那么 parent[cur] 就會(huì)被反復(fù)覆蓋开呐，因?yàn)?cur 是一個(gè)固定值烟勋。

舉個(gè)例子，cur = 1筐付， 在 for循環(huán)中卵惦，可能 就 j = 2， j = 3瓦戚，j =4 都符合條件沮尿，那么本來(lái)應(yīng)該記錄 節(jié)點(diǎn)1 與 節(jié)點(diǎn) 2、節(jié)點(diǎn)3伤极、節(jié)點(diǎn)4相連的蛹找。

如果 parent[cur] = j 這么寫(xiě)，最后更新的邏輯是 parent[1] = 2, parent[1] = 3哨坪， parent[1] = 4庸疾， 最后只能記錄 節(jié)點(diǎn)1 與節(jié)點(diǎn) 4 相連，其他相連情況都被覆蓋了当编。

如果這么寫(xiě) parent[j] = cur届慈， 那就是 parent[2] = 1, parent[3] = 1， parent[4] = 1 忿偷，這樣 才能完整表示出 節(jié)點(diǎn)1 與 其他節(jié)點(diǎn)都是鏈接的金顿，才沒(méi)有被覆蓋。

主要問(wèn)題也是我們使用了一維數(shù)組來(lái)記錄鲤桥。

如果是二維數(shù)組揍拆，來(lái)記錄兩個(gè)點(diǎn)鏈接，例如 parent[節(jié)點(diǎn)編號(hào)A][節(jié)點(diǎn)編號(hào)B] = 1 茶凳，parent[節(jié)點(diǎn)編號(hào)B][節(jié)點(diǎn)編號(hào)A] = 1嫂拴，來(lái)表示 節(jié)點(diǎn)A 與 節(jié)點(diǎn)B 相連，那就沒(méi)有上面說(shuō)的這個(gè)注意事項(xiàng)了贮喧，當(dāng)然這么做的話筒狠，就是多開(kāi)辟的內(nèi)存空間。

kruskal算法精講

文章講解

思路

• Kruskal箱沦，同樣可以求最小生成樹(shù)辩恼。

• prim 算法是維護(hù)節(jié)點(diǎn)的集合，而 Kruskal 是維護(hù)邊的集合。

kruscal的思路：

• 邊的權(quán)值排序灶伊，因?yàn)橐獌?yōu)先選最小的邊加入到生成樹(shù)里
• 遍歷排序后的邊
  • 如果邊首尾的兩個(gè)節(jié)點(diǎn)在同一個(gè)集合疆前，說(shuō)明如果連上這條邊圖中會(huì)出現(xiàn)環(huán)
  • 如果邊首尾的兩個(gè)節(jié)點(diǎn)不在同一個(gè)集合，加入到最小生成樹(shù)谁帕，并把兩個(gè)節(jié)點(diǎn)加入同一個(gè)集合

具體畫(huà)圖峡继，看代碼隨想錄。

如果將兩個(gè)節(jié)點(diǎn)加入同一個(gè)集合匈挖，又如何判斷兩個(gè)節(jié)點(diǎn)是否在同一個(gè)集合呢？
這里就涉及到并查集
并查集主要就兩個(gè)功能：

• 將兩個(gè)元素添加到一個(gè)集合中
• 判斷兩個(gè)元素在不在同一個(gè)集合

import java.util.*;

class Edge {
    int l, r, val;

    Edge(int l, int r, int val) {
        this.l = l;
        this.r = r;
        this.val = val;
    }
}

public class Main {

    // 節(jié)點(diǎn)數(shù)量
    static int n = 10001;
    // 并查集標(biāo)記節(jié)點(diǎn)關(guān)系的數(shù)組
    static int[] father = new int[n]; // 節(jié)點(diǎn)編號(hào)是從1開(kāi)始的康愤，n要大一些

    // 并查集初始化
    static void init() {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    // 并查集的查找操作
    static int find(int u) {
        if (u == father[u]) {
            return u;
        } else {
            father[u] = find(father[u]); // 路徑壓縮
            return father[u];
        }
    }

    // 并查集的加入集合
    static void join(int u, int v) {
        int rootU = find(u); // 尋找u的根
        int rootV = find(v); // 尋找v的根
        if (rootU != rootV) { // 如果根不同儡循，則將v的根連接到u的根上
            father[rootV] = rootU;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int v = sc.nextInt(); // 頂點(diǎn)數(shù)量
        int e = sc.nextInt(); // 邊數(shù)量

        List<Edge> edges = new ArrayList<>();
        int result_val = 0;

        for (int i = 0; i < e; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            int val = sc.nextInt();
            edges.add(new Edge(v1, v2, val));
        }

        // 執(zhí)行Kruskal算法
        // 按邊的權(quán)值對(duì)邊進(jìn)行從小到大排序
        edges.sort(Comparator.comparingInt(edge -> edge.val));

        // 并查集初始化
        init();

        // 從頭開(kāi)始遍歷邊
        for (Edge edge : edges) {
            // 并查集，搜出兩個(gè)節(jié)點(diǎn)的祖先
            int x = find(edge.l);
            int y = find(edge.r);

            // 如果祖先不同征冷，則不在同一個(gè)集合
            if (x != y) {
                result_val += edge.val; // 這條邊可以作為生成樹(shù)的邊
                join(x, y); // 兩個(gè)節(jié)點(diǎn)加入到同一個(gè)集合
            }
        }

        System.out.println(result_val);
    }
}

拓展一

如果題目要求將最小生成樹(shù)的邊輸出的話择膝，應(yīng)該怎么辦呢？

import java.util.*;

class Edge {
    int l, r, val;

    Edge(int l, int r, int val) {
        this.l = l;
        this.r = r;
        this.val = val;
    }
}

public class Main {

    static int n = 10001;
    static int[] father = new int[n]; 

    // 并查集初始化
    static void init() {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    // 并查集的查找操作
    static int find(int u) {
        if (u == father[u]) {
            return u;
        } else {
            father[u] = find(father[u]); // 路徑壓縮
            return father[u];
        }
    }

    // 并查集的加入集合
    static void join(int u, int v) {
        int rootU = find(u); // 尋找u的根
        int rootV = find(v); // 尋找v的根
        if (rootU != rootV) { // 如果根不同检激，則將v的根連接到u的根上
            father[rootV] = rootU;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int v = sc.nextInt(); // 頂點(diǎn)數(shù)量
        int e = sc.nextInt(); // 邊數(shù)量

        List<Edge> edges = new ArrayList<>();
        int result_val = 0;

        // 讀取所有的邊信息
        for (int i = 0; i < e; i++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            int val = sc.nextInt();
            edges.add(new Edge(v1, v2, val));
        }

        // 按照邊的權(quán)值升序排序
        edges.sort(Comparator.comparingInt(edge -> edge.val));

        List<Edge> result = new ArrayList<>(); // 存儲(chǔ)最小生成樹(shù)的邊

        // 并查集初始化
        init();

        // 遍歷排序后的邊
        for (Edge edge : edges) {
            int x = find(edge.l);
            int y = find(edge.r);

            // 如果祖先不同肴捉，則不在同一個(gè)集合
            if (x != y) {
                result.add(edge); // 保存最小生成樹(shù)的邊
                result_val += edge.val; // 這條邊可以作為生成樹(shù)的邊
                join(x, y); // 兩個(gè)節(jié)點(diǎn)加入到同一個(gè)集合
            }
        }

        // 打印最小生成樹(shù)的邊
        for (Edge edge : result) {
            System.out.println(edge.l + " - " + edge.r + " : " + edge.val);
        }

        sc.close();
    }
}

代碼解析

1. Edge 類(lèi)：

   • 用于存儲(chǔ)每條邊的兩個(gè)節(jié)點(diǎn)（l 和 r）以及權(quán)值（val）。

2. 并查集的操作：

   • init() 方法：初始化 father 數(shù)組叔收，每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)初始為自身齿穗。
   • find(int u) 方法：查找節(jié)點(diǎn) u 的根，并使用路徑壓縮優(yōu)化查詢(xún)饺律。
   • join(int u, int v) 方法：將節(jié)點(diǎn) u 和 v 合并到同一個(gè)集合中窃页。

3. Kruskal算法：

   • 讀取輸入的邊信息，并將它們存儲(chǔ)在 edges 列表中复濒。
   • 對(duì) edges 列表按照邊的權(quán)值進(jìn)行排序脖卖。
   • 遍歷排序后的邊，并使用并查集檢查每條邊是否可以加入最小生成樹(shù)巧颈。

4. 記錄最小生成樹(shù)的邊：

   • 使用 result 列表來(lái)存儲(chǔ)最小生成樹(shù)中的邊畦木。
   • 在每次成功加入一條邊到生成樹(shù)時(shí)，將該邊添加到 result 列表中砸泛。

5. 輸出最小生成樹(shù)的邊：

   • 遍歷 result 列表十籍，輸出每條邊的兩個(gè)節(jié)點(diǎn)及其權(quán)值，格式為 l - r : val晾嘶。

示例輸出

根據(jù)題目要求妓雾，代碼會(huì)輸出最小生成樹(shù)中的每條邊及其權(quán)值。例如：

1 - 2 : 1
1 - 3 : 1
2 - 6 : 1
3 - 4 : 1
4 - 5 : 1
5 - 7 : 1

該 Java 代碼實(shí)現(xiàn)了 Kruskal 算法垒迂，并能夠輸出最小生成樹(shù)的所有邊和它們的權(quán)值械姻。

拓展二

此時(shí)我們已經(jīng)講完了 Kruskal 和 prim 兩個(gè)解法來(lái)求最小生成樹(shù)。

什么情況用哪個(gè)算法更合適呢。

Kruskal 與 prim 的關(guān)鍵區(qū)別在于楷拳，prim維護(hù)的是節(jié)點(diǎn)的集合绣夺，而 Kruskal 維護(hù)的是邊的集合。 如果 一個(gè)圖中欢揖，節(jié)點(diǎn)多陶耍，但邊相對(duì)較少，那么使用Kruskal 更優(yōu)她混。

所以在 稀疏圖中烈钞，用Kruskal更優(yōu)。 在稠密圖中坤按，用prim算法更優(yōu)毯欣。

邊數(shù)量較少為稀疏圖，接近或等于完全圖（所有節(jié)點(diǎn)皆相連）為稠密圖

Prim 算法 時(shí)間復(fù)雜度為 O(n^2)臭脓，其中 n 為節(jié)點(diǎn)數(shù)量酗钞，它的運(yùn)行效率和圖中邊樹(shù)無(wú)關(guān)，適用稠密圖来累。

Kruskal算法 時(shí)間復(fù)雜度 為 nlogn砚作，其中n 為邊的數(shù)量，適用稀疏圖嘹锁。