21xrx.com
2024-09-20 00:28:13 Friday
登录
文章检索 我的文章 写文章
C++代码实现Prim算法
2023-06-23 11:56:23 深夜i     --     --
C++ Prim算法 最小生成树 优先队列 图数据结构

Prim算法是一种常见的最小生成树算法，用于在一个带权连通图中找到一个子图，使得这个子图中所有边的权值之和最小。

C++是一种基于对象的编程语言，广泛应用于计算机科学和编程。下面介绍如何使用C++代码实现Prim算法。

Prim算法的实现步骤如下：

1. 选定一个任意顶点作为起点，加入到生成树中。

2. 在未加入生成树的点集中，选取与生成树中任意一个点相连的权值最小的点，并将这个点加入到生成树中。

3. 重复步骤2，直至所有点都加入到生成树中。

下面是用C++代码实现Prim算法的示例程序：



#include<iostream>


#include<cstdio>


#include<queue>


using namespace std;


const int MAXN=100010,INF=1<<30;


int head[MAXN],en[MAXN<<1],cap[MAXN<<1],dis[MAXN],nxt[MAXN<<1],tot=1,s,t,vis[MAXN],n,m;


void add(int u,int v,int c){


  en[++tot]=v;


  cap[tot]=c;


  nxt[tot]=head[u];


  head[u]=tot;


  en[++tot]=u;


  cap[tot]=0;


  nxt[tot]=head[v];


  head[v]=tot;


}


struct node{


  int w,id;


  bool operator<(const node& o)const


    return w>o.w;


  


};


priority_queue<node>Q;


void prim(int s){


  for(int i=1;i<=n;i++)dis[i]=INF;


  dis[s]=0;


  Q.push(nodes);


  while(!Q.empty()){


    int x=Q.top().id;Q.pop();


    if(vis[x])continue;


    vis[x]=1;


    for(int i=head[x];i;i=nxt[i]){


      int y=en[i];


      if(cap[i]&&dis[y]>cap[i]){


        dis[y]=cap[i];


        Q.push(node{dis[y],y});


      }


    }


  }


}


int main(){


  cin>>n>>m;


  for(int i=1;i<=m;i++){


    int u,v,c;


    cin>>u>>v>>c;


    add(u,v,c);


    add(v,u,c);


  }


  prim(1);


  int ans=0;


  for(int i=1;i<=n;i++)ans+=dis[i];


  cout<<ans<<endl;


  return 0;


}

以上代码中，首先定义了图的头结点，边端点和边权值数组，记录顶点是否已经加入的vis数组。

add函数用于添加边，由于Prim算法是针对无向图的，因此每条边应该添加两次。

prim函数用于实现Prim算法，首先将所有顶点的距离dis初始化为INF，将起点s加入优先队列中，并将其dis设置为0。

接着，每次从优先队列中取出距离最小的顶点x，并标记vis[x]=1。遍历与x相连的顶点y，如果边x->y未被访问且dis[y]>cap[i]，则将dis[y]更新为cap[i]，并将(y,dis[y])加入优先队列中。

最后，prim函数结束时所有点都已被加入到生成树中，dis数组记录了每个点到生成树上的最短距离。通过计算dis数组的和，可以得到生成树的最小权值和。

以上就是使用C++代码实现Prim算法的过程和示例程序。使用Prim算法可以有效地求解最小生成树，而C++语言提供了丰富的工具和类库，使得编写高效的算法代码变得更加容易。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复