GMQ出品，最小生成树（MST）概念、算法、基础例题及代码详解
一、生成树的定义
生成树：一个|V|个点的无向连通图中，取其中|V|-1条边，并连接所有的顶点，则为原图的一棵生成树。
树的属性：树是图的一种特殊形态。一个图G是树当且仅当以下任意一个条件成立：
-
G有V-1条边，无圈；
-
G有V-1条边，连通；
-
任意两点只有唯一的简单路径；
-
G连通，但任意删除一条边后不连通；
二、最小生成树的定义
最小生成树：在一张带权的无向连通图中，各边权和为最小的一棵生成树即为最小生成树。
简单讲：找出连接所有点的最低成本路线
示意图：
红边连接了所有顶点，
所以构成一棵生成树，
权和=1+2+2+4+4+7+8+9。
三、最小生成树的特性
环属性：一棵生成树上，增加一条边e，再删除e所在环上的最大边，会得到另一棵“更好”的生成树(如果e不是最大边)
剪切属性：在图中，剪切将顶点划分成两个不相交集合。交叉边为这些顶点在两个不同集合的边。对于任何一个剪切，各条最小的交叉边都属于某个MST，且每个MST中都包含一条最小交叉边。
最小边原则：图中权值最小的边(如果唯一的话)一定在最小生成树上。
唯一性：一棵生成树上，如果各边的权都不相同，则最小生成树是唯一的。反之不然。
四、最小生成树的算法
无向图的最小生成树（贪心思想）
-
Kruskal算法，适用于边少的图
-
Prim算法，适用于点少的图
Kruskal算法
算法思想
Kruskal算法是一种贪心算法，它是将边按权值排序，每次从剩下的边集中选择权值最小且两个端点不在同一集合的边加入生成树中，反复操作，直到加入了n-1条边。
算法步骤
-
将图G中的边按权值从小到大排序；
-
按照权值从小到大依次选边。若当前选取的边加入后使生成树T形成环，则舍弃当前边；否则标记当前边并计数；
-
重复“2”的操作，直到生成树T中包含n-1条边为止。否则当遍历完所有的边后，都不能选取n-1条边，表示最小生成树不存在。
算法的关键在于如何判定新加入的边会不会使图G‘产生环，在这里使用并查集，如果新加入边的两个端点在并查集的同一个集合中，说明存在环，需要舍弃这条边；否则保留当前边，并合并涉及的两个集合。用并查集优化后总的时间复杂度为O(mlogm+mα(n))
算法核心代码
bool cmp(constEdge &x,constEdge &y) {return x.z<y.z;}
int Getfather(int x) {//查找祖先
if(prt[x]==x)return x;
prt[x]=Getfather(prt[x]);
return prt[x];
}
void kruskal() {//kruskal核心程序
intf1,f2,k,i;k=0;
for(i=1;i<=n;i++)prt[i]=i;//初始化
for(i=1;i<=m;i++) {
f1=Getfather(a[i].x);
f2=Getfather(a[i].y);
if(f1!=f2){//非环
ans=ans+a[i].z;
prt[f1]=f2;//合并不相同的两个集合
k++;
if(k==n-1) break;
}
}
if(k<n-1) {
cout<<"Impossible"<<endl;
bj=0;
return;
}
}
int main(){
cin>>n>>m;
ans=0;
bj=1;
for(inti=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].z;//结构体存储
sort(a+1,a+m+1,cmp);
kruskal();
if(bj)cout<<ans<<endl;
}
该算法例题
1452 -- 【MST练习】修复公路2988
Description
A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
Input
第1行两个正整数N，M（N<=1000，M<=100000）
下面M行，每行3个正整数x, y, t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。（x<=N，y<=N，t<=100000）
Output
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1，否则输出最早什么时候任意两个村庄能够通车。
Sample Input
4 4
1 2 6
1 3 4
1 4 5
4 2 3
Sample Output
5
显然，这道题应该输出的是接边最大时间（即权值）
代码如下（注意注释内容）：
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
struct star{
int x,y,k;
}a[maxn];
bool did(star ax,star by) {
return ax.k<by.k;
}
int fa[maxn];//并查集
int getf(int x) {
if(fa[x]==x) {
return x;
}
else {
fa[x]=getf(fa[x]);
return fa[x];
}
}
int n,m;
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
fa[i]=i;
}
for(int i=1; i<=m; i++) {
cin>>a[i].x>>a[i].y>>a[i].k;//结构体存边
}
sort(a+1,a+m+1,did);
int sum=0;//记录接边次数
int t=0;//记录接边最大时间
for(int i=1; i<=m+1; i++) {//Kruskal算法过程
if(i==m+1) {//无法生成
cout<<"-1";
return 0;
}
if(sum>=n-1) break;//已经生成
if(getf(a[i].x)!=getf(a[i].y)) {//非环
sum++;//记录接边次数
fa[getf(a[i].x)]=getf(a[i].y);//合并
t=max(t,a[i].k);//针对本题记录接边最大时间
}
if(sum>=n-1) break;//已经生成
}
cout<<t<<endl;//输出接边最大时间
return 0;
}
1455 -- 【MST练习】联络员
Description
Tyvj已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着Tyvj网站的逐步壮大，管理员的数目也越来越多，现在你身为Tyvj管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。Tyvj是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。
目前你已经知道，Tyvj的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所有的管理员联通。
Input
第一行n，m表示Tyvj一共有n个管理员，有m个通信渠道;
第二行到m+1行，每行四个非负整数，p,u,v,w 当p=1时，表示这个通信渠道为必选通信渠道；当p=2时，表示这个通信渠道为选择性通信渠道；u,v,w表示本条信息描述的是u，v管理员之间的通信渠道，u可以收到v的信息，v也可以收到u的信息，w表示费用。
Output
输出仅一个整数表示最小的通信费用。
Sample Input
5 6
1 1 2 1
1 2 3 1
1 3 4 1
1 4 1 1
2 2 5 10
2 2 5 5
Sample Output
9
Hint
【样例解释】
1-2-3-4-1存在四个必选渠道，形成一个环，互相可以到达。需要让所有管理员联通，需要联通2号和5号管理员，选择费用为5的渠道，所以总的费用为9。
【注意】
U,v之间可能存在多条通信渠道，你的程序应该累加所有u,v之间的必选通行渠道
【数据范围】
对于30%的数据，n<=10，m<=100
对于50%的数据, n<=200，m<=1000
对于100%的数据，n<=2000，m<=10000
这道题存在“必选通信渠道”，但我们的解决方式也简单粗暴——直接连接解决一切（但是别忘了必选通道的价格应该计入答案）
代码如下：
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
struct star{
int x,y,k;
}a[maxn];
bool did(star ax,star by) {
return ax.k<by.k;
}
int fa[maxn];//并查集
int getf(int x) {
if(fa[x]==x) {
return x;
}
else {
fa[x]=getf(fa[x]);
return fa[x];
}
return 0x7fffffff;//这是不可能执行的（划掉
}
int n,m;
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
fa[i]=i;
}
int ans=0;//记录权值和
for(int i=1; i<=m; i++) {
int p,u,v,w;
cin>>p;
if(p==1) {//必选通道，直接连接
cin>>u>>v>>w;
fa[getf(u)]=getf(v);
ans+=w;
}
else cin>>a[i].x>>a[i].y>>a[i].k;
}
sort(a+1,a+m+1,did);
int sum=0;//记录接边次数
for(int i=1; i<=m; i++) {
if(sum>=n-1) break;
if(getf(a[i].x)!=getf(a[i].y)) {
sum++;
fa[getf(a[i].x)]=getf(a[i].y);
ans+=a[i].k;
}
if(sum>=n-1) break;
}
cout<<ans<<endl;
return 0;
}
Prim算法
算法步骤
- 将1号节点置入集合S中。
- 找到所有连接S中的节点和非S中的节点的边中的权值最小的那一条，并标记这条边，同时将连接的非S中的节点加入S集合。
- 重复“2”步骤，直到所有节点都在S中了。
任意时刻的中间结果都是一棵树：从某一个点开始，每次都花最小的代价，用一条边加进一个新的点。
证明过程
这里啥也没有
核心代码
这不是我的码风
int vst[505];//vst[i]标记顶点i是否加入最小生成树中
int d[505];//d[i]表示不是生成树中点i到当前生成树中点到最小值
int g[505][505],n,m,ans=0;
void Read()//读入数据,构建图
{
inti,j,x,y,w;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)g[i][j]=INF;
for(i=1;i<=m;i++){cin>>x>>y>>w;g[x][y]=g[y][x]=w;}
}
void Prim(intv0){
inti,j,k,minn;memset(vst,0,sizeof(vst)); //初始化生成树点集合
for(i=1;i<=n;i++)d[i]=INF;d[v0]=0;ans=0;for(i=1;i<=n;i++) //选择n个点
{
minn=INF;
for(j=1;j<=n;j++)//选择最小边if(vst[j]==0 && minn>d[j])
{
minn=d[j];
k=j;
}
vst[k]=1; //标记
ans+=d[k];for(j=1;j<=n;j++) //修改d数组
if(vst[j]==0&&d[j]>g[k][j])d[j]=g[k][j];
}
}
int main(){
Read();
Prim(1);
cout<<ans<<endl;
}
优化方法
该算法例题
1450 -- 【MST练习】局域网1123
Description
某个局域网内有n(n<=100)台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)<=1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的Σf(i,j)最大，请求出这个最大值。
Input
第一行两个正整数n和k；
接下来的k行每行三个正整数i j m，表示i,j两台计算机之间有网线联通，通畅程度为m。
Output
输出仅一个正整数，Σf(i,j)的最大值
Sample Input
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
Sample Output
8
废话少说，上代码：
#include<iostream>
#include<cstdio>
#define maxn 5010
#define yao_bu_ke_ji 0x3f3f3f3f//其实就是inf啦~~
using namespace std;
bool join[maxn];
int d[maxn];
int am[maxn][maxn];//邻接矩阵
int n,m;
int prim() {
int minn=yao_bu_ke_ji;
for(int i=1; i<=n; i++) {
d[i]=yao_bu_ke_ji;
}
d[1]=0;
int ans=0,jo;
for(int i=1; i<=n; i++) {
minn=yao_bu_ke_ji;
for(int j=1; j<=n; j++) {
if(join[j]==0) {//未加入集合
if(d[j]<minn) {//边权小
minn=d[j];//更新
jo=j;
}
}
}
join[jo]=1;//标记
ans+=d[jo];
for(int j=1; j<=n; j++) {
if(join[j]==0) {
d[j]=min(am[jo][j],d[j]);//更新d[]
}
}
}
return ans;
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
am[i][j]=yao_bu_ke_ji;//初始化为inf
}
}
int sum=0;//记录总权值
for(int i=1; i<=m; i++) {
int x,y,k;
cin>>x>>y>>k;
am[x][y]=k;
am[y][x]=k;
sum+=k;
}
cout<<sum-prim();//总权值减去保留权值得到答案
return 0;
}
1451 -- 【MST练习】繁忙的都市（SCOI2005）1406
Description
城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2．在满足要求1的情况下，改造的道路尽量少。
3．在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小。
任务：作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。
Input
第一行有两个整数n,m表示城市有n个交叉路口，m条道路。
接下来m行是对每条道路的描述，u, v, c表示交叉路口u和v之间有道路相连，分值为c。(1≤n≤300，1≤c≤10000，1≤m≤8000)
Output
输出两个整数s, max，表示你选出了几条道路，分值最大的那条道路的分值是多少。
Sample Input
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
Sample Output
3 6
代码来咯（注释请参考上一题）：
#include<iostream>
#include<cstdio>
#define maxn 5010
#define yao_bu_ke_ji 0x3f3f3f3f
using namespace std;
bool join[maxn];
int d[maxn];
int am[maxn][maxn];//邻接矩阵
int n,m;
int anm,anss;
int prim() {
int minn=yao_bu_ke_ji;
for(int i=1; i<=n; i++) {
d[i]=yao_bu_ke_ji;
}
d[1]=0;
int ans=0,jo;
for(int i=1; i<=n; i++) {
minn=yao_bu_ke_ji;
for(int j=1; j<=n; j++) {
if(join[j]==0) {
if(d[j]<minn) {
minn=d[j];
jo=j;
}
}
}
anm=max(anm,d[jo]);
anss++;
join[jo]=1;
ans+=d[jo];
for(int j=1; j<=n; j++) {
if(join[j]==0) {
d[j]=min(am[jo][j],d[j]);
}
}
}
return ans;
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
am[i][j]=yao_bu_ke_ji;
}
}
for(int i=1; i<=m; i++) {
int x,y,k;
cin>>x>>y>>k;
am[x][y]=k;
am[y][x]=k;
}
int did=prim();
cout<<anss-1<<" "<<anm;
return 0;
}
图片来源：Did's 课件
题目来源：Did及Xinyue
代码：GMQ原创出品
代码详解/注释：GMQ原创出品
有转载需求请私信：gao.maoqi.2007@foxmail.com