最小生成樹(shù)

• 連通圖：圖的連通其實(shí)就是樹(shù)，圖的最小連通圖其實(shí)就是最小生成樹(shù)钉疫。

• 樹(shù)：如果一個(gè)無(wú)向連通圖中不存在回路豁状，則這種圖稱為樹(shù)。
• 生成樹(shù)：無(wú)向連通圖G的一個(gè)子圖如果是一顆包含G的所有頂點(diǎn)的樹(shù)鸳君，則該子圖稱為G的生成樹(shù)农渊。
• 最小生成樹(shù)：或者稱為最小代價(jià)樹(shù)，對(duì)無(wú)向連通圖的生成樹(shù)或颊，各邊的權(quán)值總和稱為生成樹(shù)的權(quán)腿时，權(quán)最小的生成樹(shù)稱為最小生成樹(shù)。

最小生成樹(shù).png

最小生成樹(shù)2.png

• 一個(gè)連通圖的生成樹(shù)是一個(gè)極小的連通子圖饭宾，它含有圖中全部的頂點(diǎn)批糟，但只有足以構(gòu)成一棵樹(shù)的n-1條邊。我們把構(gòu)造連通網(wǎng)的最小代價(jià)生成樹(shù)看铆。稱為最小生成樹(shù)徽鼎。
• 找連通網(wǎng)的最小生成樹(shù)，經(jīng)典的有兩種算法弹惦，普里姆算法和克魯斯卡爾算法否淤。

普里姆算法

• 普里姆算法：

#代表無(wú)限大


假設(shè)以v0為基準(zhǔn)開(kāi)始，探測(cè)v0到各個(gè)頂點(diǎn)的距離：
v0
0, 10, #, #, #, 11, #, #, #
看到v0到v1的距離最短為10.

接下來(lái)我們要把v1加到基準(zhǔn)里棠隐。以v0和v1為基準(zhǔn)石抡，探測(cè)到各個(gè)頂點(diǎn)的距離：
v0，v1
0, 0, 18, #, #, 11, 16, #, 12
看到到v8的舉例最短為12.
這個(gè)過(guò)程前會(huì)把v0到各個(gè)頂點(diǎn)的距離和v1到各個(gè)頂點(diǎn)的距離作比較助泽，小的留下啰扛。
=======>

v0
0, 10, #, #, #, 11, #, #, #
v1
10, 0, 18, #, #, #, 16, #, 12
可以看到相同位置的元素嚎京，18比#小，11比16小隐解，12比#小鞍帝。替換后：

v0，v1
0, 0, 18, #, #, 11, 16, #, 12

=======>

就是這樣不斷尋找基準(zhǔn)距離最短的頂點(diǎn)煞茫，將其加入基準(zhǔn)帕涌。然后再以基準(zhǔn)探測(cè)周圍舉例最短的點(diǎn)。一直到所有頂點(diǎn)都找完续徽！

圖的深度優(yōu)先遍歷.png

package com.cx.graphdemo;

public class Graph {

    private int vertexSize; // 頂點(diǎn)數(shù)量
    private int[] vertexs; // 頂點(diǎn)數(shù)組
    private int[][] matrix; // 鄰接矩陣
    private static final int MAX_WEIGHT = 1000;
    private boolean[] isVisited; // 是否被訪問(wèn)過(guò)

    public Graph(int vertexSize) {
        this.vertexSize = vertexSize;
        vertexs = new int[vertexSize];
        matrix = new int[vertexSize][vertexSize];

        for (int i = 0; i < vertexSize; i++) {
            vertexs[i] = i;
        }

        isVisited = new boolean[vertexSize];
    }

    /**
     * prim 普里姆算法
     */
    public void prim() {
        // 最小代價(jià)頂點(diǎn)權(quán)值的數(shù)組,為0表示已經(jīng)獲取最小權(quán)值
        int[] lowcost = new int[vertexSize];
        // 放頂點(diǎn)權(quán)值
        int[] adjvex = new int[vertexSize];
        int min, minId, sum = 0;

        // 把v0數(shù)組賦值給lowcost
        for (int i = 1; i < vertexSize; i++) {
            lowcost[i] = matrix[0][i];
        }

        // 只是單純的循環(huán)蚓曼，除此之外沒(méi)有任何用處
        for (int i = 1; i < vertexSize; i++) {
            min = MAX_WEIGHT;
            minId = 0;

            // lowcost數(shù)組已更新，所以還要找出lowcost中最小的元素及下標(biāo)
            for (int j = 1; j < vertexSize; j++) {
                if (lowcost[j] < min && lowcost[j] > 0) {
                    min = lowcost[j];
                    minId = j;
                }
            }

            /**
             * 為什么要找到最小元素和下標(biāo)钦扭？<br>
             * 
             * 因?yàn)樽钚≡卮懋?dāng)前的已知頂點(diǎn)到其它頂點(diǎn)的最短路徑辟躏，我們要得到這個(gè)<br>
             * 最短路徑通向的頂點(diǎn)。然后周而復(fù)始土全。<br>
             * 
             * 核心思想:<br>
             * 
             * 從某一頂點(diǎn)開(kāi)始捎琐，找到該頂點(diǎn)周圍的最短路徑及此路徑通向的頂點(diǎn)。<br>
             * 以這兩個(gè)頂點(diǎn)為準(zhǔn)裹匙，找到這兩個(gè)頂點(diǎn)周圍的最短路徑及此路徑通向的頂點(diǎn)瑞凑。<br>
             * ......最終會(huì)通過(guò)這個(gè)"最短路徑算法"走完所有的頂點(diǎn)。
             */

            // System.out.println("頂點(diǎn)：" + adjvex[minId] + "權(quán)值：" + min);
            sum += min; // 加權(quán)重
            lowcost[minId] = 0;

            // 在v[minId]中找到比lowcost[]中同等位置小的值
            for (int j = 1; j < vertexSize; j++) {
                if (lowcost[j] != 0 && matrix[minId][j] < lowcost[j]) {
                    lowcost[j] = matrix[minId][j];
                    adjvex[j] = minId;
                }
            }
        }
        System.out.println("最小生成樹(shù)權(quán)值和:" + sum);
    }

    public static void main(String[] args) {
        Graph graph = new Graph(9);

        int[] a1 = new int[] { 0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
        int[] a2 = new int[] { 10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12 };
        int[] a3 = new int[] { MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8 };
        int[] a4 = new int[] { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, MAX_WEIGHT, 16, 21 };
        int[] a5 = new int[] { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT };
        int[] a6 = new int[] { 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT };
        int[] a7 = new int[] { MAX_WEIGHT, 16, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT };
        int[] a8 = new int[] { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT };
        int[] a9 = new int[] { MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0 };

        graph.matrix[0] = a1;
        graph.matrix[1] = a2;
        graph.matrix[2] = a3;
        graph.matrix[3] = a4;
        graph.matrix[4] = a5;
        graph.matrix[5] = a6;
        graph.matrix[6] = a7;
        graph.matrix[7] = a8;
        graph.matrix[8] = a9;

        graph.prim();
    }
}

克魯斯卡爾算法

克魯斯卡爾算法.png

普里姆算法是按頂點(diǎn)來(lái)連通圖概页，而克魯斯卡爾算法則是按邊來(lái)構(gòu)成圖籽御。

兩個(gè)頂點(diǎn)確立一條邊，沒(méi)有問(wèn)題惰匙！所有的邊可以從小到大排序技掏，也沒(méi)有問(wèn)題！
克魯斯卡爾算法就是按照這個(gè)順序排好的邊來(lái)連通圖项鬼。

規(guī)則：
1.找到最小的邊哑梳。
2.探測(cè)邊的兩個(gè)頂點(diǎn)是否會(huì)構(gòu)成回環(huán)。
3.如果構(gòu)成回環(huán)則放棄這條邊绘盟，尋找下一條鸠真。
4.如果不構(gòu)成回環(huán)，則記錄龄毡。再尋找下一條吠卷。

整個(gè)尋找過(guò)程，可以看下圖：一點(diǎn)點(diǎn)畫的沦零，一定能看懂祭隔！

注意：這里面有一個(gè)點(diǎn)。探測(cè)是否會(huì)構(gòu)成回環(huán)路操！克魯斯卡爾用一個(gè)神奇的數(shù)組來(lái)完成這個(gè)探索疾渴！
比如：
v4-v7千贯，權(quán)重為7，是最小的邊程奠。則記錄4號(hào)元素為7。也就是說(shuō)：以起始點(diǎn)為下標(biāo)祭钉，以結(jié)束點(diǎn)為值瞄沙！

[0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

v2-v8，權(quán)重為8
[0, 0, 8, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

如果這時(shí)候第3條為：
v2-v1慌核，權(quán)重為5距境。這不就沖突了嗎？因?yàn)?號(hào)位置上已經(jīng)有元素了垮卓。如果發(fā)生這種情況垫桂，就以該位置上值為位置放置新頂點(diǎn)。也就是：
[0, 0, 8, 0, 7, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

為什么這樣做粟按？因?yàn)檫@是最簡(jiǎn)單的測(cè)試回環(huán)的方法诬滩。
2號(hào)位置是8，代表v2和v8相連灭将。8號(hào)位置是1疼鸟，代表v8和v1相連。
如果再有邊是v1-v2庙曙，那么就構(gòu)成了回環(huán)空镜，一個(gè)三角回環(huán)。所以理解這個(gè)數(shù)組很重要捌朴！

克魯斯卡爾算法過(guò)程.png

package com.cx.graphtraversal;

public class GraphKruskal {

    private Edge[] edges;
    private int edgeSize; // 邊的數(shù)量

    public GraphKruskal(int edgeSize) {
        this.edgeSize = edgeSize;
        edges = new Edge[edgeSize];
    }

    public void miniSpanTreeKruskal() {
        int m, n, sum = 0;
        int[] parent = new int[edgeSize]; // 神奇的數(shù)組吴攒，下標(biāo)為起點(diǎn)，值為終點(diǎn)
        for (int i = 0; i < edgeSize; i++) {
            parent[i] = 0;
        }
        for (int i = 0; i < edgeSize; i++) {
            n = find(parent, edges[i].begin);
            m = find(parent, edges[i].end);
            if (n != m) { // 代表沒(méi)有回環(huán)
                parent[n] = m;
                System.out.println("起始頂點(diǎn)：" + edges[i].begin + "---結(jié)束頂點(diǎn)：" + edges[i].end + "~權(quán)值：" + edges[i].weight);
                sum += edges[i].weight;
            } else {
                System.out.println("第" + i + "條邊回環(huán)了");
            }
        }
        System.out.println("sum:" + sum);
    }

    /**
     * 將神奇數(shù)組進(jìn)行查詢獲取非回環(huán)的值
     */
    public int find(int[] parent, int f) {
        while (parent[f] > 0) {
            System.out.println("找到起點(diǎn)" + f);
            f = parent[f];
            System.out.println("找到終點(diǎn):" + f);
        }
        return f;
    }

    public void createEdgeArray() {
        Edge edge0 = new Edge(4, 7, 7);
        Edge edge1 = new Edge(2, 8, 8);
        Edge edge2 = new Edge(0, 1, 10);
        Edge edge3 = new Edge(0, 5, 11);
        Edge edge4 = new Edge(1, 8, 12);
        Edge edge5 = new Edge(3, 7, 16);
        Edge edge6 = new Edge(1, 6, 16);
        Edge edge7 = new Edge(5, 6, 17);
        Edge edge8 = new Edge(1, 2, 18);
        Edge edge9 = new Edge(6, 7, 19);
        Edge edge10 = new Edge(3, 4, 20);
        Edge edge11 = new Edge(3, 8, 21);
        Edge edge12 = new Edge(2, 3, 22);
        Edge edge13 = new Edge(3, 6, 24);
        Edge edge14 = new Edge(4, 5, 26);
        edges[0] = edge0;
        edges[1] = edge1;
        edges[2] = edge2;
        edges[3] = edge3;
        edges[4] = edge4;
        edges[5] = edge5;
        edges[6] = edge6;
        edges[7] = edge7;
        edges[8] = edge8;
        edges[9] = edge9;
        edges[10] = edge10;
        edges[11] = edge11;
        edges[12] = edge12;
        edges[13] = edge13;
        edges[14] = edge14;
    }

    class Edge {
        private int begin;
        private int end;
        private int weight;

        public Edge(int begin, int end, int weight) {
            super();
            this.begin = begin;
            this.end = end;
            this.weight = weight;
        }

        public int getBegin() {
            return begin;
        }

        public void setBegin(int begin) {
            this.begin = begin;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        GraphKruskal graphKruskal = new GraphKruskal(15);
        graphKruskal.createEdgeArray();
        graphKruskal.miniSpanTreeKruskal();
    }
}