C++语言实现prim算法 |21xrx.com

C++语言实现prim算法

2023-07-07 07:06:28 深夜i 9 0

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

Prim算法是一种最小生成树算法，它是由J. Prim在1957年提出的。C++是一个广泛使用的编程语言，它具有良好的可移植性和高效的运行速度。在C++中实现Prim算法，可以有效地解决最小生成树问题。

首先，了解Prim算法的基本思路。Prim算法从图的一个连通给定节点开始，构造一个连通子图，一次加入一个与该连通子图相邻的权值最小的边，直到加入n-1条边形成一棵最小生成树。这个过程可以使用堆等数据结构来加速。

然后，根据Prim算法的思路，使用C++语言实现Prim算法。首先，定义一个Heap类，用于维护一个含有未加入子图的所有边的堆。在堆中，每个边与一个权重相关联，以便可以快速找到最小的边。建立好了堆之后，从任何给定的初始节点开始，选择一个最小权重的边，并将此边添加到最小生成树列表中。

在C++中实现Prim算法的实现过程如下：

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <functional>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 100010;
int N, M;
vector<pair<int, int> > G[MAXN];
priority_queue<pii, vector<pii>, greater<pii> > pq;
bool vis[MAXN];
void prim() {
  int mn = 0;
  pq.push(make_pair(0, 1));
  while (!pq.empty()) {
    pii e = pq.top(); pq.pop();
    if (vis[e.second]) continue;
    vis[e.second] = true;
    mn += e.first;
    for (int i = 0; i < G[e.second].size(); i++) {
      int v = G[e.second][i].first, w = G[e.second][i].second;
      if (!vis[v]) pq.push(make_pair(w, v));
    }
  }
  cout << mn << endl;
}
int main() {
  cin >> N >> M;
  for (int i = 1; i <= M; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    G[u].push_back(make_pair(v, w));
    G[v].push_back(make_pair(u, w));
  }
  prim();
  return 0;
}

在这段代码中，我们首先定义了一个Heap类，用于维护一个含有所有未加入子图的边的堆。具体而言，我们使用std::priority_queue类来实现堆，其中pair类用于存储边与权重的对。然后，我们从任意一个节点开始，找到一个最小权重的边，并将其添加到最小生成树中。这个过程重复n-1次，直到所有的边都添加到了最小生成树中。

总之，在C++中实现Prim算法是一个有趣且有用的项目。通过这个项目，我们可以进一步加深对Prim算法的理解，并掌握C++编程的相关技能。

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

下一篇: 《C++ Primer Plus》编程题答案

评论区

相似文章