最小生成树

2022/7/13 6:20:08

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

基本算法:\(Kruskal\)算法和\(Prim\)算法

喜欢的算法动画演示

最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示,up主:WAY_zhong

喜欢的板子

以下代码引用自:题解 P3366 【【模板】最小生成树,作者:yhtwd

//Prim+邻接链表
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define R register int
using namespace std;

int k,n,m,cnt,sum,ai,bi,ci,head[5005],dis[5005],vis[5005];

struct Edge
{
    int v,w,next;
}e[400005];

void add(int u,int v,int w)
{
    e[++k].v=v;
    e[k].w=w;
    e[k].next=head[u];
    head[u]=k;
}

typedef pair <int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> > q;

void prim()
{
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()&&cnt<n)
    {
        int d=q.top().first,u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        cnt++;
        sum+=d;
        vis[u]=1;
        for(R i=head[u];i!=-1;i=e[i].next)
            if(e[i].w<dis[e[i].v])
                dis[e[i].v]=e[i].w,q.push(make_pair(dis[e[i].v],e[i].v));
    }
}

int main()
{
    memset(dis,127,sizeof(dis));
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(R i=1;i<=m;i++)
    {
        scanf("%d%d%d",&ai,&bi,&ci);
        add(ai,bi,ci);
        add(bi,ai,ci);
    }
    prim();
    if (cnt==n)printf("%d",sum);
    else printf("orz");
}

然后放个洛谷最高赞,感觉是不是有点奇技淫巧啊。最小生成树浅谈,作者:呢没理他
另外还看到有一个貌似蛮全的总结,生成树专题,作者:October

其他

链式前向星

(这名字好漂亮)
链式前向星详解,作者:ACdreamers

优先队列

(很熟悉了 不过还是放一下)
priority_queue,作者:Deribs4

Prim和DJ哥

Dijkstra:加入b到已拓展节点集合里面后

shortest_path[c] = min( shortest_path[b]+distance[b,c] , shortest_path[c] )

就是看看加入b后会不会源点a通过b而到达c的路径更短,是就更新。

Prim:加入b到已拓展节点集合里面后

min_edge[c] = min( distance[b,c] , min_edge[c] )

就是看看加入b后会不会b到c的枝条长度更短,是就更新。

引用自:Dijkstra 与 Prim 算法的区别,作者:rancho628


这俩个算法都是找出俩个集合,初始状态下,一个集合S只含有源点,另一个(V-S)含有图的其他顶点。然后是从V-S中挑出顶点到S中....但是这俩个算法还是有很大的区别的。

1,prim算法是用来求最小生成树的,而Dijkstra算法是用来求任意俩点间的最短路径问题.

2,边的权值修改方式不同。prim中,对V-S中的任意顶点,如果新进入到S中的顶点K,使得K到该顶点的距离最小,则修改该顶点的权值。而Dijkstra算法中,对v-s中的顶点,如果新加入S的顶点K,使得(源点到K的距离+<Vi,Vk>)小于加入K点前源点到改点的最短距离,则修改该顶点权值。

3,时间复杂度不同。prim算法中,必须求出n个顶点,n-1条边。而Dijkstra算法中最多求n个顶点。

4,出发点不同。prim算法是从任意顶点出发,到所有顶点都进入集合S为止。而Dijkstra算法是从源点开始到汇点结束。

引用自:关于prim算法与dijskra算法得区别,作者:暖阳下的好日子

碎碎念

技术学了蛮多的 但是还是感觉系统性上差了点意思
服了 我数据结构的书不会明年才能到吧



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


扫一扫关注最新编程教程