最小生成树prim算法kruskal算法

最小生成树

在一个无向图中求一棵树(n-1条边，无环，连通所有点)而且这棵树的边的权和最小

prim(普利姆)算法

prim算法有叫加点法，我们先标定一个点，然后寻找与这个点相连的边的权值最小的点，不断重复此操作，直到所有的点都被连通，我们看下图
在这里插入图片描述
我们以洛谷P3366这道题为例来具体写一下代码

代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>  // 用于memset
using namespace std;const int N = 5010;    // 最大的点数
const int INF = 0x3f3f3f3f;    // 无穷大，表示两个点之间没有直接边
int n;      // n 表示点数
int mp[N][N];        // 邻接矩阵，存储所有边的权重
int dist[N];         // 存储其他点到当前最小生成树的最短距离
bool st[N];          // 用于标记每个点是否已经在生成树中// 初始化函数，将邻接矩阵和其他辅助数组进行初始化
void init() {// 将邻接矩阵所有值设为无穷大INF，表示初始时没有任何边for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {mp[i][j] = INF;}}// 其他辅助数组清空memset(dist, 0x3f, sizeof dist);   // 将 dist 初始化为INFmemset(st, 0, sizeof st);          // 将 st 数组全置为 false（初始时没有点在最小生成树中）
}// Prim算法，计算最小生成树的权重总和
// 如果图不连通，返回 "orz"
int prim() {dist[1] = 0;  // 从第 1 个点开始，初始时距离设为0int res = 0;  // 存储最小生成树的总权重// 遍历 n 次，每次找一个点加入生成树for (int i = 0; i < n; i++) {int t = -1;  // t 用来存储当前距离生成树最近的点// 在所有未加入生成树的点中，找到距离最近的点 tfor (int j = 1; j <= n; j++) {if (!st[j] && (t == -1 || dist[t] > dist[j])) {t = j;}}// 如果除了第一个点以外，某个点的距离为INF，说明图不连通if (i && dist[t] == INF) {cout << "orz" << endl;return 0;}// 如果该点不是第一个点，将其距离加入总权重if (i) {res += dist[t];}st[t] = true;  // 将点 t 标记为已加入生成树// 更新所有其他点到生成树的最短距离for (int j = 1; j <= n; j++) {dist[j] = min(dist[j], mp[t][j]);}}// 返回最小生成树的总权重return res;
}int main() {int m;  // m 表示边数cin >> n >> m;  // 读入点数和边数init();  // 初始化邻接矩阵和其他辅助数组// 读入所有的边for (int i = 1; i <= m; i++) {int u, v, w;  // u, v 表示边的两个端点，w 表示权重cin >> u >> v >> w;// 如果这条边比之前存的边权小，则更新邻接矩阵if (mp[u][v] > w) {mp[u][v] = mp[v][u] = w;}}// 调用 Prim 算法，计算最小生成树的总权重int ans = prim();// 如果图连通，输出最小生成树的权重if (ans) {cout << ans << endl;}return 0;
}

kruskal(克鲁斯卡尔)算法

kruskal算法，又叫加边法，我们把所有点都列出来，然后一次把权值最短的边加上去，要注意加边之后不能形成环，我们看下图
在这里插入图片描述
还是同样的问题我们使用kruskal算法，我们主要是通过并查集来确保不会生成环

代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>  // 用于 std::sort
using namespace std;const int N = 5010;      // 最大点数
const int M = 2e5 + 10;  // 最大边数
const int INF = 0x3f3f3f3f;int n, m;       // n 是点数，m 是边数
int p[N];       // 并查集的父节点数组// 边结构体，存储一条边的信息（起点、终点、权重）
struct Edge {int a, b, w;// 运算符重载，用于边的排序，按边权升序排列bool operator< (const Edge& W) const {return w < W.w;}
} edges[M];// 并查集查找操作，带路径压缩
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) break;}}// 如果连通块的数量小于 n - 1，说明图不连通if (cnt < n - 1) return INF;return res;  // 返回最小生成树的权重总和
}int main() {cin >> n >> m;  // 输入点数和边数// 读入所有边for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;edges[i] = { u, v, w };  // 初始化每一条边}// 调用 Kruskal 算法计算最小生成树int ans = kruskal();// 如果图不连通，输出 "orz"，否则输出最小生成树的总权重if (ans == INF) cout << "orz" << endl;else cout << ans << endl;return 0;
}