浅谈最小生成树
算法·理论
浅谈最小生成树
最小生成树定义
生成树是从一张无向连通图中选取一些边构成一张新图，使得这张图是是一棵树。最小生成树即为边权和最小的生成树。
最小生成树的一些性质：
-
在最小生成树上，两个点路径上经过的边权最小值即是这两个点在原图中所有路径中可能经过边的边权最小值。
-
对于原图中所有合法的最小生成树，他们的边权构成是相同的。
我们接下来将介绍两种求最小生成树的方法，即 Kruskal 和 Prim。
Kruskal
Kruskal 是一种贪心算法，基本思想为：从小到大加入边，我们需要同时判断两个东西：
- 当前的最小边权的边
- 这条边所连接的两个点的连通性
对于第一个问题，可以对原图的边进行排序，然后按顺序判断是否满足 1 即可。
对于第二个问题，我们可以用并查集来维护两个点之间的连通性，如果两个点在并查集内部有共同祖先，那么就说明这两个点是联通的即可判断连通性。
Prim
如果说 Kruskal 是找满足条件的边，那么 Prim 就是找满足条件的点。
就是在目前没有加入连通块的点中，选一个距离连通块最近的点加入。
想要找到这个点，就需要思考三个东西
- 现在有哪些没有加入连通块的点
- 这些点距离连通块的距离是多少
- 距离最近的点是什么
我们发现，其实只需考虑和当前连通块有连边的那些点， 也就是说，我们只需要保存当前和连通块有连边的点就行了。
同时，我们也就是只需要在每次加入新的点之后，更新一下这个点连接的点和他们到连通块的距离。
然后每次取出距离连通块最近的点，然后向堆中加入其相邻的点，或者更新相邻点到当前连通块的距离。
Boruvka
Boruvka 算法利用了分治的思想。
初始时，每个节点自成一个联通分量，之后每次遍历，以每个联通分量为中心，找出与其距离最近的其他联通分量。而连接这两个联通分量的边为最小边。
然后把这条最小边加入最小生成树中，并把这两个联通分量合并。
直到图中只剩一个联通分量为止。
Kruskal 和 Prim 的区别
Kruskal：
- 基本思想：按边权值从小到大选择，不形成环。
- 数据结构：并查集。
- 适用图的类型： 稀疏图 (边少)
Prim：
- 基本思想：从一个顶点开始，逐步扩展最小生成树
- 数据结构：优先队列 (堆)。
- 适用图的类型： 稠密图 (边多)
模版
Kruskal：
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=200020,INF=0x3f3f3f3f;
int n,m;
int p[N];
struct Node
{
int a,b,w;
bool operator<(const Node &W)const{
return w<W.w;
}
}ku[M];
int find(int x)
{
if (p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int kul()
{
sort(ku,ku+m);
for (int i=0;i<n;i++) p[i]=i;
int ans,cnt;
ans=cnt=0;
for (int i=0;i<m;i++)
{
int a=ku[i].a;
int b=ku[i].b;
int w=ku[i].w;
int fax=find(a),fay=find(b);
if (fax!=fay)
{
p[fax]=fay;
ans+=w;
cnt++;
}
}
if (cnt<n-1)return INF;
return ans;
}
int main()
{
cin>>n>>m;
for (int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
ku[i].a=a;
ku[i].b=b;
ku[i].w=w;
}
int kull=kul();
if (kull==INF)cout<<"orz";
else cout<<kull;
return 0;
}
Prim：
#include<bits/stdc++.h>
using namespace std;int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
#define inf 123456789
#define maxn 5005
#define maxm 200005
struct edge
{
int v,w,next;
}e[maxm<<1];
int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans;
bool vis[maxn];
void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
void init()
{
n=read(),m=read();
for(int i=1,u,v,w;i<=m;++i)
{
u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
}
}
int prim()
{
for(int i=2;i<=n;++i) dis[i]=inf;
for(int i=head[1];i;i=e[i].next) dis[e[i].v]=min(dis[e[i].v],e[i].w);
while(++tot<n)
{
int minn=inf;
vis[now]=1;
for(int i=1;i<=n;++i)
{
if(!vis[i]&&minn>dis[i])
{
minn=dis[i];
now=i;
}
}
ans+=minn;
for(int i=head[now];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>e[i].w&&!vis[v]) dis[v]=e[i].w;
}
}
return ans;
}
int main()
{
init();
printf("%d",prim());
return 0;
}
Boruvka
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 5005;
const int MAXM = 200005;
const int INF = 0x3f3f3f3f;
struct Edge {
int u, v, w;
} edges[MAXM];
int parent[MAXN], bestEdge[MAXN], bestWeight[MAXN];
int find(int u) {
return parent[u] == u ? u : parent[u] = find(parent[u]);
}
void boruvka(int N, int M) {
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
int totalWeight = 0;
int components = N;
bool updated;
do {
updated = false;
memset(bestEdge, -1, sizeof(bestEdge));
memset(bestWeight, INF, sizeof(bestWeight));
// 为每个连通块寻找最小边
for (int i = 0; i < M; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
int rootU = find(u), rootV = find(v);
if (rootU == rootV) continue;
if (w < bestWeight[rootU]) {
bestWeight[rootU] = w;
bestEdge[rootU] = i;
}
if (w < bestWeight[rootV]) {
bestWeight[rootV] = w;
bestEdge[rootV] = i;
}
}
// 合并连通块
for (int i = 1; i <= N; i++) {
if (bestEdge[i] != -1) {
int e = bestEdge[i];
int u = edges[e].u, v = edges[e].v, w = edges[e].w;
int rootU = find(u), rootV = find(v);
if (rootU != rootV) {
parent[rootU] = rootV;
totalWeight += w;
components--;
updated = true;
}
}
}
} while (updated);
if (components == 1) {
cout << totalWeight << endl;
} else {
cout << "orz" << endl;
}
}
int main() {
int N, M;
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
boruvka(N, M);
return 0;
}
应用：
最小生成树算法的基础应用
- 在多个节点之间铺设线路，求最小成本。
- 连接所有村庄的最低修路成本。
- 要求所有城市通电，求最小电缆长度。
最小生成树算法的进阶应用
- 次小生成树。
- 最小生成树计数。
例题
我们给出如下几道例题：
1. 最短网络：这道题要求出总光纤长度最短的方案，就是最小生成树定义。一道纯板子
首先，题目给的是邻接矩阵的形式，转化成 Kruskal 对的存储形式 然后跑最小生成树，最后树的边权和就是答案
#include<bits/stdc++.h>
using namespace std;
int n,a[110][110],ans,tot;// n: 顶点数, a: 邻接矩阵, ans: 最小生成树的总权重, tot: 已选边数
struct Node
{
int u,v,w;
bool operator<(const Node &N)const
{
return w<N.w;
}
}e[100010];
int cnt,fa[1000100];
int found(int x)// 并查集的查找函数，带路径压缩
{
if (fa[x]==x) return x;
return fa[x]=found(fa[x]);
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
cin>>a[i][j];
if (i<j) e[++cnt]={i,j,a[i][j]};
}
for (int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+cnt+1);
// Kruskal算法求最小生成树
for (int i=1;i<=cnt;i++)
{
int u=e[i].u;
int v=e[i].v;
int w=e[i].w;
int fatheru=found(u),fatherv=found(v);
if (fatheru!=fatherv)
{
fa[fatheru]=fatherv;
tot++;
ans+=w;
}
// 如果已经选了n-1条边，最小生成树构建完成
if (tot==n-1) break;
}
cout<<ans;
return 0;
}
2. 局域网：题目中要求在保证联通的情况下使得去除的网线边权和最大，即保留的边权和最小，我们考虑求最小生成树
答案即是原图边权和减去最小生成树边权和。
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int to,len;
};
int n,m;
vector<Node>e[100010];
bool st[100010];
int dis[100010],ans,tot;
void prim(int rt)
{
priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>> >q;
dis[rt]=0;
q.push(pair<int,int>(dis[rt],rt));
while(!q.empty())
{
int u=q.top().second,w=q.top().first;
q.pop();
if(st[u]) continue;
st[u]=1;
ans+=w;
for (auto v:e[u])
{
if(dis[v.to]>v.len)
{
dis[v.to]=v.len;
q.push(pair<int,int>(dis[v.to],v.to));
}
}
}
}
int main()
{
memset(dis,0x3f,sizeof dis);
cin>>n>>m;
for (int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
tot+=w;
}
prim(1);
cout<<tot-ans;
}
总结
对于 Kruskal 与 Prim 算法仍有一定优化空间，这里不做过多赘述。朴素版已经能满足大部分比赛的需求。