prime算法基本思想,java中prime是什么意思

目录

Prim算法简介1。点睛之笔2。算法介绍3。算法步骤4。素数算法实现说明1。图2施工后。代码3。试验

Prim算法介绍

　　00-1010在生成树的过程中，已经在生成树中的节点视为一个集合，剩下的节点视为另一个集合，可以从连接两个集合的边中选择权重最小的边。

1.点睛

　　首先选择任意一个节点，比如节点1，放入集合U中，其中U={1}，那么剩下的节点就是V-U={2，3，4，5，6，7}，集合V就是图的所有节点的集合。

　　现在我们只需要看看连接两个集合(U和V-U)的边中，哪条边的权重最小，将权重最小的边所关联的节点加入到集合U中，从上图可以看出，连接两个集合的三条边中，1-2的权重最小。选中它，添加节点2设置U，其中U={1，2}，V -U={3，4，5，6}，如下图所示。

　　然后从连接两个集合(U和V-U)的边中选择权重最小的边。从上图可以看出，连接两个集合的四条边中，节点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 U中找到最低成本[]最小的节点。

　　00-1010 1.初始化

　　设集合U={u0}，u0属于V，初始化数组closest[]，lowcost[]，s[]。

　　2.在集合V-U中找出lowcost值最低的节点T，即low cost [t]=min {low cost [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]low cost[J]){ low cost[J]=C[t][J]；最近的[j]=t；}，转到步骤2。

　　按照上面的步骤，最终可以得到一棵权重之和最小的生成树。

　　00-1010图G=(V，E)是一个无向连通加权图，如下图所示。

　　1初始化。假设u0=1，设集合U={1}，集合V-U={2，3，4，5，6，7}，s [1]=true，初始化数组closest[]:除了节点1，其他所有节点都是1，这意味着集合V-U中的节点到集合U的最近点都是1。成本低。最接近[]和低成本[]如下图所示。

　　初始化后的图如下：

　　2找到低成本最低的节点，对应的t=2。下图显示了选定的边和节点。

　　3加入集合U .将节点T加入集合U，U={1，2}，更新V-U={3，4，5，6，7}

　　4更新。集合V-U中T的每个相邻点j可以被T更新.节点2的相邻点是节点3和节点7。

　　C[2][3]=20lowcost[3]=无穷大，更新最近距离lowcost[3]=20，最近点closest[3]=2；

　　C[2][7]=1lowcost[7]=36，更新最近距离lowcost[7]=1，最近点closest[7]=2；

　　更新后的最近[]和低成本[]如下图所示。

　　更新后的集合如下图所示：

　　ter">

　　5找lowcost最小的节点，对应的t=7，选中的边和节点如下图。

　　6 加入集合U中。将节点t加入集合U中，U={1,2,7}，同时更新V-U={3,4,5,6}

　　7更新。对t在集合V-U中的每一个邻接点j,都可以借助t更新。节点 7的邻接点是节点 3、4、5、6。

　　C[7][3]=4<lowcost[3]=20，更新最邻近距离 lowcost[3]=4,最邻近点 closest[3]=7;C[7][4]=4<lowcost[4]=无穷大，更新最邻近距离 lowcost[3]=9,最邻近点 closest[4]=7;C[7][5]=4<lowcost[5]=无穷大，更新最邻近距离 lowcost[3]=16,最邻近点 closest[5]=7;C[7][6]=4<lowcost[6]=28，更新最邻近距离 lowcost[3]=25,最邻近点 closest[6]=7;更新后的 closest[]和lowcost[]如下图所示。

　　更新后的集合如下图所示：

　　8找lowcost最小的节点，对应的t=3，选中的边和节点如下图。

　　9 加入集合U中。将节点t加入集合U中，U={1,2,3,7}，同时更新V-U={4,5,6}

　　10 更新。对t在集合V-U中的每一个邻接点j,都可以借助t更新。节点 3 的邻接点是节点 4。

　　C[3][4]=15>lowcost[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<lowcost[5]=16，更新最邻近距离 lowcost[5]=3,最邻近点 closest[5]=4;

　　更新后的 closest[]和lowcost[]如下图所示。

　　更新后的集合如下图所示：

　　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<lowcost[6]=25，更新最邻近距离 lowcost[6]=17,最邻近点 closest[6]=5;

　　更新后的集合如下图所示：

　　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中Prime算法的原理与实现详解的详细内容，更多关于Java Prime算法的资料请关注盛行IT其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。