JAVA實踐最小生成樹-Prim算法

前言

這個算法的普通版本時間複雜度是O（n^2），據說是可優化的。

鄰接表+最小堆。然而我并沒有去實作。

不過此未經優化的版本适合稠密圖，Kruskal解決稀疏圖，豈不美哉= =

好吧，我就是懶了

已實作利用最小堆+鄰接表優化：

http://blog.csdn.net/xubaifu1997/article/details/52068329

實作功能

實作最小生成樹路徑長度的計算

中文版參考

/**
 * Prim算法
 * 同樣假設所有頂點未連接配接
    6   9
    2   4   11
    3   5   13
    4   6   3
    5   6   4
    2   3   6
    4   5   7
    1   2   1
    3   4   9
    1   3   2
 *
 * 從頂點1開始，尋找頂與點1可連接配接所有的頂點
 *      找到
 *          1→2，權值為1
 *          1→3，權值為2
 *      選擇權值最低的2号頂點，連接配接頂點1、2；
 *
 * 尋找與頂點1、2可連接配接的所有頂點
 *      找到
 *          1→2（此點排除，2已被作為末端連接配接）
 *          1→3     權值2
 *          2→3     權值6
 *          2→4     權值11
 *      選擇1→3
 * 尋找1、2、3可連接配接的所有頂點
 *      （排除以1、2、3作為末端的選項）找到
 *          2→4     權值11
 *          3→4     權值9
 *          3→5     權值13
 *       選擇3→4
 *  其餘點的操作類似
 *
 *  這個過程中唯一的問題是，腦袋會受到最短路徑思想的影響
 *  假設
 *      1→2權值1
 *      1→3權值5
 *      選擇頂點4時，1→2→4的總長度是12
 *                   1→3→4的總長度為14
 *  碰到這樣一開始覺得好奇怪，後來畫了個圖，發現雖然1到4經過2，單條路徑長度最短，總體生成的樹卻更長
 *  3→1→2→4長度17
 *  2→1→3→4長度15
 *  是以每次選擇 距離[任意一個已連接配接末端頂點] 最短的頂點，而不是距離首個頂點最短的頂點
 *
 *  解決了疑問，馬上寫代碼
 */
           

代碼實作

public class MinGenerationTreePrim {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int Inf = ;
        int n, m, count, min, minIndex;
        int[][] vertexes;
        boolean[] isConnected;//如果某頂點作為末端頂點被連接配接，應該為true
        int[] dis;//存儲已連接配接頂點都未連接配接頂點的最短距離
        int sum = ;//存儲路徑長度
        n = in.nextInt();
        m = in.nextInt();
        vertexes = new int[n][n];
        isConnected = new boolean[n];
        dis = new int[n];

        for (int i = ; i < n; i++) {
            for (int j = ; j < n; j++) {
                if (i == j) {
                    vertexes[i][j] = ;
                } else {
                    vertexes[i][j] = Inf;
                }
            }
        }

        for (int i = , a, b, c; i < m; i++) {
            a = in.nextInt();
            b = in.nextInt();
            c = in.nextInt();
            vertexes[a - ][b - ] = c;
            vertexes[b - ][a - ] = c;
        }

        //初始化dis數組
        minIndex = ;
        count = ;
        for (int i = ; i < n; i++) {
            dis[i] = vertexes[][i];
        }
        while (count < n) {
            min = Inf;
            //尋找權值最小的
            for (int i = ; i < n; i++) {
                if (!isConnected[i] && dis[i] < min) {
                    min = dis[i];
                    minIndex = i;
                }
            }
            sum += min;
            //System.out.println(min);
            isConnected[minIndex] = true;
            count++;
            //在minIndex之前的所有頂點已經對dis更新過了
            //是以隻需要更新minIndex頂點到其他頂點是否還有更短的距離
            for (int i = ; i < n; i++) {
                if (!isConnected[i] && dis[i] > vertexes[minIndex][i]) {
                    dis[i] = vertexes[minIndex][i];
                }
            }
        }
        System.out.println(sum);
    }
}
           

結果

輸入
    6   9
    2   4   11
    3   5   13
    4   6   3
    5   6   4
    2   3   6
    4   5   7
    1   2   1
    3   4   9
    1   3   2
輸出
19
           

END