Prim、Kruskal算法求解最小生成树
关于最小生成树有两个很重要的算法：Prime(普利姆)算法和Kruskal(克鲁斯卡尔)算法，下面是这两个算法的代码上的基本实现：
Prime算法
该算法利用了最小生成树的MST性质，该算法很好的运用了贪心算法，其基本思想是随机选取一个结点，找出与该结点权值最小的结点，将该结点与之前的结点相连，并将该点加入集合，如此循环，直至找出所有的点，这样找出来的树就是最小生成树。由于该算法的时间复杂度与定点有关而与边数无关，所以适合求稠密网的生成树。时间复杂度(O(elogv))
【题意】：给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e3;
int n,m,cost[maxn][maxn],dis[maxn],v[maxn];
int prime()
{
int res=0,pos;
memset(dis,inf,sizeof(dis));
memset(v,0,sizeof(v));
for(int i=1;i<=n;++i)
dis[i]=cost[1][i];
v[1]=1;
for(int i=1;i<n;++i)
{
pos=0;
for(int j=2;j<=n;++j){
if(!v[j] && dis[j]<dis[pos])
pos=j;
}
if(pos==0) return inf;
v[pos]=1;
res+=dis[pos];
for(int j=2;j<=n;++j)
if(!v[j]) dis[j]=min(dis[j],cost[pos][j]);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>m)
{
memset(cost,inf,sizeof(cost));
for(int i=1;i<=m;++i){
int a,b,c;
cin>>a>>b>>c;
cost[a][b]=cost[b][a]=min(cost[a][b],c);
}
prime()==inf?cout<<"impossible"<<endl:cout<<prime()<<endl;
}
return 0;
}
2.Kruskal算法
先将所有边排个序，然后从权值小的开始加，如果两个点不在同一个连通分支里面，则将它们加入到一个连通分支里面，直到一共加入了节点数-1条边。
【题意】：给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2e5+10;
int fa[maxn],ran[maxn],n,m; //并查集中的父结点数组和秩序数组
struct node
{
int l,r,val; //左右端点及权值
}arr[maxn];
void init()
{
for(int i=1;i<=n;++i)
fa[i]=i,ran[i]=0;
}
int ffind(int x)
{
return x==fa[x]?x:fa[x]=ffind(fa[x]);
}
void unite(int x,int y)
{
int fx=ffind(x);
int fy=ffind(y);
if(fx==fy) return;
if(ran[fx]<ran[fy]) fa[fx]=fy;
else{
fa[fy]=fx;
if(fa[fx]==fa[fy]) ran[fx]++;
}
}
bool operator < (node &a,node &b)
{
return a.val<b.val; //重载小于号，按权值从小到大排序
}
int Kruskal()
{
int res=0,tot=0;
for(int i=1;i<=m;++i)
{
if(ffind(arr[i].l)!=ffind(arr[i].r))
{
tot++;
res+=arr[i].val;
unite(arr[i].l,arr[i].r);
}
if(tot==n-1) return res;
}
return inf;
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>m)
{
for(int i=1;i<=m;++i)
cin>>arr[i].l>>arr[i].r>>arr[i].val;
sort(arr+1,arr+m+1);
init();
int res=Kruskal(); //一定要先赋值在调用，否则会调用两次函数
res==inf?cout<<"impossible"<<endl:cout<<res<<endl;
}
}