C++代码实现Prim算法 |21xrx.com

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++语言提供了丰富的工具和类库，使得编写高效的算法代码变得更加容易。

上一篇: idea打包java可执行jar包

下一篇: NodeJS打造的网上商城简介

评论区

()

相似文章