Kruskal最小生成树
Kruskal最小生成树 是求解图G的最小生成树(最优树)T 的算法。Kruskal算法是基于边来构造的算法,相对好理解。还有一个Prim算法是从点方面考虑的构建方式。
对于图 \(G(V,E)\) ,Kruskal算法的时间复杂度是 \(O(|E| \cdot \alpha(V))\) ,其中α为Ackermann函数,其增长非常慢,我们可以视为常数。所以Kruskal算法的时间复杂度为 \(O(E \log(E))\).
Kruskal算法运行步骤如下:
设权图 \(G = (P, L)\) 是连通的。
- 取 $l_1 \in L(G) $ ,使 \(\omega(l_1)\) 最小。
- 如果 \(l_1,l_2, ...,l_i\) 已经得到,则从 $L(G) - {l_1,l_2,...,l_i} $ 中取 \(l_{i+1}\) ,使得 \(\{l_1,l_2,...,l_i,l_{i+1} \}\) 组成无回路的图,并且 \(\omega(l_{i+1})\) 最小,如果不存在这样的 \(l_{i+1}\) ,则算法停止。
以上来自《离散数学结构》
至于代码怎么写。
我们先存下所有的边,将所有边按照边权排序。然后开始按顺序枚举每一条边,如果会成环则跳过,不成还就加入,直到所有边都枚举完成。
其中如何判断成环,我们需要用到并查集。每次加入一条边时,我们把起点和终点加入一个并查集中。判断成环时,只需要判断新加的这条边的起点终点是否在同一个并查集中即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1000010;
struct Edge {
int x, y, value;
} edge[maxn];
int fa[maxn];
int n, m, p;
int x, y;
int res;
bool com(Edge x, Edge y) { //排序函数
if (x.value < y.value) return true;
else return false;
}
//并查集操作
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void combine(int x, int y) {
int fx = find(x), fy = find(y);
fa[fx] = fy;
return;
}
//Kruskal算法
int Kruskal() {
int ans = 0, cnt = 0;
for (int i = 1; i <= m; i++) {
if (find(edge[i].x) != find(edge[i].y)) { //判断加上这条边之后是否会形成回路
combine(edge[i].x, edge[i].y); //不会,则合并
cnt++;
ans = ans + edge[i].value; //记录答案
}
if (cnt == n - 1) break; //n-1条边代表已经提前生成完成了
}
if (cnt < n - 1) return -1; //枚举完所有边之后任然不足 n-1条边,则不存在最小生成树 orz
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].value);
}
sort(edge + 1, edge + m + 1, com);
res = Kruskal();
if (res == -1) printf("orz\n");
else printf("%d\n", res);
return 0;
}
标签:return,int,Kruskal,最小,生成,fa,算法
From: https://www.cnblogs.com/pengcheng-official/p/18227809