最小生成树可以选择的是很少的,一共就两个。

简述:
1.如果是稀疏图那么就用Kruskal算法.
2.如果是稠密图就用Prim算法.
ps:个人觉得Kruskal比较优越一点😁

Prim

怎么说,Prim的代码简介,思路好理解,而且操作起来容易一点。
但是他对于稀疏图的处理速度比Kruskal慢的多。
当然Prim算法是有堆优化版的,不过速度快不了多少,代码反而麻烦太多,所以不推荐也不写。

算法思路🎉

初始化:将**disk[rand()]**初始化为0,这样代码会好理解很多,好写很多。
1.查找集合可以到达的点中,花费最小的点,连接。
2.重复1步骤。就是这么简单O(∩_∩)O

Prim_code🎈

int h[N],ne[N],w[N],e[N],idx;
int dist[N];bool st[N];
int prim(int u){
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    dist[u]=0;int res = 0;
    For(i,1,n){
        For(j,1,n){
            int t = -1;
            if(!st[j]&&(t==-1||dist[j]<dist[t]))t=j;
        }
        if(dist[t]==INF)return INF;
        res+=dist[t];st[t]=true;
        for(int i = h[t];i!=-1;i=ne[i]){
            t = e[i];
            dist[t]=min(dist[t],w[i]);
        }
    }
    return res;
}

Kruskal

Kruskal是按照边的原则进行的,所以我们只需要遍历所有的边就OK,其中对并查集进行优化速度是非常可观的,当然这决定了它适合稀疏图的特性。当然稠密图可以碰碰运气😁。

算法思路🎉

初始化:cnt统计最小生成树集合中的点,所以一开始必须是1.需要对边权进行排序。
1.查找最小的边,看看是否属于同一集合
2.如果属于继续下一条边,如果不属于合并集合,继续操作
3.重复1,2;

Kruskal_code🎈

int p[N];
struct Edge{
    int a,b,w;
    bool operator<(const Edge &w)const{
        return w<W.w
    }
};
Edge e[N];
int find(int x){
    return p[x]==x?p[x]:p[x]=find(p[x]);
}
int kruskal(int m){
    sort(e,e+m);
    int res  = 0,cnt = 1;
    For(i,1,m){
        int a=e[i].a,b=e[i].b,w=e[i].w;
        a=find(a),b=find(b);
        if(a!=b){
                p[a]=b;//可以随机化处理
                res+=w;
                cnt++;//不用担心两个连通块,因为cnt就直接判出了
        }
    }
    return cnt<n?INF:res;//最小生成树生成的时候会进行环的处理,所以最小生成树中点的个数可以用来判断是否有最小生成树。
}

喜欢的话就打个赏吧,不打赏转发总可以吧💰。