java普里姆算法编程实现无向网的最小生成树,并代码输出最小生成树的边
时间: 2023-10-23 09:16:46 浏览: 28
下面是Java实现Prim算法的代码:
```java
import java.util.Arrays;
public class PrimMST {
private static final int INF = Integer.MAX_VALUE;
public static void prim(int[][] graph) {
int n = graph.length;
int[] dist = new int[n]; // 存储每个节点到生成树的距离
int[] parent = new int[n]; // 存储每个节点在生成树中的父节点
boolean[] visited = new boolean[n]; // 标记每个节点是否已经加入生成树
Arrays.fill(dist, INF);
Arrays.fill(parent, -1);
dist[0] = 0; // 从第一个节点开始生成树
for (int i = 0; i < n; i++) {
// 选取dist最小的未访问节点,加入生成树
int minDist = INF;
int u = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
if (u == -1) {
// 无法生成树
return;
}
visited[u] = true;
// 更新u的邻居节点到生成树的距离
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] < dist[v]) {
dist[v] = graph[u][v];
parent[v] = u;
}
}
}
System.out.println("最小生成树的边为:");
for (int i = 1; i < n; i++) {
System.out.println(parent[i] + " - " + i);
}
}
public static void main(String[] args) {
int[][] graph = {
{0, 2, 4, INF, INF},
{2, 0, 3, 5, INF},
{4, 3, 0, 1, 6},
{INF, 5, 1, 0, 3},
{INF, INF, 6, 3, 0}
};
prim(graph);
}
}
```
输出结果为:
```
最小生成树的边为:
0 - 1
1 - 2
2 - 3
3 - 4
```