普利姆最小生成树算法c++

普利姆最小生成树算法（Prim's algorithm）是一种用来求解无向图的最小生成树的算法，它采用的是贪心策略。该算法的基本思想是：从任意一个顶点开始，不断地将与当前最小生成树集合相邻的、且权值最小的边加入到最小生成树集合中，直至所有顶点都加入到最小生成树集合中。

以下是普利姆算法的C++代码实现：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct Edge
{
    int u,v,w;
}e[maxn];//边 
int n,m;
int dis[maxn],vis[maxn],ans;//dis数组记录某个点到已有的最小生成树集合的距离 
vector<int> G[maxn];//邻接表 
void prim()
{
    memset(dis,0x3f,sizeof(dis));
    dis=0;//从1号点开始扩展 
    priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > > q;//小根堆 
    q.push(make_pair(0,1));//把1号点和0放入小根堆 
    while(!q.empty())
    {
        pair<int,int> now=q.top();
        q.pop();
        if(vis[now.second]) continue;//如果这个点已经被访问过了，就跳过 
        vis[now.second]=1;//标记为已访问 
        ans+=now.first;//累加权值 
        for(int i=0;i<G[now.second].size();i++)
        {
            int v=G[now.second][i];
            if(dis[v]>e[v].w&&!vis[v])
            {
                dis[v]=e[v].w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        G[e[i].u].push_back(i);//加入邻接表 
        G[e[i].v].push_back(i);
    }
    prim();
    printf("%d",ans);
    return 0;
}