最小生成树详解
例题链接
概述
求最小生成树的两种算法：
1.Kruskal算法
2.Prim算法
熟悉实现思路
下面的讲解比较好，代码可以看我写的。
这写的也太好了吧（我真的不是懒）
Kruskal算法（比较简单）
本质是 贪心+并查集
这个方法我记得离散数学学过，老师称其“避圈法”。田呈亮yyds！！！
//最小生成树板子 Kruskal算法 并查集实现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5100;
int a,b,fa[N],rx,ry,n,m;
ll c,ans;
struct edge
{
int u,v;
ll w;
}e[N<<1];
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
e[i].u=a;
e[i].v=b;
e[i].w=c;
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
rx=find(e[i].u);
ry=find(e[i].v);
if(rx!=ry)
{
ans+=e[i].w;
fa[rx]=ry;
}
}
cout<<ans<<endl;
}
Prim算法
链式前向星实现（未优化）
因为我所看的大佬的题解是通过“链式前向星”写的，又因为没学过，所以恶补了一下，发现不难。
链式前向星讲解
//最小生成树板子 Prim算法 链式前向星实现
/*
说在前面，注意：
注意区别数组的下标，
比如e数组的下标的含义为边的编号，而dis数组的下标的含义为点的编号，
所以在循环的时候要注意区分i的含义。
同时dis[i]表示编号为i的点到已选点集的最小距离（边权）
*/
#include<bits/stdc++.h>
#define ll long long
const int N=5005;
const int M=2e5+10;
const int INF=0x3f3f3f3f;
using namespace std;
struct edge
{
int v,w,next;
}e[M<<1];//无向图开两倍
int n,m,cnt;
int vis[N],dis[N],head[N];
void add(int u,int v,int w)//链式向前星 加边操作
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
int prim()
{
ll ans=0;
int minn=INF,now=1,tot=0;
for(int i=1;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)
{
vis[now]=1;minn=INF;//每次循环都要初始化
//注意这里不是枚举now点的所有连边，而是1~n
for(int i=1;i<=n;i++)//注意这里遍历的是点的编号
if(!vis[i]&&dis[i]<minn)
minn=dis[i],now=i;//找到最小的边，就是要加的边
for(int i=head[now];i;i=e[i].next)//注意这里遍历的是边的编号
{
int v=e[i].v;//边对应的点
if(!vis[v]&&e[i].w<dis[v]) dis[v]=e[i].w;//更新dis
}
ans+=minn;//加边
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++)
{
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
cout<<prim()<<endl;
}链式前向星（优先队列优化）
/*
确实和Dijkstra优先队列优化很像，所以不多解释了，另附Dijkstra算法优先队列优化代码
*/
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=5005;
const int M=2e5+10;
const int INF=0x3f3f3f3f;
int head[N],cnt;
int n,m,vis[N],dis[N],ans,tot;
struct edge
{
int v,w,next;
}e[M<<1];
void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
int prim()
{
priority_queue<pii,vector<pii>,greater<pii> > q;
q.push(pii(0,1));
fill(dis+1,dis+n+1,INF);
while(!q.empty() && tot<n)
{
int d=q.top().first,u=q.top().second;
q.pop();//勿忘
if(vis[u]) continue;
++tot;
vis[u]=1;//勿忘
ans+=d;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>e[i].w)
dis[v]=e[i].w,q.push(pii(e[i].w,v));
}
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1,u,v,w;i<=m;i++)
{
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
cout<<prim()<<endl;
return 0;
}
