摘要：最小生成樹有兩種生成算法普里姆算法克魯斯克爾算法算法普利姆算法算法流程我的理解任選一個元素，作為起始點將起始點標記為，代表該點已經加入最小生成樹集合計算這個集合到未加入的各個點的距離選擇一個最小的距離點，加入集合，即標記為已訪問更新集合到其

Prim（普里姆算法）

Kruskal（克魯斯克爾）算法

算法流程：（我的理解）

任選一個元素，作為起始點

將起始點標記為visit，代表該點已經加入最小生成樹集合

計算這個集合到未加入的各個點的距離

選擇一個最小的距離點，加入集合，即標記為已訪問

更新集合到其他各個點的最小距離

迭代

存疑

- 目前沒有找到記錄下路徑的辦法，不知道是不是還沒理解到位

package com.edu.chapter03;

import org.junit.Test;

public class MinimumTree {
    /**
     * 最小生成樹
     */
    int n;
    int e[][];
    int dis[];

    public void createMinmumTree() {
        int pos = 1; // 從1節點開始，可以任意指定；pos 代表當前要加入最小生成樹集合的編號
        int join[] = new int[n + 1]; // 記錄各個點加入的情況
        int weight = 0;
        // 初始化最小生成樹集合與其他各個點的距離
        for (int i = 1; i <= n; i++) {
            dis[i] = i == pos ? 0 : e[pos][i];
        }

        for (int i = 2; i <= n; i++) { // 從尋找第二個點開始（并不是代表要把2號點添加進去）
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= n; j++) {
                if (join[j] == 0 && dis[j] !=0 && min > dis[j]) { // 找出集合距離未加入的點的最近邊及點;dis[j]!=0 表示跳過和自己的比較
                    min = dis[j];
                    pos = j; // 找到最小位置，下一個要加入的點就是這個點
                }
            }

            join[pos] = 1; // 標記為以加入最小生成樹集合
            weight += min;
 
            //重新計算集合距離其他點的距離
            for (int j = 1; j <= n; j++) {
                if (join[j] == 0 && dis[j] > e[pos][j]) { // 比較新加入的點是否帶來的更短的距離，
                    dis[j] = e[pos][j]; //有，則更新。保證dis里存儲的是到其他點的最近距離
                }
            }
        }
        System.out.println("weight:" + weight);
    }

    @Test
    public void test01() {
        n = 6;
        e = new int[n + 1][n + 1];
        dis = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    e[i][j] = 0;
                } else {
                    e[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        e[1][2] = e[2][1] = 2;
        e[1][3] = e[3][1] = 4;
        e[1][4] = e[4][1] = 7;

        e[2][3] = e[3][2] = 1;
        e[2][5] = e[5][2] = 2;

        e[3][4] = e[4][3] = 1;
        e[3][5] = e[5][3] = 6;
        createMinmumTree();
    }
}

算法思路

首先將圖中的邊按權重大小排序（從小到大）

可以使用快速排序或者堆排序

取出一條邊，將邊對應的兩個節點放入一個集合

如果集合中已經存在這兩個點，則放棄該邊

不斷有邊加入，將不同的集合連起來，直到集合包含了所有節點，結束

每次有效添加的一條邊，代表了最小生成樹中對應的邊，或者說路徑