1 最小生成树的概论

最小生成树的概念

2 Kruskal算法

首先我们要熟记最小生成树的概念
必须是无向带权图，必须保证连通性，总的权值必须是最小的
如果无向带权图有n个节点，那么最小生成树一定有n-1个边

这个也被叫成k算法，很常用相比较prim算法
这个是不需要建图的，只需要构建并查集就可以解决问题
(实际解决的问题一般是权值最小是多少)

思路流程
1 首先我们要把这个根据这个权值把这些边进行排序
2 我们根据这个顺序进行挑选边，如果选择的当前边不会构成环，那么选择
3 如果这个边会构成环，那么我们就不选择

代码实现

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;const int MAXN = 10000;
int father[MAXN];
vector<vector<int>> edge;
int m, n;void build() {for (int i = 0; i < n; i++) {father[i] = i;}
}int find(int i) {if (i != father[i]) {father[i] = find(father[i]);}return father[i];
}bool binunion(int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy) {father[fx] = fy;return true;}else {return false;}
}// 修正比较函数
bool comparebin(const vector<int>& a, const vector<int>& b) {return a[2] < b[2];  // 按权重比较
}int sort_k() {build();sort(edge.begin(), edge.end(), comparebin);  // 使用vector的迭代器int weightval = 0;int edgecount = 0;for (int i = 0; i < m; i++) {if (binunion(edge[i][0], edge[i][1])) {weightval += edge[i][2];edgecount++;if (edgecount == n - 1) {break;}}}return edgecount == n - 1 ? weightval : 0;
}int main() {cin >> n >> m;edge.resize(m, vector<int>(3));for (int i = 0; i < m; i++) {cin >> edge[i][0] >> edge[i][1] >> edge[i][2];}int ans = sort_k();if (ans == 0) {cout << "orz" << endl;}else {cout << ans << endl;}return 0;
}

我们这里的find，binunion，build是在并查集实现的
sort_k才是克鲁斯卡尔算法
这个克鲁斯卡尔算法十分的简单
思路梳理
1 构建一个初始化的并查集，然后对这个vector进行排序
2 然后判断每一个边，利用并查集判断是否可以进行合并，然后加上这个权值和这个边数，加上边数和权值就可以进行返回了
3 继续要先从小到大排序

3 Prim算法

这个算法也被叫成P算法

思路流程
1 开辟一个小根堆和一个数组，小根堆是用来装边的，数组是用来装顶点的，记录那些顶点走过
2 可以从图上的任意节点开始，然后把这个点放入到数组里面，把这个边都放到小根堆里
3 通过小根堆去往没有去过的点
A 如果这个点已经存在数组里，那么就直接把这个点给舍弃掉，重复步骤3
B 如果这个点没有存在数组里，那么就加权值和点个数，然后把这个点放入数组里，进入下一个点