算法-最小生成樹算法(普裡姆算法 Prim`s algorithm)

Prim`s algorithm

• 概述
• • 修路問題

概述

• 普裡姆算法(Prim`s algorithm)是求出最小生成樹的算法, 也就是在包含 n個頂點的帶權無向連通圖中, 找出(n-1)條邊的最小耗費生成樹(Minimum Cost Spanning Tree), 簡稱 MST
• 普裡姆算法的時間複雜度為: 鄰接矩陣 O(v^2), 鄰接表 O(elog2v) e為網中的邊數

修路問題

• 有叫(A,B,C,D,E,F,G)的7個村莊, 現在需要将這7個村莊通過修路連通. 各個村莊的距離用邊線權值來表示, 比如 A-B距離5公裡
• 需要保證各個村莊都能連通, 且修建公路的總裡程為最短

• 求出最小生成樹的步驟:

1. 從頂點開始處理, 其中選出公裡數最近的, 也就是 A-G(權值2): <A,G>

   A-C(權值7),

   A-G(權值2)

   , A-B(權值5)

2. <A,G>開始, 将與 A和 G頂點相鄰的, 且還未通路的頂點進行處理: <A,G,B>

   A-C(權值7), A-B(權值5),

   G-B(權值3)

   , G-E(權值4), G-F(權值6)

3. <A,G,B>開始, 将與 A,G,B頂點相鄰的, 且還未通路的頂點進行處理: <A,G,B,E>

   A-C(權值7),

   G-E(權值4)

   , G-F(權值6), B-D(權值9)
4. 處理 F <A,G,B,E,F>, 對應的邊是

   E-F(權值5)

5. 處理 D <A,G,B,E,F,D>, 對應的邊是

   F-D(權值4)

6. 處理 C <A,G,B,E,F,D,C>, 對應的邊是

   A-C(權值7)

• 代碼實作

public class PrimAlgorithmApp {
    public static void main(String[] args) {
        /** 定義頂點(村莊)*/
        char[] data = new char[] {'A','B','C','D','E','F','G'};
        /** 設定鄰接矩陣的頂點與頂點間的邊(附帶權值), 權值9999表示不連通*/
        int[][] matrix = new int[][] {
                {9999,5,7,9999,9999,9999,2},
                {5,9999,9999,9,9999,9999,3},
                {7,9999,9999,9999,8,9999,9999},
                {9999,9,9999,9999,9999,4,9999},
                {9999,9999,8,9999,9999,5,4},
                {9999,9999,9999,4,5,9999,6},
                {2,3,9999,9999,4,6,9999},};
        /** 建立圖執行個體*/
        MSTGraph graph = new MSTGraph(data.length);
        /** 建立最小生成樹類執行個體*/
        MinimumCostSpanningTree mst = new MinimumCostSpanningTree();
        /** 建立鄰接矩陣*/
        mst.createGraph(graph, data, matrix);
        /** 列印鄰接矩陣*/
        mst.showGraph(graph);
        /** 求出最小生成樹*/
        mst.prim(graph, 1);
    }
}

/** 定義最小生成樹圖類*/
class MSTGraph {
    /** 頂點個數*/
    int vertexCount;
    /** 頂點資料*/
    char[] vertexes;
    /** 鄰接矩陣*/
    int[][] matrix;

    public MSTGraph(int count) {
        this.vertexCount = count;
        vertexes = new char[count];
        matrix = new int[count][count];
    }
}

/** 定義建立最小生成樹的類*/
class MinimumCostSpanningTree {
    /** 建立鄰接矩陣
     * @param graph 圖對象
     * @param data 圖的各個頂點的值
     * @param matrix 圖的鄰接矩陣*/
    public void createGraph(MSTGraph graph, char data[], int[][] matrix) {
        int i, j;
        for(i = 0; i < data.length; i++) {
            graph.vertexes[i] = data[i];
            for(j = 0; j < data.length; j++) {
                graph.matrix[i][j] = matrix[i][j];
            }
        }
    }

    /** 列印鄰接矩陣*/
    public void showGraph(MSTGraph graph) {
        for(int[] link: graph.matrix) {
            System.out.println(Arrays.toString(link));
        }
    }

    /** 求出最小生成樹
     * @param graph 圖
     * @param v 生成時, 起始頂點 'A'->0 'B'->1...*/
    public void prim(MSTGraph graph, int v) {
        /** 标記已被通路過的頂點, 按序每個頂點預設标記為0, 表示未通路過*/
        int visited[] = new int[graph.vertexCount];
        /** 将目前頂點标記為已通路*/
        visited[v] = 1;
        /** 臨時存儲已通路頂點下标*/
        int h1 = -1;
        /** 臨時存儲未通路頂點下标*/
        int h2 = -1;
        /** 初始權值設為9999表示不連通*/
        int minWeight = 9999;
        /** 最小生成樹的最終邊個數為 graph.vertexCount-1個*/
        for(int k = 1; k < graph.vertexCount; k++) {
            for(int i = 0; i < graph.vertexCount; i++) { /** i表示已被通路過的頂點*/
                for(int j = 0; j< graph.vertexCount;j++) { /** i表示未通路過的頂點*/
                    /** 已通路的頂點 && 未通路的頂點 && 公裡(權值)可達*/
                    if(visited[i] == 1 && visited[j] == 0 && graph.matrix[i][j] < minWeight) {
                        minWeight = graph.matrix[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            /** 找到一條邊是最小的可達邊*/
            System.out.println("邊<" + graph.vertexes[h1] + "," + graph.vertexes[h2] + "> 權值: " + minWeight);
            /** 将目前節點标記為已經通路*/
            visited[h2] = 1;
            /** 重新将 minWeight設為不連通*/
            minWeight = 9999;
        }
    }

}

輸出:
[9999, 5, 7, 9999, 9999, 9999, 2]
[5, 9999, 9999, 9, 9999, 9999, 3]
[7, 9999, 9999, 9999, 8, 9999, 9999]
[9999, 9, 9999, 9999, 9999, 4, 9999]
[9999, 9999, 8, 9999, 9999, 5, 4]
[9999, 9999, 9999, 4, 5, 9999, 6]
[2, 3, 9999, 9999, 4, 6, 9999]
邊<B,G> 權值: 3
邊<G,A> 權值: 2
邊<G,E> 權值: 4
邊<E,F> 權值: 5
邊<F,D> 權值: 4
邊<A,C> 權值: 7

           

如果您覺得有幫助，歡迎點贊哦 ~ 謝謝!!