Java中Prime算法的原理與實現（總結分享）

本篇文章給大家帶來了關于java的相關知識，Prime算法是一種窮舉查找算法來從一個連通圖中構造一棵最小生成樹。本文主要為大家介紹了Java中Prime算法的原理與實現，感興趣的可以學習一下。

推薦學習：《java視頻教程》

Prim算法介紹

1.點睛

在生成樹的過程中，把已經在生成樹中的節點看作一個集合，把剩下的節點看作另外一個集合，從連接兩個集合的邊中選擇一條權值最小的邊即可。

2.算法介紹

首先任選一個節點，例如節點1，把它放在集合 U 中，U={1},那么剩下的節點為 V-U={2,3,4,5,6,7},集合 V 是圖的所有節點集合。

現在只需要看看連接兩個集合（U 和 V-U）的邊中，哪一條邊的權值最小，把權值最小的邊關聯的節點加入集合 U 中。從上圖可以看出，連接兩個集合的 3 條邊中，1-2 邊的權值最小，選中它，把節點 2 加入集合 U 中，U={1,2}，V – U={3,4,5,6}，如下圖所示。

再從連接兩個集合（U 和 V-U）的邊中選擇一條權最小的邊。從上圖看出，在連接兩個集合的4條邊中，節點2到節點7的邊權值最小，選中這條邊，把節點7加入集合U={1,2,7}中，V-U={3,4,5,6}。

如此下去，直到 U=V 結束，選中的邊和所有的節點組成的圖就是最小生成樹。這就是 Prim 算法。

直觀地看圖，很容易找出集合 U 到 集合 U-V 的邊中哪條邊的權值是最小的，但在程序中窮舉這些邊，再找最小值，則時間復雜度太高?？梢酝ㄟ^設置數組巧妙解決這個問題，closet[j] 表示集合 V-U 中的節點 j 到集合 U 中的最鄰近點，lowcost[j] 表示集合 V-U 中節點 j 到集合 U 中最鄰近點的邊值，即邊(j,closest[j]) 的權值。

例如在上圖中，節點 7 到集合 U 中的最鄰近點是2，cloeest[7]=2。節點 7 到最鄰近點2 的邊值為1，即邊(2,7)的權值，記為 lowcost[7]=1,如下圖所示。

所以只需在集合 V – U 中找到 lowcost[] 只最小的節點即可。

3. 算法步驟

1.初始化

令集合 U={u0}，u0 屬于 V，并初始化數組 closest[]、lowcost[]和s[]。

2.在集合 V-U 中找 lowcost 值最小的節點t，即 lowcost[t]=min{lowcost[j]},j 屬于 V-U，滿足該公式的節點 t 就是集合 V-U 中連接 U 的最鄰近點。

3.將節點 t 加入集合 U 中。

4.如果集合 V – U 為空，則算法結束，否則轉向步驟 5。

5.對集合 V-U 中的所有節點 j 都更新其 lowcost[] 和 closest[]。if(C[t][j]<lowcost[j]){lowcost[j]=C[t][j];closest[j]=t;},轉向步驟2。

按照上面步驟，最終可以得到一棵權值之和最小的生成樹。

4.圖解

圖 G=（V,E）是一個無向連通帶權圖，如下圖所示。

1 初始化。假設 u0=1，令集合 U={1},集合 V-U={2,3,4,5,6,7},s[1]=true，初始化數組 closest[]：除了節點1，其余節點均為1，表示集合 V-U 中的節點到集合 U 的最鄰近點均為1.lowcost[]:節點1到集合 V-U 中節點的邊值。closest[] 和 lowcost[] 如下圖所示。

初始化后的圖為：

2 找 lowcost 最小的節點，對應的 t=2，選中的邊和節點如下圖。

3 加入集合U中。將節點 t 加入集合 U 中，U={1,2}，同時更新 V-U={3,4,5,6,7}

4 更新。對 t 在集合 V-U 中的每一個鄰接點 j,都可以借助 t 更新。節點 2 的鄰接點是節點 3 和節點7。

C[2][3]=20<lowcost[3]=無窮大，更新最鄰近距離 lowcost[3]=20,最鄰近點 closest[3]=2;

C[2][7]=1<lowcost[7]=36，更新最鄰近距離 lowcost[7]=1,最鄰近點 closest[7]=2;

更新后的 closest[] 和 lowcost[] 如下圖所示。

更新后的集合如下圖所示：

5 找 lowcost 最小的節點，對應的 t=7，選中的邊和節點如下圖。

6 加入集合U中。將節點 t 加入集合 U 中，U={1,2,7}，同時更新 V-U={3,4,5,6}

7 更新。對 t 在集合 V-U 中的每一個鄰接點 j,都可以借助 t 更新。節點 7 的鄰接點是節點 3、4、5、6。

• C[7][3]=4<lowcost[3]=20，更新最鄰近距離 lowcost[3]=4,最鄰近點 closest[3]=7;
• C[7][4]=4<lowcost[4]=無窮大，更新最鄰近距離 lowcost[3]=9,最鄰近點 closest[4]=7;
• C[7][5]=4<lowcost[5]=無窮大，更新最鄰近距離 lowcost[3]=16,最鄰近點 closest[5]=7;
• C[7][6]=4<lowcost[6]=28，更新最鄰近距離 lowcost[3]=25,最鄰近點 closest[6]=7;

更新后的 closest[] 和 lowcost[] 如下圖所示。

更新后的集合如下圖所示：

8 找 lowcost 最小的節點，對應的 t=3，選中的邊和節點如下圖。

9 加入集合U中。將節點 t 加入集合 U 中，U={1,2,3,7}，同時更新 V-U={4,5,6}

10 更新。對 t 在集合 V-U 中的每一個鄰接點 j,都可以借助 t 更新。節點 3 的鄰接點是節點 4。

C[3][4]=15>lowcost[4]=9，不更新

closest[] 和 lowcost[] 數組不改變。

更新后的集合如下圖所示：

11 找 lowcost 最小的節點，對應的 t=4，選中的邊和節點如下圖。

12 加入集合U中。將節點 t 加入集合 U 中，U={1,2,3,4,7}，同時更新 V-U={5,6}

13 更新。對 t 在集合 V-U 中的每一個鄰接點 j,都可以借助 t 更新。節點 4 的鄰接點是節點 5。

C[4][5]=3<lowcost[5]=16，更新最鄰近距離 lowcost[5]=3,最鄰近點 closest[5]=4;

更新后的 closest[] 和 lowcost[] 如下圖所示。

更新后的集合如下圖所示：

14 找 lowcost 最小的節點，對應的 t=5，選中的邊和節點如下圖。

15 加入集合U中。將節點 t 加入集合 U 中，U={1,2,3,4,5,7}，同時更新 V-U={6}

16 更新。對 t 在集合 V-U 中的每一個鄰接點 j,都可以借助 t 更新。節點 5 的鄰接點是節點 6。

C[5][6]=17<lowcost[6]=25，更新最鄰近距離 lowcost[6]=17,最鄰近點 closest[6]=5;

更新后的集合如下圖所示：

17 找 lowcost 最小的節點，對應的 t=6，選中的邊和節點如下圖。

18 加入集合U中。將節點 t 加入集合 U 中，U={1,2,3,4,5,6,7}，同時更新 V-U={}

19 更新。對 t 在集合 V-U 中的每一個鄰接點 j,都可以借助 t 更新。節點 6 在集合 V-U 中無鄰接點。不用更新 closest[] 和 lowcost[] 。

20 得到的最小生成樹如下。最小生成樹的權值之和為 57.

Prime 算法實現

1.構建后的圖

2.代碼

package graph.prim;   import java.util.Scanner;   public class Prim {     static final int INF = 0x3f3f3f3f;     static final int N = 100;     // 如果s[i]=true,說明頂點i已加入U     static boolean s[] = new boolean[N];     static int c[][] = new int[N][N];     static int closest[] = new int[N];     static int lowcost[] = new int[N];       static void Prim(int n) {         // 初始時，集合中 U 只有一個元素，即頂點 1         s[1] = true;         for (int i = 1; i <= n; i++) {             if (i != 1) {                 lowcost[i] = c[1][i];                 closest[i] = 1;                 s[i] = false;             } else                 lowcost[i] = 0;         }         for (int i = 1; i < n; i++) {             int temp = INF;             int t = 1;             // 在集合中 V-u 中尋找距離集合U最近的頂點t             for (int j = 1; j <= n; j++) {                 if (!s[j] && lowcost[j] < temp) {                     t = j;                     temp = lowcost[j];                 }             }             if (t == 1)                 break; // 找不到 t，跳出循環             s[t] = true; // 否則，t 加入集合U             for (int j = 1; j <= n; j++) { // 更新 lowcost 和 closest                 if (!s[j] && c[t][j] < lowcost[j]) {                     lowcost[j] = c[t][j];                     closest[j] = t;                 }             }         }     }       public static void main(String[] args) {         int n, m, u, v, w;         Scanner scanner = new Scanner(System.in);         n = scanner.nextInt();         m = scanner.nextInt();         int sumcost = 0;         for (int i = 1; i <= n; i++)             for (int j = 1; j <= n; j++)                 c[i][j] = INF;         for (int i = 1; i <= m; i++) {             u = scanner.nextInt();             v = scanner.nextInt();             w = scanner.nextInt();             c[u][v] = c[v][u] = w;         }         Prim(n);         System.out.println("數組lowcost:");           for (int i = 1; i <= n; i++)             System.out.print(lowcost[i] + " ");           System.out.println();         for (int i = 1; i <= n; i++)             sumcost += lowcost[i];         System.out.println("最小的花費：" + sumcost);     } }

3.測試

推薦學習：《java視頻教程》