站長(zhǎng)資訊網(wǎng)本篇文章給大家?guī)?lái)了關(guān)于java的相關(guān)知識(shí)，Prime算法是一種窮舉查找算法來(lái)從一個(gè)連通圖中構(gòu)造一棵最小生成樹。本文主要為大家介紹了Java中Prime算法的原理與實(shí)現(xiàn)，感興趣的可以學(xué)習(xí)一下。
推薦學(xué)習(xí)：《java視頻教程》
Prim算法介紹
1.點(diǎn)睛
在生成樹的過(guò)程中，把已經(jīng)在生成樹中的節(jié)點(diǎn)看作一個(gè)集合，把剩下的節(jié)點(diǎn)看作另外一個(gè)集合，從連接兩個(gè)集合的邊中選擇一條權(quán)值最小的邊即可。
2.算法介紹
首先任選一個(gè)節(jié)點(diǎn)，例如節(jié)點(diǎn)1，把它放在集合 U 中，U={1},那么剩下的節(jié)點(diǎn)為 V-U={2,3,4,5,6,7},集合 V 是圖的所有節(jié)點(diǎn)集合。
現(xiàn)在只需要看看連接兩個(gè)集合（U 和 V-U）的邊中，哪一條邊的權(quán)值最小，把權(quán)值最小的邊關(guān)聯(lián)的節(jié)點(diǎn)加入集合 U 中。從上圖可以看出，連接兩個(gè)集合的 3 條邊中，1-2 邊的權(quán)值最小，選中它，把節(jié)點(diǎn) 2 加入集合 U 中，U={1,2}，V – U={3,4,5,6}，如下圖所示。
再?gòu)倪B接兩個(gè)集合（U 和 V-U）的邊中選擇一條權(quán)最小的邊。從上圖看出，在連接兩個(gè)集合的4條邊中，節(jié)點(diǎn)2到節(jié)點(diǎn)7的邊權(quán)值最小，選中這條邊，把節(jié)點(diǎn)7加入集合U={1,2,7}中，V-U={3,4,5,6}。
如此下去，直到 U=V 結(jié)束，選中的邊和所有的節(jié)點(diǎn)組成的圖就是最小生成樹。這就是 Prim 算法。
直觀地看圖，很容易找出集合 U 到 集合 U-V 的邊中哪條邊的權(quán)值是最小的，但在程序中窮舉這些邊，再找最小值，則時(shí)間復(fù)雜度太高?？梢酝ㄟ^(guò)設(shè)置數(shù)組巧妙解決這個(gè)問(wèn)題，closet[j] 表示集合 V-U 中的節(jié)點(diǎn) j 到集合 U 中的最鄰近點(diǎn)，lowcost[j] 表示集合 V-U 中節(jié)點(diǎn) j 到集合 U 中最鄰近點(diǎn)的邊值，即邊(j,closest[j]) 的權(quán)值。
例如在上圖中，節(jié)點(diǎn) 7 到集合 U 中的最鄰近點(diǎn)是2，cloeest[7]=2。節(jié)點(diǎn) 7 到最鄰近點(diǎn)2 的邊值為1，即邊(2,7)的權(quán)值，記為 lowcost[7]=1,如下圖所示。
所以只需在集合 V – U 中找到 lowcost[] 只最小的節(jié)點(diǎn)即可。
3. 算法步驟
1.初始化
令集合 U={u0}，u0 屬于 V，并初始化數(shù)組 closest[]、lowcost[]和s[]。
2.在集合 V-U 中找 lowcost 值最小的節(jié)點(diǎn)t，即 lowcost[t]=min{lowcost[j]},j 屬于 V-U，滿足該公式的節(jié)點(diǎn) t 就是集合 V-U 中連接 U 的最鄰近點(diǎn)。
3.將節(jié)點(diǎn) t 加入集合 U 中。
4.如果集合 V – U 為空，則算法結(jié)束，否則轉(zhuǎn)向步驟 5。
5.對(duì)集合 V-U 中的所有節(jié)點(diǎn) j 都更新其 lowcost[] 和 closest[]。if(C[t][j]<lowcost[j]){lowcost[j]=C[t][j];closest[j]=t;},轉(zhuǎn)向步驟2。
按照上面步驟，最終可以得到一棵權(quán)值之和最小的生成樹。
4.圖解
圖 G=（V,E）是一個(gè)無(wú)向連通帶權(quán)圖，如下圖所示。
1 初始化。假設(shè) u0=1，令集合 U={1},集合 V-U={2,3,4,5,6,7},s[1]=true，初始化數(shù)組 closest[]：除了節(jié)點(diǎn)1，其余節(jié)點(diǎn)均為1，表示集合 V-U 中的節(jié)點(diǎn)到集合 U 的最鄰近點(diǎn)均為1.lowcost[]:節(jié)點(diǎn)1到集合 V-U 中節(jié)點(diǎn)的邊值。closest[] 和 lowcost[] 如下圖所示。
初始化后的圖為：
2 找 lowcost 最小的節(jié)點(diǎn)，對(duì)應(yīng)的 t=2，選中的邊和節(jié)點(diǎn)如下圖。
3 加入集合U中。將節(jié)點(diǎn) t 加入集合 U 中，U={1,2}，同時(shí)更新 V-U={3,4,5,6,7}
4 更新。對(duì) t 在集合 V-U 中的每一個(gè)鄰接點(diǎn) j,都可以借助 t 更新。節(jié)點(diǎn) 2 的鄰接點(diǎn)是節(jié)點(diǎn) 3 和節(jié)點(diǎn)7。
C[2][3]=20<lowcost[3]=無(wú)窮大，更新最鄰近距離 lowcost[3]=20,最鄰近點(diǎn) closest[3]=2;
C[2][7]=1<lowcost[7]=36，更新最鄰近距離 lowcost[7]=1,最鄰近點(diǎn) closest[7]=2;
更新后的 closest[] 和 lowcost[] 如下圖所示。
更新后的集合如下圖所示：
5 找 lowcost 最小的節(jié)點(diǎn)，對(duì)應(yīng)的 t=7，選中的邊和節(jié)點(diǎn)如下圖。
6 加入集合U中。將節(jié)點(diǎn) t 加入集合 U 中，U={1,2,7}，同時(shí)更新 V-U={3,4,5,6}
7 更新。對(duì) t 在集合 V-U 中的每一個(gè)鄰接點(diǎn) j,都可以借助 t 更新。節(jié)點(diǎn) 7 的鄰接點(diǎn)是節(jié)點(diǎn) 3、4、5、6。
- C[7][3]=4<lowcost[3]=20，更新最鄰近距離 lowcost[3]=4,最鄰近點(diǎn) closest[3]=7;
- C[7][4]=4<lowcost[4]=無(wú)窮大，更新最鄰近距離 lowcost[3]=9,最鄰近點(diǎn) closest[4]=7;
- C[7][5]=4<lowcost[5]=無(wú)窮大，更新最鄰近距離 lowcost[3]=16,最鄰近點(diǎn) closest[5]=7;
- C[7][6]=4<lowcost[6]=28，更新最鄰近距離 lowcost[3]=25,最鄰近點(diǎn) closest[6]=7;
更新后的 closest[] 和 lowcost[] 如下圖所示。
更新后的集合如下圖所示：
8 找 lowcost 最小的節(jié)點(diǎn)，對(duì)應(yīng)的 t=3，選中的邊和節(jié)點(diǎn)如下圖。
9 加入集合U中。將節(jié)點(diǎn) t 加入集合 U 中，U={1,2,3,7}，同時(shí)更新 V-U={4,5,6}
10 更新。對(duì) t 在集合 V-U 中的每一個(gè)鄰接點(diǎn) j,都可以借助 t 更新。節(jié)點(diǎn) 3 的鄰接點(diǎn)是節(jié)點(diǎn) 4。
C[3][4]=15>lowcost[4]=9，不更新
closest[] 和 lowcost[] 數(shù)組不改變。
更新后的集合如下圖所示：
11 找 lowcost 最小的節(jié)點(diǎn)，對(duì)應(yīng)的 t=4，選中的邊和節(jié)點(diǎn)如下圖。
12 加入集合U中。將節(jié)點(diǎn) t 加入集合 U 中，U={1,2,3,4,7}，同時(shí)更新 V-U={5,6}
13 更新。對(duì) t 在集合 V-U 中的每一個(gè)鄰接點(diǎn) j,都可以借助 t 更新。節(jié)點(diǎn) 4 的鄰接點(diǎn)是節(jié)點(diǎn) 5。
C[4][5]=3<lowcost[5]=16，更新最鄰近距離 lowcost[5]=3,最鄰近點(diǎn) closest[5]=4;
更新后的 closest[] 和 lowcost[] 如下圖所示。
更新后的集合如下圖所示：
14 找 lowcost 最小的節(jié)點(diǎn)，對(duì)應(yīng)的 t=5，選中的邊和節(jié)點(diǎn)如下圖。
15 加入集合U中。將節(jié)點(diǎn) t 加入集合 U 中，U={1,2,3,4,5,7}，同時(shí)更新 V-U={6}
16 更新。對(duì) t 在集合 V-U 中的每一個(gè)鄰接點(diǎn) j,都可以借助 t 更新。節(jié)點(diǎn) 5 的鄰接點(diǎn)是節(jié)點(diǎn) 6。
C[5][6]=17<lowcost[6]=25，更新最鄰近距離 lowcost[6]=17,最鄰近點(diǎn) closest[6]=5;
更新后的集合如下圖所示：
17 找 lowcost 最小的節(jié)點(diǎn)，對(duì)應(yīng)的 t=6，選中的邊和節(jié)點(diǎn)如下圖。
18 加入集合U中。將節(jié)點(diǎn) t 加入集合 U 中，U={1,2,3,4,5,6,7}，同時(shí)更新 V-U={}
19 更新。對(duì) t 在集合 V-U 中的每一個(gè)鄰接點(diǎn) j,都可以借助 t 更新。節(jié)點(diǎn) 6 在集合 V-U 中無(wú)鄰接點(diǎn)。不用更新 closest[] 和 lowcost[] 。
20 得到的最小生成樹如下。最小生成樹的權(quán)值之和為 57.
Prime 算法實(shí)現(xiàn)
1.構(gòu)建后的圖
2.代碼
package graph.prim; import java.util.Scanner; public class Prim { static final int INF = 0x3f3f3f3f; static final int N = 100; // 如果s[i]=true,說(shuō)明頂點(diǎn)i已加入U(xiǎn) 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) { // 初始時(shí)，集合中 U 只有一個(gè)元素，即頂點(diǎn) 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最近的頂點(diǎn)t for (int j = 1; j <= n; j++) { if (!s[j] && lowcost[j] < temp) { t = j; temp = lowcost[j]; } } if (t == 1) break; // 找不到 t，跳出循環(huán) 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("數(shù)組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("最小的花費(fèi)：" + sumcost); } }
3.測(cè)試
推薦學(xué)習(xí)：《java視頻教程》
