最小生成树的两种算法


最小生成树是图论当中的重要知识,想要解决该类问题一般是有2种算法,分别是普利姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。

1.普利姆(Prim)算法

Prim算法跟之前用来求最短路算法的Dijkstra算法极其相似,主要分为两种,分别是稠密图和稀疏图。稠密图我们可以采用朴素版的Prim算法,而稀疏图我们要使用堆优化版的Prim算法(使用频率不多,一般使用Kruskal算法),这两种的时间复杂度分别是O(n2)和O(mlogn)。

算法流程:

先将所有的距离初始化成正无穷,然后进行n次迭代,每次迭代先找到不在集合内(未标记的)的距离最小的点,然后用t更新这个点到集合的距离(Dijkstra算法中是更新这个点到起点的距离),最后将t加入到集合当中(标记t),就完成了。

代码实现:

题目大意:一个n个点m条边的无向稠密图,如果该图存在最小生成树,输出最小生成树的树边权重之和,否则输出impossible。

Code:

#include <cstring>
#include <iostream>
#include <algorithm>
#define N 510
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim(){
    memset(dist,0x3f,sizeof dist);
    int res=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        if(i&&dist[t]==INF) return INF;
        if(i) res+=dist[t];
        st[t]=true;
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int t=prim();
    if(t==INF) printf("impossible");
    else printf("%d/n",t);
    return 0;
}

2.克鲁斯卡尔(Kruskal)算法

Kruskal与并查集有点相似,一般用作稀疏图,时间复杂度为O(mlogm)。

算法流程:

1.将所有边按权重从小到大排序  时间复杂度O(mlogm)

2.从小到大枚举每条边AB,权重为C。如果AB不连通,则将这一条边加入到这个集合中来

代码实现:

题目大意:一个n个点m条边的无向稀疏图,如果该图存在最小生成树,输出最小生成树的树边权重之和,否则输出impossible。

Code:

#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100010
#define M 200010
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
int p[N];
struct Edge{
    int a,b,w;
    bool operator<(const Edge &W)const{//重载运算符,可以写个cmp 
        return w<W.w;
    }
}edges[M];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int kruskal(){
    sort(edges,edges+m);
    for(int i=1;i<=n;i++) p[i]=i;//初始化并查集
    int res=0,cnt=0;
    for(int i=0;i<m;i++){
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        a=find(a),b=find(b);
        if(a!=b){
            p[a]=b;
            res+=w;
            cnt++;
        }
    }
    if(cnt<n-1) return INF;
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }
    int t=kruskal();
    if(t==INF) printf("impossible");
    else printf("%d/n",t);
    return 0;
}

–最小生成树–最小生成树–最小生成树–最小生成树–最小生成树–最小生成树–最小生成树–最小生成树–最小生成树–

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/276460.html

(0)
上一篇 2022年7月23日 18:53
下一篇 2022年7月23日 19:45

相关推荐

发表回复

登录后才能评论