普利姆算法(Prim)解決修路問題

普利姆算法應用目前問題得到的最小生成樹思路圖解:

java代碼

package com.bingym.prim;

import java.util.Arrays;

public class PrimAlgorithm {
    /*
    * 普利姆算法:
    * 典型的修路問題:
    * 1)有勝利鄉有7個村莊(A, B, C, D, E, F, G) ，現在需要修路把7個村莊連通
    * 2)各個村莊的距離用邊線表示(權) ，比如 A – B 距離 5公裡
    * 3)問：如何修路保證各個村莊都能連通，并且總的修建公路總裡程最短?
    * 思路: 将10條邊，連接配接即可，但是總的裡程數不是最小.
    * 正确的思路，就是盡可能的選擇少的路線，并且每條路線最小，保證總裡程數最少.
    * 修路問題本質就是就是最小生成樹問題:
    * 先介紹一下最小生成樹(Minimum Cost Spanning Tree)，簡稱MST。
    * 1)給定一個帶權的無向連通圖,如何選取一棵生成樹,使樹上所有邊上權的總和為最小,這叫最小生成樹
    * 2)N個頂點，一定有N-1條邊
    * 3)包含全部頂點
    * 4)N-1條邊都在圖中
    * 普裡姆算法生成最小生成樹的思路:
    * 普利姆(Prim)算法求最小生成樹，也就是在包含n個頂點的連通圖中，找出隻有(n-1)條邊包含所有n個頂點的連通子圖，也就是所謂的極小連通子圖
    * 普利姆的算法如下:
    * 設G=(V,E)是連通網，T=(U,D)是最小生成樹，V,U是頂點集合，E,D是邊的集合 
    * 若從頂點u開始構造最小生成樹，則從集合V中取出頂點u放入集合U中，标記頂點v的visited[u]=1
    * 若集合U中頂點ui與集合V-U中的頂點vj之間存在邊，則尋找這些邊中權值最小的邊，但不能構成回路，将頂點vj加入集合U中，将邊（ui,vj）加入集合D中，标記visited[vj]=1
    * 重複步驟②，直到U與V相等，即所有頂點都被标記為通路過，此時D中有n-1條邊
    * */
    public static void main(String[] args) {
        //測試看看圖是否建立ok
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxNums = data.length;
        //鄰接矩陣的關系使用二維數組表示,10000這個大數，表示兩個點不聯通
        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},};

        //建立MGraph對象
        Graph graph = new Graph(verxNums);
        //建立最小生成樹對象
        MinTree minTree = new MinTree();
        //建立Graph
        minTree.createGraph(graph,verxNums,data,weight);
        //輸出圖
        System.out.println("修路圖的鄰接矩陣為:");
        minTree.showGraph(graph);
        //測試普利姆算法
        System.out.println("使得路的總裡程數最少的路線為:");
        minTree.prim(graph,0);//0:表示誰為開始的頂點(此處表示從A開始進行最小生成樹的建立)

    }

}
//建立最小生成樹
class MinTree {
    //建立圖的鄰接矩陣
    public void createGraph(Graph graph,int vertexNums,char[] data,int[][] weight) {
        int i,j;
        for (i = 0; i < vertexNums; i++) {
            graph.data[i] = data[i];
            for (j = 0; j < vertexNums; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }
    //顯示圖的鄰接矩陣
    public void showGraph(Graph graph) {
        for (int[] link : graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }
    //編寫prim算法,擷取最小生成樹
    public void prim(Graph graph,int start) {
        //V表示進行最小生成樹的開始的頂點
        //定義數組visited[]:标記結點(頂點)是否被通路過:預設初始全為0(表示都未通路過)
        int[] visited = new int[graph.vertexNums];
        //标記目前開始的結點的為已經通路
        visited[start] = 1;
        //定義兩個下标:表示兩個頂點的下标
        int vertex1 = -1;
        int vertex2 = -1;
        int minWeight = 10000;//先将minWeight初始化一個很大的數,對于路的權值近似為無窮大
        for (int k = 1; k < graph.vertexNums; k++) {
            //因為有 graph.verxs頂點，普利姆算法結束後，有 graph.verxs-1邊
            for (int i = 0; i < graph.vertexNums; i++) {//i表示已經通路過的結點
                for (int j = 0; j < graph.vertexNums; j++) {//j表示還未通路的結點
                  if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
                      //替換minWeight(尋找已經通路過的結點和未通路過的結點間的權值最小的邊)
                      minWeight = graph.weight[i][j];
                      //同時記錄此時邊的兩個頂點
                      vertex1 = i;
                      vertex2 = j;
                  }

                }
            }
            //此時for循環以後找到了一條最小的了
            System.out.println("邊<" + graph.data[vertex1] + "," + graph.data[vertex2] + "> 權值:" + minWeight);
            //将此前未通路的j置為已通路的
            visited[vertex2] = 1;
            //重新将minWeight置為最大值
            minWeight = 10000;
        }
    }
}

//定義一個圖
class Graph {
    //圖的結點的個數(即頂點)的個數
    int vertexNums;
    int[][] weight;//存放邊,即鄰接矩陣
    char[] data;//存放結點的資料

    public Graph(int vertexNums) {
        this.vertexNums = vertexNums;
        //初始化結點數組
        data = new char[vertexNums];
        //初始化鄰接矩陣
        weight = new int[vertexNums][vertexNums];
    }
}