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

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

---

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;
}