代码随想录算法训练营第六十二天| 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;
}