<span>最小生成树学习笔记1 - Kruskal</span>

最小生成树

定义

定义

给定一个带权图，满足以下条件：

1.保证图中所有的点都联通
2.在满足条件1的情况下尽可能去掉多的边，使得所有的边权之和最小，即 $Σ_{i = 1}^{i < = m} w_{i}$ 最小。

Kruskal算法

Kruskal是基于贪心的思想，根据以上的定义描述依次枚举 $1 - m$ 条边，如果两个点没有存在于一个连通分量中，那么就连上这一条边。
此算法的难点在于查询两个点是否在一个连通分量中，朴素思想可以使用 $D F S$ / $B F S$ 进行遍历，但是会使得时间复杂度非常高，此时可以使用并查集进行维护，优化时间。

算法流程

1.建立并查集，初始化 $f a [i] = i$ .
2.按边权从小到大枚举。
3.如果 $(u, v, w)$ 中 $u$ 和 $v$ 不连通，就合并 $u$ , $v$ 所在的集合， $a n s$ 累加上 $w$ .
4.否则直接跳过
5.如果已经加上了 $n - 1$ 条边，那么就退出，得到答案。

时间复杂度为 $O (m l o g m)$ .

具体实现

建立结构体存边

struct node {
	int u, v, w; // u -> 起点 v -> 终点 w -> 边权
} dis[MAXM];
bool cmp(node x, node y) {//自定义排序 贪心 保证边权较小的排在前面
	return x.w < y.w;
}

并查集维护

int FindSet(int v) {//查询父节点
	if(fa[v] == v) return v;
	else {
		return fa[v] = FindSet(fa[v]);//路径压缩
	}
}
bool UnionSet(int v, int u) {//查询是否在一个连通分量之中 + 合并
	int x = FindSet(v);
	int y = FindSet(u);
	if(x == y) return 0;
	fa[x] = fa[y];
	return 1;
}

完整代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 105;
const int MANM = MAXN * MAXN;

int n, m, tot, ans;
int fa[MAXN];
//存边与排序
struct node {
	int u, v, w;
} dis[MAXM];
bool cmp(node x, node y) {
	return  x.w < y.w;
}
//并查集维护
int FindSet(int v) {
	if(fa[v] == v) return v;
	else {
		return fa[v] = FindSet(fa[v]);
	}
} 
bool UnionSet(int v, int u) {
	int x = FindSet(v);
	int y = FindSet(u);
	if(x == y) return 0;
	fa[y] = fa[x];
	return 1;
}  

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++) {
		scanf("%d %d %d", &dis[i].u, &dis[i].v, &dis[i].w);//输入每一条边的值
	}
	sort(dis + 1, dis + 1 + m, cmp) ;//按w从小到大排序
	for(int i = 1; i <= n; i++) fa[i] = i;//并查集初始化
	for(int i = 1; i <= m; i++) {//枚举每一条边
		if(UnionSet(dis[i].u, dis[i].v)) {//查询是否在一个连通分量之中
			ans += dis[i].w;//加入边权
			tot ++;//记录已经加入的边数
		}
		if(tot == n - 1) break; //如果边数已满，就积时退出
	}
	printf("%d\n", ans);
	return 0;
}

最小生成树 学习笔记1 - Kruskal