最小生成树入门 kruskal和堆优化的prim

定义：给定一个无向图，如果它的某个子图中的任意两个顶点都互相连通并且是一棵树，那么这棵树就叫生成树（Spanning Tree）如果边存在权值，那么使得边权和最小的生成树叫做最小生成树（MST Minimum Spanning Tree）。

求最小生成树的算法有两种：Prim和Kruskal。Prim在稠密图中效率更高，Kruskal在稀疏图中效率更高。

Prim类似于Dijkstra，从某个顶点出发，维护一个权值数组d[v]，寻找这个顶点周围权值最小的边，然后更新顶点，继续下去，当所有点都被更新时，d[v]就是最后的结果。

Kruskal就是把边权排序，从最小的边权开始，按照大小连接，当连接点为n-1个时，树就完成了，当中用并查集处理数据，连起来的点放入同一个集合（连入同一个根节点）。

#include<bits/stdc++.h>

using namespace std;
#define MAXN 10000005
int pa[MAXN],ra[MAXN],a[MAXN],n,k,ans,cnt;
bool is_prime[MAXN];
vector<int> prime;
struct edge
{
    int x,y,z;
}mp[MAXN];

int init(int n)
{
    for(int i=1; i<=n; i++)
    {
        pa[i]=i;
        ra[i]=0;
    }
}

int Find(int x)
{
    return pa[x]==x ? x : pa[x]=Find(pa[x]);
}

bool cmp(const edge &x,const edge &y)
{
    return x.z<y.z;
}

void kruskal()
{
    sort(mp,mp+k,cmp);           //排序
    for(int i=0;i<k;i++)
    {
         int x=Find(mp[i].x),y=Find(mp[i].y);           //取出根节点
         if(x==y) continue;                            //如果已经加入集合就跳过
         ans+=mp[i].z;
         pa[y]=x;
         cnt++;                                        //记录节点数
         if(cnt==n-1) break;
    }
}

Prim呢，就类似于dijkstra，我用的是使用堆优化的prim（其实就是用优先队列优化了dijkstra）邻接表存图，然后类似于dijkstra的方式比较距离起点最近的边，只不过把边按照边权排序，连满n条边时，这个生成树就是最小的。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int>pii;
#define INF 2147483647
int d[1000005],vis[1000005],cnt,sum,n,m;
vector<pii>e[1000005];

struct cmp                                          //自定义排序方法 因为我定义的优先队列里，边权和是第二个元素，如果直接greater，它会默认按第一个元素排序
{
    bool operator()(pii &a,pii &b)
    {
        return a.second>b.second;
    }
};

priority_queue <pii,vector<pii>,cmp > q;

void add_edge(int x, int y, int z)                 //邻接表存图
{
    e[x].push_back(make_pair(y, z));
    e[y].push_back(make_pair(x, z));
}

void init(int n)
{
    for (int i = 1; i <= n; i++) e[i].clear();     //初始化
    for (int i = 1; i <= n; i++) d[i] = INF;
}

void prim()
{
    d[1]=0;
    q.push(make_pair(1,0));
    while(!q.empty()&&cnt<n)
    {
        int now=q.top().first;
        int dis=q.top().second;
        q.pop();
        if(vis[now]) continue;
        cnt++;
        sum+=dis;
        vis[now]=1;
        for(int i=0; i<e[now].size(); i++)         //可以把这个i声明成register类型 提高效率
        {
            int v=e[now][i].first;
            if(d[v]>e[now][i].second)
            {
                d[v]=e[now][i].second;
                q.push(make_pair(v,d[v]));
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    init(n);
    for(int i=1; i<=m; i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
    }
    prim();
    if (cnt==n) printf("%d",sum);
    else printf("orz");
}

原文链接: https://www.cnblogs.com/youchandaisuki/p/8619555.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍