当前位置：首页 > news >正文

代码随想录算法训练营第六十二天| prim算法，kruskal算法

news 2025/7/25 20:51:46

训练营六十二天打卡，图论比较难，坚持下来胜利就在眼前！

53.卡码网【寻宝】

题目链接

解题过程

没做过类似的题目，跟着答案敲了一遍
最小生成树可以使用 prim算法也可以使用 kruskal算法计算出来。
prim算法是从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中。
prim算法核心就是三步，prim三部曲：
1. 第一步，选距离生成树最近节点
2. 第二步，最近节点加入生成树
3. 第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
minDist数组用来记录每一个节点距离最小生成树的最近距离。

prim算法

#include<iostream>
#include<vector>
#include<climits>
using namespace std;int main() {int v, e;cin >> v >> e;vector<vector<int>>grid(v + 1, vector<int>(v + 1, 10001));while (e--) {int x, y, val;cin >> x >> y >> val;grid[x][y] = grid[y][x] = val;}vector<int>minDist(v + 1, 10001);vector<bool>isInTree(v + 1, false);for (int i = 1; i < v; i++) { // v - 1条边int cur = -1;int minVal = INT_MAX;for (int j = 1; j <= v; j++) {if (!isInTree[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}isInTree[cur] = true;for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}int result = 0;for (int i = 2; i <= v; i++) {result += minDist[i];}cout << result << endl;return 0;
}

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
kruscal的思路：
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 遍历排序后的边
  - 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
  - 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
将两个节点加入同一个集合，又如何判断两个节点是否在同一个集合呢
- 答案是并查集
- 并查集主要就两个功能：
  - 将两个元素添加到一个集合中
  - 判断两个元素在不在同一个集合

Kruskal算法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge{int l, r, val;
}; // l r 为边，val为边的数值
vector<int>father;
void init(int v) {father.resize(v + 1);for (int i = 0; i <= v; i++) {father[i] = i;}
}
int find(int u) {return u == father[u] ? u : father[u] = find(father[u]);
}void join(int u, int v) {u = find(u);v = find(v);if (u != v) {father[v] = u;}
}int main() {int v, e;cin >> v >> e;init(v);vector<Edge>edges;while (e--) {int l, r, val;cin >> l >> r >> val;Edge edge;edge.l = l;edge.r = r;edge.val = val;edges.push_back(edge);}sort(edges.begin(), edges.end(), [](Edge& e1, Edge& e2)->bool{return e1.val < e2.val;});int result = 0;for (Edge edge : edges) {int x = find(edge.l);int y = find(edge.r);if (x != y) {result += edge.val;join(x, y);}}cout << result << endl;return 0;
}