最小生成树
prim：点
kruskal：边
都是贪心
prim算法精讲
从顶点的角度，按照贪心算法，一个一个加入生成树。
关键点：
minDist表示不是生成树上的点到生成树的最小距离。
inTheTree表示是否是生成树上的点
步骤：
1.选取距离最小的点加入生成树
2.更新minDist
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
//input
int v, e, v1, v2, val;
cin >> v >> e;
vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));
while (e--) {
cin >> v1 >> v2 >> val;
grid[v1][v2] = val;
grid[v2][v1] = val;
}
vector<int> minDist(v + 1, 10001);
vector<bool> inTheTree(v + 1, false);
for (int i = 1; i <= v; i++) {
// cout << "i=" << i << endl;
//选一个距离最近的点加入生成树
//条件1：不在生成树里
//条件2：距离最近
int cur = -1;//随便选一个不存在的数
int minVal = INT_MAX;//选一个最大的数
for (int j = 1; j <= v; j++) {
if (!inTheTree[j] && minDist[j] < minVal) {
cur = j;
minVal = minDist[j];
}
}
inTheTree[cur] = true;
//更新minDist，其他非生成树的点距离生成树的距离
for (int j = 1; j <= v; j++) {
if (!inTheTree[j] && grid[cur][j] < minDist[j]) {
minDist[j] = grid[cur][j];
}
}
// for (int c = 1; c <= v; c++) {
// cout << minDist[c] << " ";
// }
}
int result=0;
for (int i = 2; i <= v; i++) {
result += minDist[i];
}
// for (int i = 0; i <= v; i++) {
// cout << minDist[i] << " ";
// }
cout << result << endl;
return 0;
}kruskal算法精讲
对所有边从小到大排序，如果这条边的两头不在同一个集合里，result加入这条边，集合中也加入这两个点。
//kruskal
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N=10001;
vector<int> father(N,-1);
struct Edge{
int l,r,val;
};
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, v1, v2, val;
cin >> v >> e;
// v = 10;
// e = 11;
// vector<vector<int>> graph;
// graph = {
// {1,2,15},
// {2,7,65},
// {2,3,88},
// {4,5,48},
// {5,7,45},
// {6,7,78},
// {6,9,40},
// {7,8,22},
// {8,9,38},
// {8,10,35},
// {9,10,52}
// };
vector<Edge> edges;
// int d = 0;
while (e--) {
cin >> v1 >> v2 >> val;
// int v1 = graph[e][0];
// int v2 = graph[e][1];
// int val = graph[e][2];
edges.push_back({v1,v2,val});
// d++;
}
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.val < b.val;
});
int result = 0;
init();
for(Edge edge:edges){
int l = find(edge.l);
int r = find(edge.r);
if(l!=r){
result += edge.val;
join(l,r);
}
}
cout << result << endl;
return 0;
}