文章目录
前言
一、Kruskal算法
二、AcWing 859. Kruskal算法求最小生成树
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：Kruskal，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、Kruskal算法
把所有边按照权重从小到大进行排序，枚举每条边（a，b，w），如果a，b不连通，把这条边也加入到集合中，判断a，b是否联通用的是并查集
下图来自AcWing算法基础课：
二、AcWing 859. Kruskal算法求最小生成树
本题链接：AcWing 859. Kruskal算法求最小生成树
本博客提供本题截图：
本题分析
p数组就是并查集中的p数组，find函数就是并查集中的find函数，res存储的是最小生成树中的所有树边的权重之和，cnt存储的是当前加入了多少条边，因为一共有n个点，所以如果最后的边数小于n - 1的话，证明不存在最小生成树
AC代码
#include <cstdio> #include <algorithm> using namespace std; const int N = 100010, M = 200010; const int INF = 0x3f3f3f3f; int 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 ++ ) { auto t = edges[i]; int a = t.a, b = t.b, w = t.w; a = find(a), b = find(b); if (a != b) { res += w; cnt ++; p[a] = b; } } if (cnt < n - 1) return INF; else return res; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i ++ ) { int a, b, w; scanf("%d%d%d", &a, &b, &w); edges[i] = {a, b, w}; } int t = kruskal(); if (t == INF) printf("impossible"); else printf("%d", t); return 0; }
三、时间复杂度
关于Kruskal算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
