C++实现最小生成树算法 |21xrx.com

C++实现最小生成树算法

2023-07-11 07:16:14 深夜i 16 0

C++ 最小生成树算法数据结构图论

最小生成树算法(Minimum Spanning Tree，简称MST) 是指在一个加权连通图中找到一棵生成树，使得树上所有边的权值之和最小。通常有两个经典的算法：普里姆算法和克鲁斯卡尔算法。这篇文章主要介绍使用C++实现最小生成树算法。

1.普里姆算法

普里姆算法是一种贪心算法，它是从任意一个节点出发，每次选择一条最小的边加入到生成树中，直到所有的节点被加入。在实现过程中，可以使用堆优化来提高算法效率。

C++代码:

const int MAXN = 100005;
vector<pair<int,int>> G[MAXN];
int vis[MAXN];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
int prim(){
  while(!q.empty())q.pop();
  memset(vis,0,sizeof(vis));//记得初始化！！！
  q.push(make_pair(0,1));
  int ans=0;
  while(!q.empty()){
    auto now = q.top();q.pop();
    int x = now.second,w = now.first;
    if(vis[x])continue;
    vis[x]=1;
    ans+=w;
    for(auto next:G[x]){
      if(!vis[next.first])
        q.push(make_pair(next.second,next.first));
    }
  }
  return ans;
}

2.克鲁斯卡尔算法

克鲁斯卡尔算法是一种贪心算法，它按照边权从小到大的顺序加入图中边，并使刚加入的边在加入后形成的子图中不产生闭合回路。通过并查集来判断是否加入边所在的节点已经属于同一个集合。

C++代码:

const int MAXN=100005;
struct edge int u;
bool cmp(const edge&a,const edge&b)return a.w<b.w;
int fa[MAXN];
int find(int x){
  return fa[x]==x?x:fa[x]=find(fa[x]);
}
void join(int u,int v){
  int x=find(u),y=find(v);
  if(x!=y)fa[x]=y;
}
edge e[MAXN];
int kruskal(int n,int m){
  for(int i=1;i<=n;i++)fa[i]=i;
  sort(e+1,e+m+1,cmp);
  int cnt=0,ans=0;
  for(int i=1;i<=m;i++){
    int u=e[i].u,v=e[i].v,w=e[i].w;
    if(find(u)==find(v))continue;
    join(u,v);
    ans+=w;
    cnt++;
    if(cnt==n-1)break;
  }
  return ans;
}

至此，我们完成了C++实现最小生成树算法。对于一般小规模图，以上两种算法都能够处理。对于大规模图，考虑通过大量的优化来提高算法效率。

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

下一篇: C++编程：实现十六进制转十进制函数

评论区

相似文章