最小生成树

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

基本算法：\(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算法得区别，作者：暖阳下的好日子

碎碎念

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

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