#创作计划#最小生成树
2025-09-28 22:34:18
发布于：浙江
更新中......
对于最小生成树，我将会从一下几个角度进行讲解
目录
-
1.并查集
-
2.最小生成树
-
3.算法---kruskal
一、并查集
把并查集拆开看：
“并”，顾名思义就是合并；
“查”，顾名思义就是查找；
“集”，还是顾名思义就是集合。
可以把集合理解成几个本互不相干的部落，那么刚开始每个部落的首领就为本身。
部落：0 1 2 3 4
首领：0 1 2 3 4
而合并，可以理解为两个部落打架，输的一方被赢的一方吞并。
部落：0 1 2 3 4
︱ \ / \ /
首领：0 1 4
查找，即查找某个部落的首领。针对上一张表，可得出以下结果
查找0->0
查找1->1
查找2->1
查找3->4
查找4->4
其实细心的人会发现，这张图表十分像树，那么我们可以通过数组 来存储并查集， 表示第 个节点（部落）的父节点（首领）。
接下来上干货：
#include<iostream>
using namespace std;
int f[105];
int main(){
for(int i=1;i<=100;i++) f[i]=i; //初始化，一开始第i个节点的父节点为i
return 0;
}
查找实际上就是从节点开始，一步步往上找，直到找到最终的父节点，可以用以下函数实现。
int find(int x){ //查找节点x的最终父节点
if(x==f[x]) return x; //查找到了
return f[x]=find(f[x]); //新赋值父节点
}
由于函数通过数组直接返回节点父节点值，无需复杂计算，所以该函数时间复杂度为感人的 。
合并就简单了，只要将两个节点的父节点都改成相同的即可。
#include<iostream>
using namespace std;
int f[105];
int main(){
for(int i=1;i<=100;i++) f[i]=i; //初始化，一开始第i个节点的父节点为i
f[13]=f[21]; //节点21将节点13合并，也就是节点13的父节点改为了节点21的父节点
return 0;
}
此代码执行过后，find(f[13])=find(f[21])。
二、最小生成树
要理解最小生成树，我们先要明白什么是“生成树”。
图：由一组顶点和连接顶点的边组成。
连通图：图中任意两个顶点之间都存在路径。
树：一个没有环的连通图。
生成树：一个连通无向图的生成树是它的一个连通子图，它包含原图的所有顶点，但边数最少（恰好有 条边，其中 是顶点数），并且没有环。
简单来说，生成树就是用最少的边把图中所有的顶点都连通起来，并且保证没有回路。
举个例子：
想象一个城市网络，每个顶点代表一个城市，边代表城市之间的道路。这个城市网络本身可能有很多条路，甚至有多条路连接相同的两个城市（形成环）。那么，这个网络的一个“生成树”就是一套能让你从任何一个城市开车到任何其他城市，且道路数量最少的路线规划。这套规划里不会有“环路”或“冗余的道路”。
现在，我们给图的每条边加上一个权重的概念。权重可以代表距离、成本、时间等。
最小生成树就是：在一个带权连通无向图中，总权重和最小的那棵生成树。
核心目标：在保证所有点连通的前提下，选择总权重最低的边。
三、算法---kruskal
待更
有帮助，赞一个