推荐学习：《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]0245db2002e0d55e9990d2bf78fc96fdlowcost[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
更新后的集合如下图所示：
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
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视频教程》
以上就是java中prime算法的原理与实现（总结分享）的详细内容。