Acwing 最小生成树
最小生成树
最小生成树:由n个节点，和n-1条边构成的无向图被称为G的一棵生成树，在G的所有生成树中，边的权值之和最小的生成树，被称为G的最小生成树。（换句话说就是用最小的代价把n个点都连起来）
- Prim 算法（普利姆）
-
- 朴素版Prim(时间复杂度 O ( n 2 ) O(n^2) O(n2),适用于稠密图；
-
- 堆优化版Prim(时间复杂度 O ( m l o g n ) O(m log n) O(mlogn),适用于稀疏图),基本不用；
- Kruskal算法，适用于稀疏图，时间复杂度 O ( m l o g m ) O(m log m) O(mlogm).$
如果是稠密图，通常选用朴素版Prim算法，因为其思路比较简洁，代码比较短；如果是稀疏图，通常选用Kruskal算法，因为其思路比Prim简单清晰。堆优化版的Prim通常不怎么用。
1.Prim
朴素Prim
与朴素dijkstra思想几乎一样，只不过Prim算法的距离指得是点到最小生成树的集合的距离，而Dijkstra算法的距离是点到起点的距离。适合用于稠密图
Prim 算法过程：
- 初始化 dist 数组，表示各点到最小生成树的距离。开始时设为无穷大（INF）。
- 使用贪心策略，每次选取距离集合最近的点 t，并将其加入最小生成树。
- 若该点距离 INF 且不是第一个节点，表示图不连通，直接返回 INF。
- 更新其余未加入集合的点与最小生成树的最短距离。
- 最终返回最小生成树的总权值，若图不连通则输出 impossible。
实现思路：
- 初始化各点到集合的距离INF；
- n次循环，每次找到集合外且距离集合最近的点t，需要先判断除第一个点外找到的距离最近的点t距离是不是INF；
-
- 若是则不存在最小生成树了，结束；否则还可能存在，继续操作，用该点t来更新其它点到集合的距离（这里就是和Dijkstra最主要的区别），然后将该点t加入集合；
- 关于集合到距离最近的点：实际上就是不在集合的点与集合内的点的各个距离的最小值，每次加入新的点都会尝试更新一遍（dist[j] = min(dist[j],g[t][j]).在Dijkstra中是dist[j] - min(dits[j],dist[t] + g[t][j]));
板子：
const int N = 510, INF = 0x3f3f3f3f; // 定义最大节点数 N 和无穷大 INF
int g[N][N], dist[N]; // g[i][j] 表示从节点 i 到节点 j 的边权，dist[i] 表示当前生成树到节点 i 的最短距离
bool st[N]; // st[i] 表示节点 i 是否已经加入到最小生成树中
int n, m; // n 表示节点数量，m 表示边的数量
// 返回最小生成树的权值之和。如果图不连通，返回 INF
int prim() {
memset(dist, 0x3f, sizeof dist); // 初始化所有节点的最短距离为 INF（即无穷大）
int res = 0; // 最终的最小生成树权值之和
// Prim 算法的核心，循环 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;
}
// 如果当前是第一个节点或者找到的节点距离集合为 INF，说明图不连通
if (i && dist[t] == INF) return INF; // 无法构成最小生成树
if (i) res += dist[t]; // 将该节点的边权值加入最终结果中
// 更新其他未加入集合的节点到生成树的最短距离
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], g[t][j]); // 使用该节点 t 更新其他节点的最短距离
}
st[t] = true; // 标记该节点已经加入生成树
}
return res; // 返回最小生成树的总权值
}
Acwing 858.Prim 算法求最小生成树
注意：本题干未设起点所以要迭代n次，并且图中可能存在负的自环，因此计算最小生成树的总距离要在更新各点到集合距离之前。且该图为无向图，含重边，则构建边需要注意。
具体实现代码（详解版）：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f; // 定义最大节点数 N 和无穷大 INF
int g[N][N], dist[N]; // g[i][j] 表示从节点 i 到节点 j 的边权，dist[i] 表示当前生成树到节点 i 的最短距离
bool st[N]; // st[i] 表示节点 i 是否已经加入到最小生成树中
int n, m; // n 表示节点数量，m 表示边的数量
// 返回最小生成树的权值之和。如果图不连通，返回 INF
int prim() {
memset(dist, 0x3f, sizeof dist); // 初始化所有节点的最短距离为 INF（即无穷大）
int res = 0; // 最终的最小生成树权值之和
// Prim 算法的核心，循环 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;
}
// 如果当前是第一个节点或者找到的节点距离集合为 INF，说明图不连通
if (i && dist[t] == INF) return INF; // 无法构成最小生成树
if (i) res += dist[t]; // 将该节点的边权值加入最终结果中
// 更新其他未加入集合的节点到生成树的最短距离
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], g[t][j]); // 使用该节点 t 更新其他节点的最短距离
}
st[t] = true; // 标记该节点已经加入生成树
}
return res; // 返回最小生成树的总权值
}
int main() {
cin >> n >> m; // 输入节点数 n 和边数 m
memset(g, 0x3f, sizeof g); // 初始化邻接矩阵，所有边权值设为无穷大（表示节点间无边）
// 输入每条边的信息，构建邻接矩阵
while (m--) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c); // 无向图，所以 g[a][b] 和 g[b][a] 相同
}
int t = prim(); // 调用 Prim 算法计算最小生成树的权值
// 输出结果。如果返回的是 INF，说明图不连通，输出 "impossible"
if (t == INF) puts("impossible");
else cout << t << endl; // 否则输出最小生成树的权值
return 0;
}
堆优化Prim：思路和堆优化的Dijkstra思路基本一样，且基本不用，对于稀疏图，不如用Kruskal，这里略过
2. Kruskal
适用于稀疏图，时间复杂度 O ( m l o g m ) O(m log m) O(mlogm).Kruskal 算法是求解无向连通图的 最小生成树（MST）的经典算法。它的核心思想是通过贪心策略，按权值从小到大逐步选择边，确保不会产生环，直到选出 n-1 条边为止。整个过程涉及使用 并查集 来判断是否形成环
- 先将所有的边按照权重，从小到大排序；
- 从小到大枚举每条边（a,b,w)若a，b不连通，则将这条边加入集合中(将a点和b点连接起来）实质上是一个并查集的应用（两点之间加边，看两点是否存在一个连通块）
- 无需用邻接表、邻接矩阵存储图，直接使用结构体，表示边及其权值
板子：
const int N = 200010, INF = 0x3f3f3f3f;
int p[N]; // 并查集的父节点数组
int n, m; // n 表示节点数，m 表示边数
// 边的结构体，表示一条边及其权值
struct Edge {
int a, b, w; // a, b 为连接的两个节点，w 为权值
// 重载小于运算符，用于按边权值升序排序
bool operator<(const Edge &W) const {
return w < W.w;
}
} edges[N]; // 存储所有边
// 并查集：寻找节点 x 所在集合的根节点
int find(int x) {
if (p[x] != x) p[x] = find(p[x]); // 路径压缩，找到根节点并直接连接
return p[x];
}
// Kruskal 算法求最小生成树
int kruskal() {
sort(edges, edges + m); // 按照边的权值升序排序
for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集，每个节点的父节点是自己
int res = 0, cnt = 0; // res 存储最小生成树的权值之和，cnt 记录最小生成树的边数
// 遍历所有边
for (int i = 0; i < m; i++) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
// 找到两个节点的根节点
a = find(a), b = find(b);
if (a != b) { // 如果两点不在同一个集合中，说明它们不连通
p[a] = b; // 将两点所在的集合合并
res += w; // 累加这条边的权值
cnt++; // 增加计数
}
}
// 如果使用的边数不足 n-1，则说明图不连通，无法构成最小生成树
if (cnt < n - 1) return INF;
else return res; // 返回最小生成树的权值
}
具体实现代码（详解版）：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010, INF = 0x3f3f3f3f;
int p[N]; // 并查集的父节点数组
int n, m; // n 表示节点数，m 表示边数
// 边的结构体，表示一条边及其权值
struct Edge {
int a, b, w; // a, b 为连接的两个节点，w 为权值
// 重载小于运算符，用于按边权值升序排序
bool operator<(const Edge &W) const {
return w < W.w;
}
} edges[N]; // 存储所有边
// 并查集：寻找节点 x 所在集合的根节点
int find(int x) {
if (p[x] != x) p[x] = find(p[x]); // 路径压缩，找到根节点并直接连接
return p[x];
}
// Kruskal 算法求最小生成树
int kruskal() {
sort(edges, edges + m); // 按照边的权值升序排序
for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集，每个节点的父节点是自己
int res = 0, cnt = 0; // res 存储最小生成树的权值之和，cnt 记录最小生成树的边数
// 遍历所有边
for (int i = 0; i < m; i++) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
// 找到两个节点的根节点
a = find(a), b = find(b);
if (a != b) { // 如果两点不在同一个集合中，说明它们不连通
p[a] = b; // 将两点所在的集合合并
res += w; // 累加这条边的权值
cnt++; // 增加计数
}
}
// 如果使用的边数不足 n-1，则说明图不连通，无法构成最小生成树
if (cnt < n - 1) return INF;
else return res; // 返回最小生成树的权值
}
int main() {
cin >> n >> m; // 输入节点数和边数
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w; // 输入每条边的两个端点 a, b 和边的权值 w
edges[i] = {a, b, w}; // 存储边的信息
}
int t = kruskal(); // 调用 Kruskal 算法
if (t == INF) puts("impossible"); // 如果返回值为 INF，说明图不连通
else cout << t << endl; // 否则输出最小生成树的权值
return 0;
}
Kruskal 算法的核心思想：
- 贪心策略：每次选择权值最小的边，且不形成环；
- 并查集：用于快速检查两个节点是否已经连通，以及合并不同的连通集合。
3.对比总结
原文地址：https://blog.csdn.net/qq_43060884/article/details/142553938
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！