「Notice」最小生成树

@toc

定义

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

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

  Kruskal算法

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

---

算法流程

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

时间复杂度为 $O(m log 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;
}