最小生成树的介绍
生成树的定义
在一个具有$ n $个点的无向连通图中，选出$ n-1 $条边将$ n $个点连接起来，构成一棵树。
注意：只有连通图才有生成树，非连通图只有生成森林。
最小生成树的定义
我们定义无向连通图的最小生成树为边权和最小的生成树。
最小生成树算法
Kruskal算法
实现
Kruskal算法是一种常见并且好写的最小生成树算法，由Kruskal发明。该算法的基本思想是从小到大加入边，是个贪心算法。如图：
来自于OI Wiki
算法虽简单，但需要相应的数据结构来支持……具体来说，维护一个森林，查询两个结点是否在同一棵树中，连接两棵树。
抽象一点地说，维护一堆 集合，查询两个元素是否属于同一集合，合并两个集合。
其中，查询两点是否连通和连接两点可以使用并查集维护。如果使用 $ O(m \log m) 的排序算法，并且使用 O(m \log n) $ 的并查集，就可以得到时间复杂度为 $ O(m \log m) $ 的 Kruskal 算法。
证明
思路很简单，为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 $ n-1 $ 条边，即形成了一棵树。
Prim算法
实现
Prim 算法是另一种常见并且好写的最小生成树算法。该算法的基本思想是从一个结点开始，不断向已生成的树中加入离这课树最近的点（而不是 Kruskal 算法的加边），也是贪心算法。如图：
来自于OI Wiki
具体来说，每次要选择距离最小的一个结点，以及用新的边更新其他结点的距离。其实跟 Dijkstra 算法一样，每次找到距离最小的一个点，可以暴力找也可以用堆维护。暴力维护的复杂度为$ O(n^2+m) $，堆优化的复杂度为 $ O((n+m) \log n) $ 。
证明
从任意一个结点开始，将结点分成两类：已加入的，未加入的。每次从未加入的结点中，找一个与已加入的结点之间边权最小值最小的结点。然后将这个结点加入，并连上那条边权最小的边。重复 $ n-1 $ 次即可。
代码
Kruskal算法
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 1000000000
#define N 1000100
int fa[N],x,y,z,nm,op,next,f1,f2,cnt,ans;
struct node
{
int f,t,v;
}e[N];
int cmp(node a,node b)
{
return a.v<b.v;
}
int find(int x)
{
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
e[++next].f=x;
e[next].t=y;
e[next].v=z;
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
f1=find(e[i].f);
f2=find(e[i].t);
if(f1!=f2)
{
fa[f1]=f2;
cnt++;
ans+=e[i].v;
if(cnt==n-1)
break;
}
}
cout<<ans;
return 0;
}
Prim算法
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 1000000000
#define N 1000100
typedef pair<int,int> pa;
priority_queue<pa,vector<pa>,greater<pa> >q;
int size,g[N],n,m,x,y,z,vis[N],len[N],sum;
struct node
{
int next,to,v;
}e[N];
void add(int x,int y,int z)
{
e[++size].to=y;
e[size].next=g[x];
g[x]=size;
e[size].v=z;
}
void prim()
{
for(int i=1;i<=n;i++)
len[i]=inf;
len[1]=0;
q.push(pa(0,1));
while(!q.empty())
{
int t=q.top().first,x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=1;
sum+=t;
for(int k=g[x];k;k=e[k].next)
{
int y=e[k].to;
if(e[k].v<len[y])
{
len[y]=e[k].v;
q.push(pa(len[y],y));
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
prim();
cout<<sum;
return 0;
}
—end—
