最小生成树定义
全部 n 个顶点和 n−1 条边构成的 无向连通子图 被称为 G 的一棵生成树,
其中边的权值之和最小的生成树被称为无向图 G 的最小生成树
Prim
朴素Prim
O(n ^ 2)
-
思路与 Dijkstra朴素版 基本相似, 只是 dist 数组存储 每个点到生成树(集合) 的最小距离[其中一个点最近即可]
-
n次迭代, 每次取出距离生成树最近的点, 当距离 生成树最近的点==初始值时,说明不存在最小生成树
if(dist[first] > Integer.MAX_VALUE / 4)
return false;
实现
// prim求最小生成树, 思路与dij相近
static boolean prim() {
// 初始化dist
Arrays.fill(dist, Integer.MAX_VALUE / 2);
dist[1] = 0; // 从1号点开始
// n次迭代, 每次选一个数 加入生成树
for(int i = 0; i < n; i++) {
int first = -1;
// 每次找到距离 集合(内的点)最近的点
for(int j = 1; j <= n; j++) // 同dij
if(!state[j] && (first == -1 || dist[first] > dist[j]))
first = j;
if(dist[first] > Integer.MAX_VALUE / 4)
return false;
state[first] = true; // 标记加入生成树
res += dist[first]; // 最短生成树 边长之和
// 更新生成树(集合)外的点 到集合的距离
for(int j = 1; j <= n; j++) {
// 到集合距离 > 到first距离, 更新
if(!state[j] && dist[j] > table[first][j]) {
// dij不同: dist[j] = Math.min(dist[j], dist[fisrt] + table[fisrt][j]);
dist[j] = table[first][j]; // 更新到集合最短距离
}
}
}
return true;
}
Kruskal - 稀疏图
O(m log m)
排序 + 并查集
==使用并查集, 不需要邻接表==
- 类数组 使用 Comparable 对边权重 进行排序
- 并查集应用
- 并查集笔记
- 题目: AcWing 837
实现
859. Kruskal算法求最小生成树 - AcWing题库
import java.util.*;
public class Main {
static int f[]; // f[x]: x的父节点
// 查找根节点 并 路径压缩
static int find(int a) {
if(f[a] != a) // 非根节点
f[a] = find(f[a]);
return f[a];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
Node nodes[] = new Node[m]; // 存储所有边 排序
for(int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int w = sc.nextInt();
nodes[i] = new Node(a, b, w);
}
// 1. 边权值排序
Arrays.sort(nodes);
// 2. 初始化并查集, 每个节点一个集合
f = new int[n + 1];
for(int i = 1; i <= n; i++)
f[i] = i;
int res = 0; // 最小生成树 距离之和
int cnt = 0; // 最小生成树 边数
// 3. 枚举所有边
for(int i = 0; i < m; i++) {
int a = nodes[i].a, b = nodes[i].b, w = nodes[i].w;
// 询问a和b是否在一个集合
if(find(a) != find(b)) {
// 不在一个, ab连通, 合并!
f[find(a)] = f[find(b)];
res += w;
cnt++;
}
}
// 边数 < n-1, 不构成生成树
if(cnt < n - 1)
System.out.print("impossible");
else
System.out.print(res);
}
}
class Node implements Comparable<Node> {
int a, b, w;
public Node(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
public int compareTo(Node node) {
return this.w - node.w; // 从小到大排序
}
}