最小生成树--kruskal算法_7-7 集合划分 分数 10 全屏浏览题目 切换布局 作者 任唯 单位 河北农业大学 当n=4

最小生成树–kruskal算法

---

ps：定理等非原创，参考资料--《信息学奥赛一本通（c++版）》。本文归总，代码皆原创，感谢阅览。

定理

首先，要知道树的一个定理：n各点用n - 1条边连接成一个连通块，形成的图形只可能是树，没有别的可能。

---

树的作用

就是用来解决如何用最小的“代价”用n - 1条边连接n个点的问题。

kruskal算法

一.定义

Kruskal（克鲁斯卡尔）算法是一种巧妙利用并查集来求最小生成树的算法。（bz:如果没学过 不熟悉并查集，可以先去补补课，以下放一些并查集基本操作代码<函数>）

并查集-基本操作（额外补充）

初始化

void initl (int x)
{
   
	for (int i = 0; i <= x; i++)father[i] = i;
}
1
2
3
4
5

寻找父节点

int find(int x)
{
   
	if(father[x] == x)return x;
	else return father[x] = find(father[x]);
}
1
2
3
4
5
6

合并两个集

void unionn(int x, int y)
{
   
	x = find(x
1
2
3