最小生成树算法笔记
最小生成树
我们先来看看关于“最小生成树”百度百科给出的解释。
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
如果单看这一句话，“连通图”、“极小连通子图”，这些概念是让人有一些懵，那么我用自己的理解来稍微直白地解释一下吧。
简述
对于n个点，存在m条带有权值的无向边将其相连（m>=n-1），选择合适的边使其各个点之间相互连通且权值最小，而找到的路径就叫最小生成树。
换一个实际一点的问题，假设n个独立起来的城市，现在需要建立道路使其n个城市之间可以相互到达。不同城市之间修路的费用有所不同，求修路的总费用最少是多少？
很明显，只需要n-1条边就可以将n个点连通，每条边都带有一定的权值。最小生成树的问题可以简化成就是找到n-1条花费最少的边使其连通。
实现
理解了什么是最小生成树之后，我们的目的很明显，就是找出n-1条边使其连通。下面我就来介绍一下常用的两种最小生成树的算法。
（一）Kruskal算法
我们是要选边嘛，很直接，Kruskal算法就是直接选边的。先将所有的边按照权值大小排序，排序后从最小的开始取。若所取边的两个点在选此边之前是还没有互相连通的，那么就可以选这条边。如果选此边之前已经连连通了，那么就不看这条边，看下一条比这个大一点的边。
简单明了，字里行间都透漏出 贪心 两个字。
对嘛，你要求最小，那么我就从最小开始，一直选到符合标准。
但是要掌握Kruskal算法必须先了解什么叫做 并查集 。为什么呢？因为选边的时候要判断是否可以取，而取的标准是否已经连通，而是否已经连通的话用并查集看一下他们的父亲是否相同即可。这里就不详细介绍并查集了。
用代码实现Kruskal部分呢就是这样：
void Kruskal()
{
sort(r+1,r+m+1,cmp);//先将所有边按照权值大小从小到大开始排序
for(int i=1;i<=m;i++)//其实不用找m遍，找到了n-1条边直接推出即可
{
int u=r[i].U,v=r[i].V,c=r[i].C;
int F_a=get_Father(u),F_b=get_Father(v);//get_Father(k)函数返回的是k点的父亲是谁，并查集的内容
if(F_a!=F_b)//如果这条边两边的父亲不一样，则代表没有这两个点没有连通
{
fa[F_a]=F_b;//将其连通
ans+=c;
}
}
if(ans>0)
printf("%d",ans);
else
printf("orz");
}
这不，看上去就简单易懂了。
而且Kruskal算法在解决一些特殊的最小生成树的问题中有奇效噢！！
但是注意，Kruskal算法中并查集一定要写好！！！！！因为如果写不好的话，很容易就wrong掉。我就因为这个wrong很多次了。
（二）Prim算法
刚刚所讲的Kruskal算法将重点放在了边上，那么Prim算法就是把重点放在了点上。
Prim的做法呢就是先从某一个点出发，因为最终每个点都会连着一条边，所以先取与这个点相连的权值最小的边。然后这样子就已经取了一条边，连接了两个点了。然后下一步就在连接这两个点的还未取的路径中取终点为未连接的点的权值最小的边相连，这样子就连接了三个点了。然后再在这三个点的边中找一条边……以此类推，直到第n-1个点加入之后，在这些点中找到连接仍未连接的点的最小权值的边，这样子就结束战斗了。
用程序来理解一下吧。
void Prim()
{
f[1]=true;//假设先从编号为1的点出发
for(int i=1;i<n;i++)
{
Road now=q.top();//这里是用了优先队列保存目前为止以加入的点所连接的边
while(f[now.to] && !q.empty())//优先队列按权值从小开始，那么找到一条边是去往未连接的点的，那直接取这个点
q.pop(),now=q.top();
ans+=now.cost;
f[now.to]=true;
for(int ki=p[now.to];ki;ki=a[ki].nex )//把新加入的点所连的路径都加入进优先队列
if(!f[a[ki].to])
q.push(a[ki]);
}
}其实呢，用优先队列反复地push和pop，在一些题目中应该会超时。别问我为什么知道，问就是改了不用优先队列后提交题目就A掉了，不显示超时了。
那么如果不用优先队列我们应该怎么弄呢？
我们要找的，是通往未连通的点的权值最小的边，先不把重点放在“边”，放在“点”，也就是找到目前离得最近的未连接的点，那通往这个点的边就是我们想要的呀！这样一来，就有另外一个方案了，那就是用dis数组来保存目前为止到其他点的距离，然后取dis中没去过的最小的点即可。
上程序理解一下吧。
void Prim()
{
f[1]=true;//从第一个点出发
for(int i=1;i<n;i++)
{
int ti=1;dis[ti]=oo;//这里利用一个ti来找出距离最小的点，因为dis[1]是不需要的，所以直接每一次赋值为最大，一次找最小。（因为dis[1]可能会被其他路径到达而刷新数值，故每次都保存）
for(int j=2;j<=n;j++)
if(!f[j] && (ti==-1 || dis[j]<dis[ti]))
ti=j;
if(ti==1)
return ;
f[ti]=true;
ans+=dis[ti];
for(int ki=p[ti];ki;ki=a[ki].nex)//更新现在已经生成的树到其他点的距离
dis[a[ki].to]=min(dis[a[ki].to],a[ki].cost);
}
}一般来说，理解上用优先队列好理解，但是用dis好一点不会超时。都OK吧看个人意愿使用。
而且这个dis数组可能在解决一些题目上是有妙用的噢！
例题
洛谷P3366 【模板】最小生成树
最基本的模板，可以尝试一下用两种算法来做。
Prim：
//Prim
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int T,n,m,k,cnt,ans,pi,p[500005],s;
struct Road{
int nex,to,cost,c;
friend bool operator < (Road i,Road j)
{
return i.cost > j.cost ;
}
}a[500005];
bool f[5005];
int dis[5005];
const int oo=1000000000;
void get_in(int ci,int vi,int mi)
{
pi++;a[pi].nex=p[ci];p[ci]=pi;a[pi].to=vi;a[pi].cost=mi;a[pi].c=ci;
}
void ready()
{
pi=0;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
{
p[i]=0;f[i]=false;dis[i]=oo;
}
ans=0;
for(int i=1;i<=m;i++)
{
int ci,vi,mi;
scanf("%d%d%d",&ci,&vi,&mi);
get_in(ci,vi,mi);
get_in(vi,ci,mi);
}
for(int ki=p[1];ki;ki=a[ki].nex)
dis[a[ki].to]=min(dis[a[ki].to],a[ki].cost);
}
bool judge_it()
{
for(int i=1;i<=n;i++)
{
if(!f[i])
return f[i];
}
return true;
}
void work()
{
f[1]=true;
for(int i=1;i<n;i++)
{
int ti=1;dis[ti]=oo;
for(int j=2;j<=n;j++)
if(!f[j] && (ti==-1 || dis[j]<dis[ti]))
ti=j;
if(ti==1)
return ;
f[ti]=true;
ans+=dis[ti];
for(int ki=p[ti];ki;ki=a[ki].nex)
dis[a[ki].to]=min(dis[a[ki].to],a[ki].cost);
}
}
int main()
{
ready();
work();
if(!judge_it())
ans=-1;
if(ans==-1)
printf("orz");
else
printf("%d",ans);
return 0;
}Kruskal
//Kruskal
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=5000+5,M=200000+5;
struct Road{
int U,V,C;
}r[M];
int fa[N],n,m,ans;
void read();
void work();
int get_Father(int root);
bool cmp(Road i,Road j)
{
if(i.C==j.C)
{
if(i.U ==j.U )
return i.V<j.V;
return i.U<j.U;
}
return i.C<j.C;
}
int main()
{
read();
work();
return 0;
}
void work()
{
for(int i=1;i<=m;i++)
{
int u=r[i].U,v=r[i].V,c=r[i].C;
int F_a=get_Father(u),F_b=get_Father(v);
if(F_a!=F_b)
{
fa[F_a]=F_b;
ans+=c;
}
}
if(ans>0)
printf("%d",ans);
else
printf("orz");
}
int get_Father(int root)
{
if(fa[root]==root) return root;
return fa[root]=get_Father(fa[root]);
}
void read()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&r[i].U,&r[i].V,&r[i].C);
sort(r+1,r+m+1,cmp);
for(int i=1;i<=n;i++)
fa[i]=i;
}
洛谷P1991 无线通讯网
这题呢就是找n-m大的路。那么就很简单啦，Kruskal算法，取到第n-m条路的时候就停，就是答案。
Kruskal算法真的好用，紫书里只写了Kruskal算法，没仔细讲Prim。
//找n-m大的路
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
int n,m;
double x[505],y[505],ans;
struct Road{
int c,v;
double dis;
}s[500005];
int fa[505],cnt,si;
int get_fa(int father)
{
if(fa[father]==father)
return father;
return fa[father]=get_fa(fa[father]);
}
bool cmp(Road i,Road j)
{
return i.dis > j.dis ;
}
void ready()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&x[i],&y[i]);
fa[i]=i;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
if(i!=j)
{
s[++si].c=i;s[si].v=j;s[si].dis=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
}
sort(s+1,s+si+1,cmp);
}
void Kruskal()
{
while(cnt<n-m && si)
{
int ci=s[si].c,vi=s[si].v;
double d=s[si].dis;si--;
fa[ci]=get_fa(fa[ci]);
fa[vi]=get_fa(fa[vi]);
int f_c=get_fa(ci),f_v=get_fa(vi);
if(f_c!=f_v)
{
fa[f_c]=f_v;
cnt++;
ans=d;
}
}
printf("%.2lf",ans);
}
int main()
{
ready();
Kruskal();
return 0;
}
洛谷P1396 营救
这题就有一点小特别，但是还是可以用Kruskal去做。
用Kruskal去做的话，当s和t共同列入的时候输出答案即可。但还是逃脱不出最小生成树的结构。
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int N=10005,M=20005,oo=1000005;
struct Road{
int u,v,w;
}a[2*M];
int n,m,s,t,fa[N],cnt;
bool cmp(Road i,Road j)
{
return i.w > j.w;
}
int get_father(int father)
{
if(fa[father]==father)
return father;
return fa[father]=get_father(fa[father]);
}
void ready()
{
freopen("in.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
cin>>a[i].u>>a[i].v>>a[i].w;
for(int i=1;i<=n;i++)
fa[i]=i;
}
void Kruskal()
{
sort(a+1,a+m+1,cmp);
while(cnt<n && m)
{
int ui=a[m].u,vi=a[m].v,wi=a[m].w;m--;
int f_a=get_father(ui),f_b=get_father(vi);
if(f_a!=f_b)
{
fa[f_a]=f_b;
cnt++;
}
if(get_father(s)==get_father(t) )
{
cout<<wi;
return ;
}
}
}
int main()
{
ready();
Kruskal();
return 0;
}
洛谷P2121 拆地毯
这题呢就是找第k大的路的最大生成树。最大生成树怎么做呢？Kruskal算法排序后换个顺序取边就可以啦。
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int N=100005,M=200005,oo=1000005;
struct Road{
int u,v,w;
}a[2*M];
int n,m,k,fa[N],cnt,ans;
bool cmp(Road i,Road j)
{
return i.w < j.w;
}
int get_father(int father)
{
if(fa[father]==father)
return father;
return fa[father]=get_father(fa[father]);
}
void ready()
{
freopen("in.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
cin>>a[i].u>>a[i].v>>a[i].w;
for(int i=1;i<=n;i++)
fa[i]=i;
}
void Kruskal()
{
sort(a+1,a+m+1,cmp);
while(cnt<n && m)
{
int ui=a[m].u,vi=a[m].v,wi=a[m].w;m--;
int f_a=get_father(ui),f_b=get_father(vi);
if(f_a!=f_b)
{
fa[f_a]=f_b;
cnt++;
ans+=wi;
}
if(cnt==k)
{
cout<<ans;
return ;
}
}
}
int main()
{
ready();
Kruskal();
return 0;
}
总结
最小生成树的话，目前为止见过的题目用Kruskal算法做得比较多，但是一定要注意并查集不要写错！这个很重要。
但也并不是说就可以不掌握Prim，说不定到时候会出一道题专门卡Kruskal算法的呢嘿嘿嘿。
这里就讲最小生成树的两种算法介绍至此啦。
如果有什么问题不懂，可以问问我，我会尽力回答。如果文章有什么问题或者我有表达错的地方，也希望能够指出。
谢谢大家，共同努力进步。
恒生电子公司氛围 49人发布
