代码随想录算法训练营第60期第六十天打卡

       大家好，今天因为有数学建模比赛的校赛，今天的文章可能会简单一点，望大家原谅，我们昨天主要讲的是并查集的题目，我们复习了并查集的功能，我们昨天的题目其实难度不小，尤其是后面的有向图，我们是如何判断有环的，而且我们还需要判断一旦我们删除了某一条边，我们还需要判断我们当前还是不是树，还得讨论多种情况，其实挺复杂的，我们今天主要讲解两种算法的理论基础，分别是最小生成树prim算法和kruskal算法，这两个算法其实还是比较重要的，我们话不多说直接开始。

第一部分 prim算法

       直接就看那道卡码网编号为53的题目寻宝，题目是这样的：

        我们题目其实是给了我们一个带权图，我们首先就需要了解一下我们的最小生成树是什么意思？最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。很明显这道题目就是求最小生成树的，我们这里其实就是要求代价最小，prim算法是从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中。

        关于prim算法我们应该了解的是prim三部曲，第一步选距离生成树最近节点，第二步最近节点加入生成树，第三步更新非生成树节点到生成树的距离（即更新minDist数组），在prim算法中，有一个数组特别重要，这里我起名为：minDist。minDist数组用来记录每一个节点距离最小生成树的最近距离。这个是该算法的核心，如果不能理解这个数组那么就很难理解这个算法。

       初始化的过程：minDist数组里的数值初始化为最大数，因为本题节点距离不会超过10000，所以初始化最大数为10001就可以。现在还没有最小生成树，默认每个节点距离最小生成树是最大的，这样后面我们在比较的时候，发现更近的距离，才能更新到minDist数组上。我们后续是会持续更新数组的。接下来就是开始构造最小生成树，选择距离最小生成树最近的节点，加入到最小生成树，刚开始还没有最小生成树，所以随便选一个节点加入就好，（因为每一个节点一定会在最小生成树里，所以随便选一个就好），如果我们要符合遍历的习惯我们就选择节点1，很明显此时节点1已经算最小生成树的节点。接下来，我们要更新所有节点距离最小生成树的距离。注意下标0，我们就不管它了，下标1与节点1对应，这样可以避免大家把节点搞混。我们就直接索引与节点号相对应就可以。

         选取一个距离最小生成树（节点1）最近的非生成树里的节点，节点2，3距离最小生成树（节点1）最近，选节点2（其实选节点3或者节点2都可以，距离一样的）加入最小生成树。此时节点1和节点2，已经算最小生成树的节点。此时节点1和节点2，已经算最小生成树的节点。

#include<iostream>
#include<vector>
#include <climits>using namespace std;
int main() {int v, e;int x, y, k;cin >> v >> e;// 填一个默认最大值，题目描述val最大为10000vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));while (e--) {cin >> x >> y >> k;// 因为是双向图，所以两个方向都要填上grid[x][y] = k;grid[y][x] = k;}// 所有节点到最小生成树的最小距离vector<int> minDist(v + 1, 10001);// 这个节点是否在树里vector<bool> isInTree(v + 1, false);// 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起for (int i = 1; i < v; i++) {// 1、prim三部曲，第一步：选距离生成树最近节点int cur = -1; // 选中哪个节点 加入最小生成树int minVal = INT_MAX;for (int j = 1; j <= v; j++) { // 1 - v，顶点编号，这里下标从1开始//  选取最小生成树节点的条件：//  （1）不在最小生成树里//  （2）距离最小生成树最近的节点if (!isInTree[j] &&  minDist[j] < minVal) {minVal = minDist[j];cur = j;}}// 2、prim三部曲，第二步：最近节点（cur）加入生成树isInTree[cur] = true;// 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）// cur节点加入之后， 最小生成树加入了新的节点，那么所有节点到 最小生成树的距离（即minDist数组）需要更新一下// 由于cur节点是新加入到最小生成树，那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢for (int j = 1; j <= v; j++) {// 更新的条件：// （1）节点是 非生成树里的节点// （2）与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小// 很多录友看到自己 就想不明白什么意思，其实就是 cur 是新加入 最小生成树的节点，那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入，需要更新一下数据了if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}// 统计结果int result = 0;for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边result += minDist[i];}cout << result << endl;}

第二部分 Kruskal算法

       首先告诉大家 Kruskal算法，同样可以求最小生成树。它的过程大概是边的权值排序，因为要优先选最小的边加入到生成树里，遍历排序后的边，如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环，如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合，其实大家如果学过一门课程叫做离散数学就会知道我们离散数学里面也涉及到最小生成树的求解问题，里面我印象中主要有两种方法，一种是破圈法，一种是避圈法，我们都知道树不可以出现环，其实这两种算法似乎就是避圈法与破圈法。

         

       大家可以看到上面的那幅图，我们尝试过一遍Kruskal算法，我们首先将图中的边按照权值有小到大排序，这样从贪心的角度来说，优先选 权值小的边加入到 最小生成树中。排序后的边顺序为[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]，随后开始从头遍历排序后的边。首先选边(1,2)，节点1 和 节点2 不在同一个集合，所以生成树可以添加边(1,2)，并将 节点1，节点2 放在同一个集合。接下来选边(4,5)，节点4 和 节点 5 不在同一个集合，生成树可以添加边(4,5) ，并将节点4，节点5 放到同一个集合。随后选边(1,3)，节点1 和 节点3 不在同一个集合，生成树添加边(1,3)，并将节点1，节点3 放到同一个集合。选边(2,6)，节点2 和 节点6 不在同一个集合，生成树添加边(2,6)，并将节点2，节点6 放到同一个集合。选边(3,4)，节点3 和 节点4 不在同一个集合，生成树添加边(3,4)，并将节点3，节点4 放到同一个集合。选边(6,7)，节点6 和 节点7 不在同一个集合，生成树添加边(6,7)，并将 节点6，节点7 放到同一个集合。选边(5,7)，节点5 和 节点7 在同一个集合，不做计算。选边(1,5)，两个节点在同一个集合，不做计算。后面遍历 边(3,2)，(2,4)，(5,6) 同理，都因两个节点已经在同一集合，不做计算。这样大家可以看我们形成的图，有绿色边相连的就是在同一个集合中：

        其实这就是我跟大家说过的避圈法，因为如果在同一个集合中我们还选取的话就会出现环，这样就不符合最小生成树了，同时这里还涉及到我们前面的并查集，这样我们就可以尝试给出代码：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;struct Edge {int l, r, val;
};int n = 10001;vector<int> father(n, -1); void init() {for (int i = 0; i < n; ++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) return ; father[v] = u;
}int main() {int v, e;int v1, v2, val;vector<Edge> edges;int result_val = 0;cin >> v >> e;while (e--) {cin >> v1 >> v2 >> val;edges.push_back({v1, v2, val});}sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {return a.val < b.val;});vector<Edge> result; // 存储最小生成树的边init();for (Edge edge : edges) {int x = find(edge.l);int y = find(edge.r);if (x != y) {result.push_back(edge); // 保存最小生成树的边result_val += edge.val; join(x, y);}}// 打印最小生成树的边for (Edge edge : result) {cout << edge.l << " - " << edge.r << " : " << edge.val << endl;}return 0;
}

          这样我们其实就可以实现最小生成树的算法，算法我们就讲解到这里。

今日总结

        今天我们主要讲解了两种最小生成树的算法，我们其实还是会用到我们以前的并查集，因此大家可以看到学习算法应该是一个脚踏实地的事情，我们要一步步学扎实了才可以，我们今天就分享到这里，我们下次再见！