题目描述
给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 G=(V,E),其中 V 表示图中点的集合,E 表示图中边的集合,n=|V|,m=|E|。
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G
的一棵生成树,其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
普利姆算法
思想:在n次循环中,每次从非集合元素中选取到集合最短距离的点t, 将t加入集合中,使用t更新其他到集合的最短距离,以此反复
举例:
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
1)初始化所有到集合的距离 dist = INF
2)起始情况,选择节点1,加入集合中,根据节点1更新其他节点的最短距离,此时集合{1},
3)在非集合中选择元素,此时选择节点2(因为节点2到集合的距离最短),加入集合中,根据节点2更新其他节点的最短距离,此是集合{1, 2}
以此反复
具体代码
import java.util.*;
import java.io.*;
public class Main {
private static int N = 510;
private static int INF = 0x3f3f3f3f;
private static int[][] g = new int[N][N]; // 邻接矩阵
private static boolean[] st = new boolean[N]; // 表示已加入集合的元素
private static int[] dist = new int[N]; // 表示元素到集合最短距离,而非像迪杰斯特拉到点1的距离
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] line = reader.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
for (int i=0; i<=n; i++) Arrays.fill(g[i], INF);
for (int i=0; i<m; i++) {
line = reader.readLine().split(" ");
int a = Integer.parseInt(line[0]);
int b = Integer.parseInt(line[1]);
int w = Integer.parseInt(line[2]);
g[a][b] = g[b][a] = Math.min(g[a][b], w);
}
int res = prim(n);
if (res == INF) System.out.println("impossible");
else System.out.println(res);
}
private static int prim(int n) {
Arrays.fill(dist, INF);
int res = 0;
// 循环n次
for (int i=0; i<n; i++) {
// 每次选取一个到集合最近的点
int t = -1;
for (int j=1; j<=n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
// 找不到通路,则无法构成最小生成树
if (i != 0 && dist[t] == INF) return INF;
// 集合内元素的最小生成树的路径长度相加
if (i != 0) res += dist[t];
// 加入集合
st[t] = true;
// 更新其他节点到集合的最短距离
for (int k=1; k<=n; k++) dist[k] = Math.min(dist[k], g[t][k]);
}
return res;
}
}