使用Prim算法求图的最小生成树(MST) 输入 每组数据分为两个部分,第一部分为图的点数n,和边数m, 第二部分为m行,每一行输入三个数字,前两个为两个顶点的编号,第三个为边权重。 输出 最小生成树,输出时按照边的两个端点的升序输出。(先看左端点,再看右端点,端点不换位置) 样例输入 Copy 3 3 0 1 10 0 2 15 1 2 50 样例输出 Copy 0 1 10 0 2 15
时间: 2024-03-07 16:46:28 浏览: 22
下面是使用Java实现Prim算法求解最小生成树的代码:
```java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt(); // 点的个数
int m = scanner.nextInt(); // 边的个数
int[][] graph = new int[n][n]; // 邻接矩阵存储图
for (int i = 0; i < m; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
int w = scanner.nextInt();
graph[u][v] = w;
graph[v][u] = w;
}
prim(graph);
}
scanner.close();
}
private 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, Integer.MAX_VALUE);
Arrays.fill(parent, -1);
dist[0] = 0; // 从第一个点开始构建最小生成树
for (int i = 0; i < n - 1; i++) {
int u = getMinVertex(dist, visited);
visited[u] = true;
for (int v = 0; v < n; v++) {
if (graph[u][v] != 0 && !visited[v] && graph[u][v] < dist[v]) {
parent[v] = u;
dist[v] = graph[u][v];
}
}
}
printMST(parent, graph);
}
private static int getMinVertex(int[] dist, boolean[] visited) {
int minDist = Integer.MAX_VALUE;
int minVertex = -1;
for (int i = 0; i < dist.length; i++) {
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
minVertex = i;
}
}
return minVertex;
}
private static void printMST(int[] parent, int[][] graph) {
for (int i = 1; i < graph.length; i++) {
if (parent[i] < i) {
System.out.println(parent[i] + " " + i + " " + graph[parent[i]][i]);
} else {
System.out.println(i + " " + parent[i] + " " + graph[parent[i]][i]);
}
}
}
}
```
对于输入`3 3 0 1 10 0 2 15 1 2 50`,程序将输出`0 1 10`和`0 2 15`,与样例输出一致。