引言

現(xiàn)在假設(shè)有一個(gè)很實(shí)際的問(wèn)題：我們要在n個(gè)城市中建立一個(gè)通信網(wǎng)絡(luò)，則連通這n個(gè)城市需要布置n-1一條通信線路，這個(gè)時(shí)候我們需要考慮如何在成本最低的情況下建立這個(gè)通信網(wǎng)？
于是我們就可以引入連通圖來(lái)解決我們遇到的問(wèn)題，n個(gè)城市就是圖上的n個(gè)頂點(diǎn)，然后，邊表示兩個(gè)城市的通信線路，每條邊上的權(quán)重就是我們搭建這條線路所需要的成本，所以現(xiàn)在我們有n個(gè)頂點(diǎn)的連通網(wǎng)可以建立不同的生成樹(shù)，每一顆生成樹(shù)都可以作為一個(gè)通信網(wǎng)，當(dāng)我們構(gòu)造這個(gè)連通網(wǎng)所花的成本最小時(shí)，搭建該連通網(wǎng)的生成樹(shù)，就稱為最小生成樹(shù)。

最小生成樹(shù)算法思路

構(gòu)造最小生成樹(shù)有很多算法，但是他們都是利用了最小生成樹(shù)的同一種性質(zhì)：MST性質(zhì):假設(shè)圖N=(V,E)是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集，如果（u，v）是一條具有最小權(quán)值的邊，其中u屬于U，v屬于V-U，則必定存在一顆包含邊（u，v）的最小生成樹(shù)，今天我們學(xué)習(xí)使用MST性質(zhì)生成最小生成樹(shù)的算法:普里姆算法。
普里姆算法的關(guān)鍵就是尋找集合U 和V-U之間的最小權(quán)邊(u,v)，然后把v頂點(diǎn)加入U(xiǎn),它把頂點(diǎn)集分割成兩部分，每一次操作就從V-U尋找頂點(diǎn)v,把它放到集合U中，這樣保證生成樹(shù)沒(méi)有回環(huán)，俗稱"避圈法"。實(shí)現(xiàn)流程如下:
1.原始圖:

2.假設(shè)我們從頂點(diǎn)v1開(kāi)始，所以我們可以發(fā)現(xiàn)（v1,v3）邊的權(quán)重最小，所以第一個(gè)輸出的邊就是：(v1,v3):

5.從v1、v3、v6、v4這四個(gè)頂點(diǎn)相關(guān)聯(lián)的邊中尋找權(quán)重最小的邊，發(fā)現(xiàn)邊(v3, v2)的權(quán)重最小，所以輸出邊：(v3, v2):

代碼實(shí)現(xiàn)

package graphic;

/**
 * Created by chenming on 2018/6/18
 * 最小生成樹(shù)算法-普利姆算法
 */
public class Prim {
    private int[][] map;
    //V-U集合中距離U集合中頂點(diǎn)最近的點(diǎn)，如closest[j] = i,
    // 表示j距離U集合最近的頂點(diǎn)為i,在最小樹(shù)中，i為j的前驅(qū)
    private int[] closest;
    private int[] lowcost;//V-U集合中距離U最近頂點(diǎn)的邊長(zhǎng)(j, closest[j])
    private boolean[] s;//標(biāo)記是否添加到集合U

    public Prim(int[][] map) {
        this.map = map;
        int size = map.length;
        closest = new int[size];
        lowcost = new int[size];
        s = new boolean[size];
    }


    /**
     * 構(gòu)造最小生成樹(shù)
     *
     * @param u0 起點(diǎn)頂點(diǎn)
     */
    public void prim(int u0) {
        int n = map.length;
        //Step1初始化
        s[u0] = true;//u0加入集合
        for (int i = 0; i < n; i++) {
            if (i != u0) {
                lowcost[i] = map[u0][i];
                closest[i] = u0;
            } else {
                lowcost[i] = 0;
                closest[i] = -1;//-1表示沒(méi)有前驅(qū)
            }
        }

        //Step2 S-U中尋找距離U最小的頂點(diǎn)t，加入集合,更新lowcost和closest
        for (int i = 0; i < n; i++) {
            //尋找
            int min = Integer.MAX_VALUE;
            //找最小權(quán)邊頂點(diǎn)t
            int t = u0;
            for (int j = 0; j < n; j++) {
                if (!s[j] && lowcost[j] < min) {
                    t = j;
                    min = lowcost[j];
                }
            }

            //加入集合
            if (t == u0) {//沒(méi)找到最小值，跳出循環(huán)
                break;
            }
            s[t] = true;
            //更新lowcost和closest,從最小頂點(diǎn)t出發(fā)，如果它的鄰接頂點(diǎn)j的邊權(quán)小于lowcost[j],則更新lowcost和closest
            for (int j = 0; j < n; j++) {
                if (!s[j] && map[t][j] < lowcost[j]) {
                    lowcost[j] = map[t][j];
                    closest[j] = t;
                }
            }

        }

        //輸出結(jié)果
        dumpResult();
    }

    /**
     * 輸出邊和頂點(diǎn)即可
     */
    private void dumpResult() {
        System.out.println("======最小樹(shù)結(jié)構(gòu)======");
        for (int i = 0; i < lowcost.length; i++) {
            System.out.println("頂點(diǎn)" + i + "的前驅(qū):" + closest[i]);
        }
        System.out.println("======最小樹(shù)權(quán)值======");
        for (int i = 0; i < lowcost.length; i++) {
            System.out.println("權(quán)值:" + lowcost[i]);
        }
    }
}

測(cè)試代碼:

 @Test
    public void testPrim() {
        int INF = Integer.MAX_VALUE;
        int[][] map = {
                {INF, 23, INF, INF, INF, 28, 36},
                {23, INF, 20, INF, INF, INF, 1},
                {INF, 20, INF, 15, INF, INF, 4},
                {INF, INF, 15, INF, 3, INF, 9},
                {INF, INF, INF, 3, INF, 17, 16},
                {28, INF, INF, INF, 17, INF, 25},
                {36, 1, 4, 9, 16, 25, INF}
        };

        Prim prim = new Prim(map);
        prim.prim(0);
    }

測(cè)試結(jié)果:

======最小樹(shù)結(jié)構(gòu)======
頂點(diǎn)0的前驅(qū):-1
頂點(diǎn)1的前驅(qū):0
頂點(diǎn)2的前驅(qū):6
頂點(diǎn)3的前驅(qū):6
頂點(diǎn)4的前驅(qū):3
頂點(diǎn)5的前驅(qū):4
頂點(diǎn)6的前驅(qū):1
======最小樹(shù)權(quán)值======
權(quán)值:0
權(quán)值:23
權(quán)值:4
權(quán)值:9
權(quán)值:3
權(quán)值:17
權(quán)值:1

完整代碼地址:數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)JAVA描述GayHub地址