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;
}讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/180026.html