最小生成樹，Prim 算法圖文詳解
prim 算法和 Kruskal 算法都是實現最小生成樹的一種算法，prim 是通過點來實現，而 Kruskal 是通過邊來實現，這節我們先講 prim 算法。對於一個有 n 個頂點的無向圖，如果只需要使用 n-1 條邊即可把圖中的所有點都連接起來，那麼這 n 個頂點和這 n-1 條邊構成的圖就是生成樹，如下圖所示。
一個圖的所有生成樹中權值總和最少的就是最小生成樹。prim 算法就是求最小生成樹的，他使用的是貪心算法。解題思路就是需要把圖中的點分成兩部分，一部分是已經選擇的，我們用集合 S 記錄，一部分是還沒選擇的，我們用集合 T 來記錄。剛開始的時候集合 S 爲空，集合 T 中包含圖中的所有頂點，如下圖所示，步驟如下。
-
第一步從集合
T中任選一個頂點v，把頂點v放到集合S中。 -
更新集合
T中和v相鄰的頂點值。 -
繼續從集合
T中選擇離集合S最近的頂點v，把它加入到集合S中，更新集合T中和v相鄰的頂點值。 -
一直重複下去，直到集合
T爲空。
/**
* @param g 圖的鄰接矩陣。
* @return 返回最小生成樹的值。
*/
private static int prim(int[][] g) {
int n = g.length;// 圖中頂點的個數。
boolean[] visited = new boolean[n];
// 沒被選擇的點到集合S的距離。
int[] dis = new int[n];
int max = 100;// 默認最大值。
Arrays.fill(dis, max);// 剛開始的時候距離都默認最大值。
visited[0] = true; // 選取頂點0作爲起始點。
for (int i = 0; i < n; i++)
dis[i] = g[0][i];// 更新0到其他點的距離。
int sum = 0;// 最小生成樹的總的權值。
// 繼續查找 n-1 次。
for (int i = 1; i < n; i++) {
int v = -1;// 查找集合T中距離S的最小頂點v。
int minDis = max;// 記錄頂點v的值。
for (int j = 0; j < n; j++) {// 查找。
if (!visited[j] && (dis[j] < minDis)) {
minDis = dis[j];
v = j;
}
}
System.out.print(v + ",");// 打印選擇的點。
visited[v] = true;// 把v加到集合S中，表示已經被選擇了。
sum += dis[v];// 累加總權值。
for (int j = 0; j < n; j++) {// 更新集合T中和v鄰接的頂點。
if (!visited[j] && g[v][j] < dis[j])
dis[j] = g[v][j];
}
}
return sum;
}本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/g8ytxqFu0RPWVOllmh_bIw