This article brings you relevant knowledge about java. The Prime algorithm is an exhaustive search algorithm to construct a minimum spanning tree from a connected graph. This article mainly introduces the principle and implementation of the Prime algorithm in Java. If you are interested, you can learn about it.
## Recommended study: "java video tutorial"
Introduction to Prim algorithm1. The finishing touch2 Find the node with the smallest lowcost, corresponding to t=2. The selected edges and nodes are as shown below.
3 Add to set U. Add node t to the set U, U={1,2}, and update V-U={3,4,5,6,7}
4 at the same time. For each adjacent point j of t in the set V-U, it can be updated with the help of t. The adjacent points of node 2 are node 3 and node 7.
C[2][3]=20 C[2][7]=1 Updated closest[] and lowcost[] as shown below. The updated set is as shown below: 5 Find the node with the smallest lowcost, and the corresponding t= 7. The selected edges and nodes are as shown below. 6 Add to set U. Add node t to the set U, U={1,2,7}, and update V-U={3,4,5,6} 7 at the same time. For each adjacent point j of t in the set V-U, it can be updated with the help of t. The adjacent points of node 7 are nodes 3, 4, 5, and 6. The updated closest[] and lowcost[] are as shown below shown. The updated set is shown in the figure below: ##14 Find the node with the smallest lowcost, and the corresponding t= 5. The selected edges and nodes are as shown below. 15 Add to set U. Add node t to the set U, U={1,2,3,4,5,7}, and update V-U={6} 16 at the same time. For each adjacent point j of t in the set V-U, it can be updated with the help of t. The neighbor of node 5 is node 6. C[5][6]=17 Updated The set is as shown below: 17 Find the node with the smallest lowcost, corresponding to t=6, and the selected edges and nodes are as shown below. 18 Add to set U. Add node t to the set U, U={1,2,3,4,5,6,7}, and update V-U={} 19 at the same time. For each adjacent point j of t in the set V-U, it can be updated with the help of t. Node 6 has no adjacent points in the set V-U. No need to update closest[] and lowcost[]. 20 The obtained minimum spanning tree is as follows. The sum of the weights of the minimum spanning tree is 57. Recommended study: " java video tutorial》 The above is the detailed content of The principle and implementation of Prime algorithm in Java (summary sharing). For more information, please follow other related articles on the PHP Chinese website!Prime algorithm implementation
1. The constructed graph
2. Code
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. Test