摘要：最小生成樹(shù)有兩種生成算法普里姆算法克魯斯克爾算法算法普利姆算法算法流程我的理解任選一個(gè)元素，作為起始點(diǎn)將起始點(diǎn)標(biāo)記為，代表該點(diǎn)已經(jīng)加入最小生成樹(shù)集合計(jì)算這個(gè)集合到未加入的各個(gè)點(diǎn)的距離選擇一個(gè)最小的距離點(diǎn)，加入集合，即標(biāo)記為已訪問(wèn)更新集合到其

Prim（普里姆算法）

Kruskal（克魯斯克爾）算法

算法流程：（我的理解）

任選一個(gè)元素，作為起始點(diǎn)

將起始點(diǎn)標(biāo)記為visit，代表該點(diǎn)已經(jīng)加入最小生成樹(shù)集合

計(jì)算這個(gè)集合到未加入的各個(gè)點(diǎn)的距離

選擇一個(gè)最小的距離點(diǎn)，加入集合，即標(biāo)記為已訪問(wèn)

更新集合到其他各個(gè)點(diǎn)的最小距離

迭代

存疑

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

package com.edu.chapter03;

import org.junit.Test;

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

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

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

            join[pos] = 1; // 標(biāo)記為以加入最小生成樹(shù)集合
            weight += min;
 
            //重新計(jì)算集合距離其他點(diǎn)的距離
            for (int j = 1; j <= n; j++) {
                if (join[j] == 0 && dis[j] > e[pos][j]) { // 比較新加入的點(diǎn)是否帶來(lái)的更短的距離，
                    dis[j] = e[pos][j]; //有，則更新。保證dis里存儲(chǔ)的是到其他點(diǎn)的最近距離
                }
            }
        }
        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();
    }
}

算法思路

首先將圖中的邊按權(quán)重大小排序（從小到大）

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

取出一條邊，將邊對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)放入一個(gè)集合

如果集合中已經(jīng)存在這兩個(gè)點(diǎn)，則放棄該邊

不斷有邊加入，將不同的集合連起來(lái)，直到集合包含了所有節(jié)點(diǎn)，結(jié)束

每次有效添加的一條邊，代表了最小生成樹(shù)中對(duì)應(yīng)的邊，或者說(shuō)路徑