本文主要是介绍最小生成树的两种算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

1.普利姆(Prim)算法

Prim算法跟之前用来求最短路算法的Dijkstra算法极其相似，主要分为两种，分别是稠密图和稀疏图。稠密图我们可以采用朴素版的Prim算法，而稀疏图我们要使用堆优化版的Prim算法（使用频率不多，一般使用Kruskal算法），这两种的时间复杂度分别是O(n²)和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;
}

--最小生成树--最小生成树--最小生成树--最小生成树--最小生成树--最小生成树--最小生成树--最小生成树--最小生成树--

这篇关于最小生成树的两种算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！