最小生成树一篇通（未完成）
2026-05-16 17:17:47
发布于：上海
感谢@Xylophone给这篇帖子提出的建议！
帖主是小白。欢迎提出建议！
——————————————————————————————————————————
本质上似乎都是贪心。毕竟叫最小生成树了。
1.Prim
用一个dis数组来记录到目前为止当前树中的点到其他点的最短边长。
先将一个随机的点（这里选择一号点）放入生成树，遍历它的边。
用它的边来更新dis。标记它。
这里用一个结论：任何时刻未标记的点中dis最小者，其dis值所对应的边一定在一颗最小生成树中。
把所有未标记点中dis最小的那个点标记，遍历它的边。
重复上述操作。
时间复杂度。
注意到这个过程其实很像dijkstra。所以不难想到它可以用优先队列优化。
时间复杂度.
不过。堆优化prim似乎是有很大的常数的。
理论上我们认为在稠密图的情况下堆优化prim会比kruskal快。但是实际上可能并不。
题目：最小生成树-模板
代码：(堆优化版本）
另：其实我并不清楚这个版本的优势在哪里。可能唯一的优点就是对我来说比较好些。因为和dijkstra很像嘛。
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
priority_queue<Node>pq;
vector<Node>v[N];
int dis[N];
bool vis[N];
typedef long long ll;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,zz;
cin>>x>>y>>zz;
v[x].push_back({y,zz});
v[y].push_back({x,zz});
}
for(int i=1;i<=n;i++)dis[i]=INT_MAX;
dis[1]=0;
pq.push({1,0});
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>len&&!vis[to]){
dis[to]=len;
pq.push({to,dis[to]});
}
}
}
int sum=0;
ll ans=0;
for(int i=1;i<=n;i++){
if(dis[i]!=INT_MAX)sum++;
ans+=dis[i];
}
if(sum!=n)cout<<"orz";
else cout<<ans;
return 0;
}
注意：更新dis[i]需要确保vis[i]没有被标记。
代码：（普通版本）
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5;
struct Node{
int z,q;
};
queue<Node>q;
vector<Node>v[N];
int dis[N];
bool vis[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
v[x].push_back({y,z});
v[y].push_back({x,z});
}
for(int i=1;i<=n+1;i++)dis[i]=INT_MAX;
dis[1]=0;
q.push({1,0});
while(!q.empty()){
Node sum=q.front();
q.pop();
int k=sum.z;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>len&&!vis[to])dis[to]=len;
}
int z=n+1;
for(int i=1;i<=n;i++){
if(!vis[i]&&dis[i]<dis[z])z=i;
}
if(z!=n+1)q.push({z,dis[z]});
}
long long ans=0;
for(int i=1;i<=n;i++){
if(dis[i]==INT_MAX){
cout<<"orz";
return 0;
}
ans+=dis[i];
}
cout<<ans;
return 0;
}
堆优化版本和普通版本的代码没什么过大的差异。
建议写普通版本。
2.kruskal
其实逻辑本身和prim是一样的。只是实现方式不同罢了。
kruskal：将所有边排序，根据边权从小到大遍历每条边。如果当前边连接的两个节点来自不同的连通块，那么就将这条边加入最小生成树。
插播小广告：并查集
想要写出kruskal，我们需要先学会并查集。
由于我早就修为散尽，所以我的并查集可能写的很烂，如果弄不懂的话可以直接看oi-wiki
并查集需要支持两个操作：1.合并（将两个元素所属集合合并） 2.查询（查询两个元素所属集合是否为同一个）
开始时，每个元素属于一个单独的集合。每个节点的父亲节点设为自己（使用一个f数组来存储当前节点的父亲节点）。
如何查询：当前节点为i，使得i=f[i]，直到i==f[i]。
考虑到集合内顺序并不重要，我们可以直接使得当前节点（i)的f[i]设置为根节点。（路径压缩）
合并：合并两棵树，只需要将一颗树的根节点改成另一棵树的根节点。
然后就可以开始挫代码了。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int z[N];
int zu(int xxx){
return (xxx==z[xxx])?xxx:z[xxx]=zu(z[xxx]);
}
struct Node{
int x,y,z;
}v[N];
bool cmp(Node a,Node b){
return a.z<b.z;
}
typedef long long ll;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>v[i].x>>v[i].y>>v[i].z;
}
sort(v+1,v+1+m,cmp);
ll ans=0;
int sum=1;
for(int i=1;i<=n;i++)z[i]=i;
for(int i=1;i<=m;i++){
int xx=v[i].x,yy=v[i].y;
if(zu(xx)!=zu(yy)){
ans+=v[i].z;
sum++;
z[zu(xx)]=z[zu(yy)];
}
}
if(sum!=n){
cout<<"orz";
return 0;
}
cout<<ans;
return 0;
}
并查集的每次操时间是一个极小的常数。
所以，kruskal的时间复杂度瓶颈在排序上。时间复杂度为。
prim从点开始，kruskal从边开始。不过它们本质相同。
应@Xylophone的建议，多加了一种方法：Boruvka
先把代码放一下，明天来写做法：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct Node{
int x,y,z;
}node[N];
int c[N];
int best[N];
bool can[N];
typedef long long ll;
ll ans;
int f(int x){
return (x==c[x])?c[x]:c[x]=f(c[x]);
}
bool better(int x,int y){
if(y==0)return 1;
if(node[x].z!=node[y].z)return node[x].z<node[y].z;
return x<y;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>node[i].x>>node[i].y>>node[i].z;
for(int i=1;i<=n;i++)c[i]=i;
bool if1=1;
int zong=n;
while(if1){
if1=0;
memset(best,0,sizeof best);
for(int i=1;i<=m;i++){
int p=f(node[i].x),q=f(node[i].y);
if(p==q)continue;
if(better(i,best[p]))best[p]=i;
if(better(i,best[q]))best[q]=i;
}
for(int i=1;i<=n;i++){
if(best[i]==0||can[best[i]])continue;
can[best[i]]=1;
if1=1;
zong--;
ans+=node[best[i]].z;
c[f(node[best[i]].x)]=f(node[best[i]].y);
//zong--;
}
}
if(zong==1)cout<<ans;
else cout<<"orz";
return 0;
}
我来了。接下来我的说明会参考洛谷的这篇题解。有兴趣的话可以直接去看原版而不是山寨版。不过山寨版会加入一些自己的见解。
我个人认为，boruvka其实算是prim和kruskal的结合体。
prim是从一个点开始，不断贪心地往外找最短边，最后构成一个大连通块。
而boruvka的每次增广，都会在每个连通块上找最短边。
而最短边有两个评判依据：
1.边权最短
2.（如果有边权相同）那么根据编号排序（也就是每条边的下标）
而连通块的形成又依靠并查集。这个部分又神似kruskal。
需要注意的点：
1.两个排序要求
2.每添加一条边，那就要将这条边进行标记。否则有可能出现加一条边两次的情况：
比如在遍历一号点的时候，我将这条边加入了一次最小生成树。
那么在遍历二号点的时候，（恰巧此时二号点的最短边也是这条边）如果我不标记，就会再次添加。
它的时间复杂度还挺特殊的。
每一次合并，需要遍历m条边。时间复杂度。
不过每一次合并后，连通块的个数都会减小一半。也就是说需要次，它们就可以合并成一颗最小生成树了。
所以时间复杂度是。（哦不过这个不像是堆优化prim那样参水）。
次的合并使boruvka十分特殊。
所以如果有题目想要考察这个算法，就一定会和这个性质密切相关。
明天会弄一些例题。
例题：买礼物
先说做法，再说想法。
做法：有优惠，一件礼物作为一个顶点，价格为边。建立零点，将零点与其他每个顶点连边，代表原价购买此商品。
由于在熟悉，所以prim和kruskal都会拿出来弄一遍。
prim:
#include<bits/stdc++.h>
using namespace std;
//prim
const int N=5e2+5;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
vector<Node>v[N];
priority_queue<Node>pq;
int dis[N];
bool vis[N];
int main(){
int a,b;
cin>>a>>b;
for(int i=1;i<=b;i++){
for(int j=1;j<=b;j++){
int x;
cin>>x;
if(x==0)continue;
v[i].push_back({j,x});
}
}
for(int i=1;i<=b;i++){
v[0].push_back({i,a});
v[i].push_back({0,a});
}
for(int i=0;i<=b;i++)dis[i]=INT_MAX;
dis[0]=0;
pq.push({0,0});
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>len&&!vis[to]){
dis[to]=len;
pq.push({to,dis[to]});
}
}
}
int ans=0;
for(int i=1;i<=b;i++)ans+=dis[i];
cout<<ans;
return 0;
}
在写prim的时候，我发现了一点比较有意思的事情。
我将vis[k]=1改动成了：
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>len&&!vis[to]){
dis[to]=len;
vis[to]=1;
pq.push({to,dis[to]});
}
}
如果加在了这里，那么如果后续我还能用别的边来优化dis，就优化不到了。
当时居然没注意，随意改了一下酿成大错qwq。
接下来是kruskal的版本。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
struct Node{
int x,y,z;
}node[N];
int c[N];
bool cmp(Node a,Node b){
return a.z<b.z;
}
int f(int x){
return (x==c[x])?x:c[x]=f(c[x]);
}
typedef long long ll;
int main(){
int a,b;
cin>>a>>b;
int n=0;//总共有多少条边
for(int i=1;i<=b;i++){
for(int j=1;j<=b;j++){
int xx;
cin>>xx;
if(xx==0)continue;
node[++n]={i,j,xx};
}
}
for(int i=1;i<=b;i++)node[++n]={0,i,a};
sort(node+1,node+1+n,cmp);
for(int i=0;i<=b;i++)c[i]=i;
ll ans=0;
for(int i=1;i<=n;i++){
int xx=node[i].x,yy=node[i].y;
if(f(xx)!=f(yy)){
ans+=node[i].z;
c[f(xx)]=f(yy);
}
}
cout<<ans;
return 0;
}
分析：
1.如何分析这道题目需要用到最小生成树
分析这个问题，先需要想到，这是一道和图论相关的问题。
如何将一个实际问题转化成为图。或者说如何识别有“图”。
它有点之间的关系。点i和点j之间的联系就是k[i][j]。
那么这个联系就可以变成边。
想在图论相关的题目中找”最小“。那么一般考虑：最短路，最小生成树，树形dp(我对树形dp不太了解，但应该也是相关）。
然后再看，这道题目需要求取整个图的所有边权。比较容易想到最小生成树。
最后分析复杂度：一共有条边。大约2e5。可以支撑的起的时间复杂度。
2.使用prim更好还是使用kruskal更好。
稠密图。推荐使用prim（非堆优化）。
好的，来看下一道例题：构造树
题目大意：一颗有n个结点的树，其中每条边有一个正整数边权。但并不知道这颗树的样子，只知道每两点之间最短路长度，但是这些最短路长度可能是错误的。请判断是否存在一颗树满足条件。
样例
输入：
3
0 2 7
2 0 9
7 9 0
输出：
YES
先说做法，再分析。
我们先将图根据题目所给出的信息建出来。
如果这n个点能构成一颗符合条件的树（指符合题目要求的树），那么一定是该图的生成树。
回顾kruskal算法的过程。一条点u到v，边权为w的边属于最小生成树，那么就代表其他所有边权小于w的边没能使得点u和点v连通。（这边的最小生成树指的是我们用图中的边建立的最小生成树）
这也就意味着在最后的生成树中（也就是我们在图中建立的生成树）这两点的路径一定会经过至少一条边权大于等于w的树。
这样下来，这两点之间的距离一定会大于等于w。只有在点u和点v直接相连的时候才能取到相等。
而点u和点v之间只会有一条边。边权是两点之间的最短距离。
因此只有在这颗树是最小生成树的时候，它才可能是满足条件的树。
这是大致的思路：
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
typedef long long ll;
ll a[N][N];
struct Node{
int z;
ll q;
};
vector<Node>vn[N];
ll dis[N];
int from[N];
bool vis[N];
vector<Node>v[N];
ll dis1[N];
void dfs(int x){
queue<int>q;
q.push(x);
while(!q.empty()){
int k=q.front();
q.pop();
for(int i=0;i<vn[k].size();i++){
int to=vn[k][i].z;
ll len=vn[k][i].q;
if(dis1[to]==-1){
dis1[to]=dis1[k]+len;
q.push(to);
}
}
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]==0&&i!=j){
cout<<"NO";
return 0;
}
if(a[i][j]!=0&&i==j){
cout<<"NO";
return 0;
}
v[i].push_back({j,a[i][j]});
}
}
for(int i=0;i<=n;i++)dis[i]=1e18;
dis[1]=0;
while(1){
int z=0;
for(int i=1;i<=n;i++){
if(dis[i]<dis[z]&&!vis[i])z=i;
}
if(z==0)break;
vis[z]=1;
if(z!=1){
vn[z].push_back({from[z],dis[z]});
vn[from[z]].push_back({z,dis[z]});
}
for(int i=0;i<v[z].size();i++){
int to=v[z][i].z;
ll len=v[z][i].q;
if(dis[to]>len&&!vis[to]){
dis[to]=len;
from[to]=z;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)dis1[j]=-1;
dis1[i]=0;
dfs(i);
for(int j=1;j<=n;j++){
if(dis1[j]==a[i][j])continue;
cout<<"NO";
return 0;
}
}
cout<<"YES";
return 0;
}
要记得加速输入输出。
有帮助，赞一个