java實作Prim算法

1 問題描述

何為Prim算法？

普裡姆算法（Prim算法），圖論中的一種算法，可在權重連通圖裡搜尋最小生成樹。意即由此算法搜尋到的邊子集所構成的樹中，不但包括了連通圖裡的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。該算法于1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；并在1957年由美國計算機科學家羅伯特·普裡姆（英語：Robert C. Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該算法。是以，在某些場合，普裡姆算法又被稱為DJP算法、亞爾尼克算法或普裡姆－亞爾尼克算法。

原理簡單介紹：

1).輸入：一個權重連通圖，其中頂點集合為V，邊集合為E；

2).初始化：Vnew = {x}，其中x為集合V中的任一節點（起始點），Enew = {},為空；

3).重複下列操作，直到Vnew = V：

a.在集合E中選取權值最小的邊<u, v>，其中u為集合Vnew中的元素，而v不在Vnew集合當中，并且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；

b.将v加入集合Vnew中，将<u, v>邊加入集合Enew中；

4).輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。

2 解決方案

2.1 貪心法

本文具體編碼使用資料參考自《算法設計與分析基礎》第三版，下面是其具體圖示：

package com.liuzhen.chapter8;

import java.util.ArrayList;

public class Prim {
    /*
     * 參數G：給定的圖，其頂點分别為0~G.length-1，相應權值為具體元素的值
     * 函數功能：傳回構造生成的最小生成樹，以二維數組形式表示，其中元素為0表示最小生成樹的邊
     */
    public void getMinTree(int[][] G) {
        int[][] result = G;
        int[] vertix = new int[G.length];   //記錄頂點是否被通路，如果已被通路，則置相應頂點的元素值為-2
        for(int i = 0;i < G.length;i++)
            vertix[i] = i;
        ArrayList<Integer> listV = new ArrayList<Integer>(); //儲存已經周遊過的頂點
        listV.add(0);      //初始随意選擇一個頂點作為起始點，此處選擇頂點0
        vertix[0] = -2;    //表示頂點0被通路
        while(listV.size() < G.length) {  //當已被周遊的頂點數等于給定頂點數時，退出循環
            int minDistance = Integer.MAX_VALUE;    //用于尋找最小權值，初始化為int最大值，相當于無窮大的意思
            int minV = -1;   //用于存放未被周遊的頂點中與已被周遊頂點有最小權值的頂點
            int minI = -1;   //用于存放已被周遊的頂點與未被周遊頂點有最小權值的頂點  ；即G[minI][minV]在剩餘的權值中最小
            for(int i = 0;i < listV.size();i++) {   //i 表示已被通路的頂點
                int v1 = listV.get(i);
                for(int j = 0;j < G.length;j++) {
                    if(vertix[j] != -2) {    //滿足此條件的表示，頂點j未被通路
                        if(G[v1][j] != -1 && G[v1][j] < minDistance) {//G[v1][j]值為-1表示v1和j是非相鄰頂點
                            minDistance = G[v1][j];
                            minV = j;
                            minI = v1;
                        }
                    }
                }
            }
            vertix[minV] = -2;
            listV.add(minV);
            result[minI][minV] = 0;
            result[minV][minI] = 0;
        }
        System.out.println("使用Prim算法，對于給定圖中的頂點通路順序為：");
        System.out.println(listV);
        System.out.println("使用Prim算法，構造的最小生成樹的二維數組表示如下（PS：元素為0表示樹的邊）：");
        for(int i = 0;i < result.length;i++) {
            for(int j = 0;j < result[0].length;j++)
                System.out.print(result[i][j]+"\t");
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Prim test = new Prim();
        int[][] G = {{-1,3,-1,-1,6,5},
                {3,-1,1,-1,-1,4},
                {-1,1,-1,6,-1,4},
                {-1,-1,6,-1,8,5},
                {6,-1,-1,8,-1,2},
                {5,4,4,5,2,-1}};
        test.getMinTree(G);
    }
}
           

使用Prim算法，對于給定圖中的頂點通路順序為：
[0, 1, 2, 5, 4, 3]
使用Prim算法，構造的最小生成樹的二維數組表示如下（PS：元素為0表示樹的邊）：
-1    0    -1    -1    6    5    
   -1    0    -1    -1    0    
-1    0    -1    6    -1    4    
-1    -1    6    -1    8    0    
   -1    -1    8    -1    0    
   0    4    0    0    -1