21xrx.com
2025-03-30 03:22:43 Sunday
文章检索 我的文章 写文章
C++实现Prim算法
2023-07-04 17:57:59 深夜i     30     0
C++ Prim算法 图论 最小生成树 数据结构

Prim算法是一种常用于求解最小生成树的算法，它基于贪心策略，通过构建优先队列和辅助数组，每次选择最小的边加入最小生成树的集合中。C++是一种非常流行的编程语言，有着丰富的数据结构和算法库，非常适合用来实现Prim算法。

实现Prim算法的核心思想是：从图中的任意一点开始，选择与该点相连的所有边的最小值，并且与该点构成新的图，重复该过程，直到生成一颗包含所有节点的最小生成树。

在C++中，可以使用优先队列来保存所有的边，这样就能够方便地找到最小边。同时，通过记录每个节点的父节点和与该节点的最小边，可以方便地构建最小生成树。

以下是一个示例代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100010;
typedef pair<int, int> pii;
vector<pii> g[MAXN]; // 存储图中所有的边
int n, m; // 图中的节点数和边数
bool vis[MAXN]; // 标记节点是否被访问过
int p[MAXN]; // 记录每个节点的父节点
int d[MAXN]; // 记录每个节点与父节点的最小边
void Prim() {
  // 更新每个节点与父节点的最小边的初始值为无穷大
  for (int i = 1; i <= n; ++i) {
    d[i] = INT_MAX;
  }
  // 从第一个节点开始遍历
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  pq.push( 1);
  d[1] = 0;
  while (!pq.empty()) {
    pii t = pq.top(); // 取出队列中最小的边
    pq.pop();
    int u = t.second;
    if (vis[u])
      continue;
    
    vis[u] = true;
    // 遍历所有与该节点相连的边，并更新最小值
    for (pii& e : g[u]) {
      int v = e.first;
      int w = e.second;
      if (!vis[v] && w < d[v]) {
        d[v] = w;
        p[v] = u;
        pq.push({d[v], v}); // 将更新后的最小边加入队列中
      }
    }
  }
}
int main() {
  cin >> n >> m;
  // 读取边的信息
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  Prim();
  // 输出最小生成树的边数和边的长度
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (p[i]) {
      ans += d[i];
    }
  }
  cout << ans << endl;
  return 0;
}

在上述代码中，我们使用了优先队列来保存所有边，并且通过标记节点是否被访问来避免重复计算。通过遍历所有节点与其相邻的边，我们能够得到所有的最小边，并在其中选择最小的边加入最小生成树中。

通过以上代码，我们可以轻松地实现Prim算法。C++的标准库中有许多实用的数据结构和算法库，所以我们可以在不必重复造轮子的情况下，快速地实现一些复杂的算法和数据结构，提高我们的编程效率。

  
  

评论区