應(yīng)用場(chǎng)景-修路問(wèn)題

看一個(gè)應(yīng)用場(chǎng)景和問(wèn)題

有勝利鄉(xiāng)有7個(gè)村莊(A, B, C, D, E, F, G) ，現(xiàn)在需要修路把7個(gè)村莊連通
各個(gè)村莊的距離用邊線表示(權(quán)) ，比如 A – B 距離 5公里
問(wèn)：如何修路保證各個(gè)村莊都能連通，并且總的修建公路總里程最短?
思路: 將10條邊，連接即可，但是總的里程數(shù)不是最小.

正確的思路，就是盡可能的選擇少的路線，并且每條路線最小，保證總里程數(shù)最少. 

最小生成樹

修路問(wèn)題本質(zhì)就是就是最小生成樹問(wèn)題， 先介紹一下最小生成樹(Minimum Cost Spanning Tree)，簡(jiǎn)稱MST。

1. 給定一個(gè)帶權(quán)的無(wú)向連通圖,如何選取一棵生成樹,使樹上所有邊上權(quán)的總和為最小,這叫最小生成樹
2. N個(gè)頂點(diǎn)，一定有N-1條邊
3. 包含全部頂點(diǎn)
4. N-1條邊都在圖中

舉例說(shuō)明(如圖:)

求最小生成樹的算法主要是普里姆?算法和克魯斯卡爾算法
如圖

普利姆算法

普里姆算法介紹

普利姆(Prim)算法求最小生成樹，也就是在包含n個(gè)頂點(diǎn)的連通圖中，找出只有(n-1)條邊包含所有n個(gè)頂點(diǎn)的連通子圖，也就是所謂的極小連通子圖
普利姆的算法如下:

設(shè)G=(V,E)是連通網(wǎng)，T=(U,D)是最小生成樹，V,U是頂點(diǎn)集合，E,D是邊的集合

若從頂點(diǎn)u開始構(gòu)造最小生成樹，則從集合V中取出頂點(diǎn)u放入集合U中，標(biāo)記頂點(diǎn)v的visited[u]=1

若集合U中頂點(diǎn)ui與集合V-U中的頂點(diǎn)vj之間存在邊，則尋找這些邊中權(quán)值最小的邊，但不能構(gòu)成回路，將頂點(diǎn)vj加入集合U中，將邊（ui,vj）加入集合D中，標(biāo)記visited[vj]=1

重復(fù)步驟②，直到U與V相等，即所有頂點(diǎn)都被標(biāo)記為訪問(wèn)過(guò)，此時(shí)D中有n-1條邊

image.png

通過(guò)代碼，比較好理解.

代碼

public class PrimAlgorithm {

    public static void main(String[] args) {
        //測(cè)試看看圖是否創(chuàng)建ok
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        //鄰接矩陣的關(guān)系使用二維數(shù)組表示,10000這個(gè)大數(shù)，表示兩個(gè)點(diǎn)不聯(lián)通
        int [][]weight=new int[][]{
            {10000,5,7,10000,10000,10000,2},
            {5,10000,10000,9,10000,10000,3},
            {7,10000,10000,10000,8,10000,10000},
            {10000,9,10000,10000,10000,4,10000},
            {10000,10000,8,10000,10000,5,4},
            {10000,10000,10000,4,5,10000,6},
            {2,3,10000,10000,4,6,10000},};
            
        //創(chuàng)建MGraph對(duì)象
        MGraph graph = new MGraph(verxs);
        //創(chuàng)建一個(gè)MinTree對(duì)象
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);
        //輸出
        minTree.showGraph(graph);
        //測(cè)試普利姆算法
        minTree.prim(graph, 1);// 
    }

}

//創(chuàng)建最小生成樹->村莊的圖
class MinTree {
    //創(chuàng)建圖的鄰接矩陣
    /**
     * 
     * @param graph 圖對(duì)象
     * @param verxs 圖對(duì)應(yīng)的頂點(diǎn)個(gè)數(shù)
     * @param data 圖的各個(gè)頂點(diǎn)的值
     * @param weight 圖的鄰接矩陣
     */
    public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
        int i, j;
        for(i = 0; i < verxs; i++) {//頂點(diǎn)
            graph.data[i] = data[i];
            for(j = 0; j < verxs; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }
    
    //顯示圖的鄰接矩陣
    public void showGraph(MGraph graph) {
        for(int[] link: graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }
    
    //編寫prim算法，得到最小生成樹
    /**
     * 
     * @param graph 圖
     * @param v 表示從圖的第幾個(gè)頂點(diǎn)開始生成'A'->0 'B'->1...
     */
    public void prim(MGraph graph, int v) {
        //visited[] 標(biāo)記結(jié)點(diǎn)(頂點(diǎn))是否被訪問(wèn)過(guò)
        int visited[] = new int[graph.verxs];
        //visited[] 默認(rèn)元素的值都是0, 表示沒(méi)有訪問(wèn)過(guò)
//      for(int i =0; i <graph.verxs; i++) {
//          visited[i] = 0;
//      }
        
        //把當(dāng)前這個(gè)結(jié)點(diǎn)標(biāo)記為已訪問(wèn)
        visited[v] = 1;
        //h1 和 h2 記錄兩個(gè)頂點(diǎn)的下標(biāo)
        int h1 = -1;
        int h2 = -1;
        int minWeight = 10000; //將 minWeight 初始成一個(gè)大數(shù)，后面在遍歷過(guò)程中，會(huì)被替換
        for(int k = 1; k < graph.verxs; k++) {//因?yàn)橛?graph.verxs頂點(diǎn)，普利姆算法結(jié)束后，有 graph.verxs-1邊
            
            //這個(gè)是確定每一次生成的子圖 ，和哪個(gè)結(jié)點(diǎn)的距離最近
            for(int i = 0; i < graph.verxs; i++) {// i結(jié)點(diǎn)表示被訪問(wèn)過(guò)的結(jié)點(diǎn)
                for(int j = 0; j< graph.verxs;j++) {//j結(jié)點(diǎn)表示還沒(méi)有訪問(wèn)過(guò)的結(jié)點(diǎn)
                    if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
                        //替換minWeight(尋找已經(jīng)訪問(wèn)過(guò)的結(jié)點(diǎn)和未訪問(wèn)過(guò)的結(jié)點(diǎn)間的權(quán)值最小的邊)
                        minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            //找到一條邊是最小
            System.out.println("邊<" + graph.data[h1] + "," + graph.data[h2] + "> 權(quán)值:" + minWeight);
            //將當(dāng)前這個(gè)結(jié)點(diǎn)標(biāo)記為已經(jīng)訪問(wèn)
            visited[h2] = 1;
            //minWeight 重新設(shè)置為最大值 10000
            minWeight = 10000;
        }
        
    }
}

class MGraph {
    int verxs; //表示圖的節(jié)點(diǎn)個(gè)數(shù)
    char[] data;//存放結(jié)點(diǎn)數(shù)據(jù)
    int[][] weight; //存放邊，就是我們的鄰接矩陣
    
    public MGraph(int verxs) {
        this.verxs = verxs;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}

結(jié)果: