最小生成树——Kruskal 算法
最小生成树(Minimum Spanning Tree,MST)是图论中的一个基本问题。
对于一个有 $n$ 个顶点的连通无向带权图,需要从中选出 $n-1$ 条边,使所有顶点都连通,并且这些边的权值之和最小。
Kruskal 算法采用贪心的思想,每次选择当前权值最小、且不会形成环的边,最终得到最小生成树。
一、算法思路
Kruskal 算法主要分为以下几个步骤:
- 将图中所有的边按照权值从小到大排序。
- 从权值最小的边开始依次遍历。
- 判断当前边连接的两个顶点是否已经连通。
- 如果已经连通,说明加入该边会形成环,直接跳过。
- 如果尚未连通,则将该边加入生成树,并累加权值。
- 当选取的边数达到 $n-1$ 时结束。
其中,判断两个顶点是否连通可以使用并查集。
并查集通过一个数组记录每个节点所属的集合。对于一条边 $(x,y)$,如果 find(x) 和 find(y) 的结果相同,就说明两个顶点已经属于同一个集合,不需要再加入这条边。
二、代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 10;
int n, m, ans, cnt, f[maxn];
struct point {
int x, y, z;
}edge[maxn];
int find(int x) {
if (x != f[x])
return f[x] = find(f[x]);
return f[x];
}
bool cmp(point x1, point x2) {
return x1.z < x2.z;
}
void Kruskal() {
sort(edge, edge + m, cmp);
for (int i = 0; i < m; i++) {
int fx = find(edge[i].x);
int fy = find(edge[i].y);
if (fx == fy)continue;
ans += edge[i].z;
f[fx] = fy;
if (++cnt == n - 1)break;
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> edge[i].x >> edge[i].y >> edge[i].z;
}
for (int i = 0; i < maxn; i++)f[i] = i;
Kruskal();
cout << ans << endl;
return 0;
}
三、代码分析
point 结构体用于存储边的信息,其中 x、y 表示边的两个端点,z 表示权值。使用 edge 数组保存输入的所有边。
cmp() 是排序比较函数,通过 sort() 将边按照权值升序排列。
f[] 是并查集数组,初始时每个节点的父节点都是自己:
for (int i = 0; i < maxn; i++)f[i] = i;
在 find() 函数中:
if (x != f[x])
return f[x] = find(f[x]);
这里使用了路径压缩。在查找一个节点所属集合的根节点时,同时将路径上的节点直接指向根节点,以减少之后的查找次数。
Kruskal 函数是整个程序的核心:
int fx = find(edge[i].x);
int fy = find(edge[i].y);
if (fx == fy)continue;
如果两个端点属于同一个集合,就跳过当前边。否则将当前边的权值加入 ans,并使用:
f[fx] = fy;
合并两个集合。
cnt 用于记录已经选择的边数。当选出的边达到 $n-1$ 条时,说明最小生成树已经构造完成,可以直接退出循环。
四、时间复杂度
Kruskal 算法主要的时间消耗在边的排序上。
假设图中有 $m$ 条边,排序的时间复杂度为:
并查集的查找和合并操作经过路径压缩后,通常也比较高效。
因此,Kruskal 算法的整体时间复杂度主要由排序决定,通常记为 $O(m\log m)$。
对于边数相对较少的稀疏图,Kruskal 算法是一种比较合适的最小生成树求解方法。

















不过问题也不少,我纠正一下。
首先是完全没有考虑图不连通的情况。程序只管把能选的边选出来,最后直接输出 `ans`,至于有没有成功构造出最小生成树,根本不检查。
其次,`ans` 用的是 `int`,边权稍微大一点就有整数溢出的风险。并查集合并也只是简单地 `f[fx] = fy`,没有按秩合并或按大小合并。
还有那个 `maxn = 1e6 + 10`,不管输入规模多大,都先把整个并查集数组初始化一遍。虽然算不上什么严重问题,但确实比较粗糙。
没有更多啦