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

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

2023-07-10 03:35:53 深夜i -- --

C++ Prim算法最小生成树

Prim算法是一种求解最小生成树的算法，它通过逐步添加连通的边来构造一棵最小生成树。这种算法的时间复杂度较低，常用于处理大量数据的问题。

C++是一种常用的编程语言，它的语法简洁、结构清晰，非常适合用于算法的实现。以下是使用C++实现Prim算法求最小生成树的步骤：

1.初始化一个空的集合S，用于记录已经连通的点集。

2.选择任意一个点作为起点，将其加入集合S。

3.对于每个不在集合S中的点，计算它与集合S中所有点的距离，选择距离最小的点，将其加入集合S，并将这条边加入最小生成树的集合中。

4.重复步骤3，直到所有点都被加入集合S。

下面给出了使用C++实现Prim算法求最小生成树的示例代码：


#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 0x3f3f3f3f
const int N = 100; //节点数
vector<pair<int, int> > adj[N]; //邻接表
int dist[N]; //距离数组
bool vis[N]; //判断是否访问过
void Prim(int s)
{
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
  //小根堆，存储每个节点到集合S的距离，以及节点编号
  for(int i=0; i<N; i++)
    dist[i] = MAX;
  dist[s] = 0;
  pq.push(make_pair(0, s));
  while(!pq.empty())
  {
    int u = pq.top().second;
    pq.pop();
    if(vis[u])
      continue;
    vis[u] = true;
    for(int i=0; i<adj[u].size(); i++)
    {
      int v = adj[u][i].first;
      int w = adj[u][i].second;
      if(!vis[v] && dist[v]>w)
      {
        dist[v] = w;
        pq.push(make_pair(dist[v], v));
      }
    }
  }
}
int main()
{
  //初始化邻接表
  adj[0].push_back(make_pair(1,3));
  adj[1].push_back(make_pair(0,3));
  adj[0].push_back(make_pair(2,1));
  adj[2].push_back(make_pair(0,1));
  adj[1].push_back(make_pair(2,1));
  adj[2].push_back(make_pair(1,1));
  adj[1].push_back(make_pair(3,4));
  adj[3].push_back(make_pair(1,4));
  adj[2].push_back(make_pair(3,1));
  adj[3].push_back(make_pair(2,1));
  Prim(0);
  int sum = 0;
  for(int i=0; i<N; i++)
    if(dist[i]!=MAX)
      sum += dist[i];
  cout << sum << endl;
  return 0;
}

上述代码中，小根堆使用了STL库中的优先队列，这个数据结构可以自动排序，并保证每次访问到的元素是距离最小的。每次从堆中取出距离最小的节点，并将它加入集合S中，然后更新与它相邻的节点的距离。

通过这种方式，我们可以很方便地实现Prim算法求最小生成树，这对于处理大量数据的问题非常有帮助。

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

下一篇: Visual C++可再分发组件

评论区

()

相似文章