最小生成树笔记
2026-03-16 21:53:30
发布于：广东
27阅读
0回复
0点赞
最小生成树（ 算法）详解
一、导言
最小生成树是信息学竞赛中图论部分的核心考点，CSP-S 2025 T2 就考查了该算法的应用，因此本文重点讲解 算法实现最小生成树的核心思路（内容若有不足，欢迎指正）。
二、前置知识：并查集
并查集是实现 算法的关键数据结构，必须先掌握其基本原理和用法。
补充说明：关于并查集的详细讲解可参考我的往期题解：并查集详解
三、最小生成树与 算法
3.1 最小生成树定义
最小生成树（）：在包含 个结点的带权无向连通图中，连通所有结点且总权值最小的子图（边数为 ）。
3.2 算法简介
求最小生成树的经典算法有两种： 和 ，其中 算法因实现简洁、适配竞赛场景，是算法竞赛中的首选，其时间复杂度为 （ 为边数）。
3.3 算法核心步骤
- 将图中所有 条边按权值从小到大排序；
- 依次遍历排序后的边，若当前边的两个端点未连通，则将该边加入生成树；
- 最终判断：若加入的边数达到 ，则输出总权值；否则说明图不连通，无最小生成树。
3.4 算法原理说明
为什么只添加“未连通端点”的边？
- 由于边是按权值从小到大排序的，若两个端点已连通，说明此前已有更小权值的边将二者连通；
- 此时再添加该边会形成环，违背“最小生成树无环且总权值最小”的核心要求。
四、实战例题：【模板】最小生成树
题目链接：洛谷 P3366 【模板】最小生成树
4.1 完整代码
#include<bits/stdc++.h>
using namespace std;
struct edge{int u,v,w;}e[200005];
int fa[5005],n,m,ans,cnt;
bool cmp(edge a,edge b){return a.w<b.w;}
int find(int x){
if(x!=fa[x]) return fa[x]=find(fa[x]);
return x;
}
void kruskal(){
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++){
int u=find(e[i].u),v=find(e[i].v);
if(u==v) continue;
ans+=e[i].w;
fa[v]=u,cnt++;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
kruskal();
if(cnt==n-1) cout<<ans;
else cout<<"orz";
return 0;
}
有帮助，赞一个