Acwing 最小生成树

最小生成树

最小生成树:由n个节点，和n-1条边构成的无向图被称为G的一棵生成树，在G的所有生成树中，边的权值之和最小的生成树，被称为G的最小生成树。（换句话说就是用最小的代价把n个点都连起来）

Prim 算法（普利姆）
- 朴素版Prim(时间复杂度 $O(n^2)$ ,适用于稠密图；
- 堆优化版Prim(时间复杂度 $O (m l o g n)$ ,适用于稀疏图),基本不用；
Kruskal算法，适用于稀疏图，时间复杂度 $O (m l o g m)$ .$

如果是稠密图，通常选用朴素版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 和边数 mmemset(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)$ .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 和边的权值 wedges[i] = {a, b, w}; // 存储边的信息}int t = kruskal(); // 调用 Kruskal 算法if (t == INF) puts("impossible"); // 如果返回值为 INF，说明图不连通else cout << t << endl; // 否则输出最小生成树的权值return 0;
}