1.prim算法精讲
代码随想录
题目：53. 寻宝（第七期模拟笔试）
代码：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main(){int v,e; // 顶点数 边数int x,y,k;cin >> v >> e;vector<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);// 构建最小联通树for(int i = 1; i < v; i++){// prim三部曲：第一步，选距离生成树最近节点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;}}// prim三部曲：第二步，最近节点加入生成树isInTree[cur] = true;// prim三部曲：第三步，更新非生成树节点到生成树的距离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;
}思路：
minDist数组 记录了 所有非生成树节点距离生成树的最小距离。
同时，minDist数组 也记录的是最小生成树所有边的权值。
prim算法类似于走一步算一步的过程，是一种贪心算法。首先先选取一个节点出发，然后选择这个节点的相邻节点中距离最近的节点构建最小生成树，然后更新这个节点所连接的相邻节点的最短距离到minDist数组里。
1、prim三部曲，第一步：距离 最小生成树最近的非生成树里的节点
// prim三部曲：第一步，选距离生成树最近节点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;}}这里cur用来记录我们要选的节点，minVal记录我们从已选节点出发的边中，权值最少的那一条，通过遍历上一次循环更新的minDist数组来确定。我们会根据这个来确定我们要加入最小生成树的节点。
2、prim三部曲，第二步：最近节点加入生成树
// prim三部曲：第二步，最近节点加入生成树isInTree[cur] = true;3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
// prim三部曲：第三步，更新非生成树节点到生成树的距离for(int j = 1; j <= v; j++){if(!isInTree[j] && grid[cur][j] < minDist[j]){minDist[j] = grid[cur][j];}}根据加入的最近节点来更新minDist数组。
2.kruskal算法精讲
代码随想录
题目：53. 寻宝（第七期模拟笔试）
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// l，r为边两边的节点，val为边的数值
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){if(father[u] == u) return u;return find(father[u]);
}
void join(int u,int v){u = find(u);v = find(v);if(u == v) return;father[u] = v;
}
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;});init();// 按权值，从小到大遍历每一条边for(Edge edge:edges){int x = find(edge.l);int y = find(edge.r);// 并查集 如果这条边的两个节点不在同一个集合if(x !=y){result_val += edge.val;join(x,y);}}cout << result_val << endl;return 0;
}思路：
prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
首先把边按照权值大小来排序。然后从小到大遍历每一条边，如果此边的两个节点不在同一个集合【说明把这条边加进来不会形成环】（利用并查集来判断） ，就可以把这条边连起来，作为最小生成树的边。
把所有的边都遍历一遍，就可以生成最小生成树了。（从小到大选取边，已经保证了我们生成的树的权值是最小的。）
