prim 算法和 Kruskal 算法以及 Boruvka 算法都是实现最小生成树的，prim 是通过点来实现，Kruskal 是通过边来实现，Brouvka 是最古老的一种算法，这节我们先讲 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;
}联系客服
