1 基础知识
kruskal算法的关键步骤为:
- 将所有边按照权重从小到大排序。
- 定义集合S,表示生成树。
- 枚举每条边(a,b,c),起点a,终点b,边长c。如果结点a和结点b不连通(用并查集来维护),则将这条边加入到集合S中。
kruskal算法的时间复杂度为O(mlogm),它用来解决稀疏图的最小生成树问题。文章来源:https://www.toymoban.com/news/detail-752521.html
2 模板
int n, m; // n是点数,m是边数
int p[N]; // 并查集的父节点数组
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通,则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
3 工程化
题目1:求最小生成树。文章来源地址https://www.toymoban.com/news/detail-752521.html
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int p[N];
int n, m;
struct Edge {
int a, b, w;
bool operator< (const Edge& W) const {
return w < W.w;
}
}edges[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> edges[i].a >> edges[i].b >> edges[i].w;
}
//初始化并查集
for (int i = 1; i <= n; ++i) p[i] = i;
sort(edges, edges + m);
int res = 0, cnt = 0;
for (int i = 0; i < m; ++i) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a);
b = find(b);
if (a != b) {
p[a] = b;
res += w;
cnt ++;
}
}
if (cnt < n-1) {
cout << "impossible" << endl;
} else {
cout << res << endl;
}
return 0;
}
到了这里,关于acwing算法基础之搜索与图论--kruskal算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!