21xrx.com
2025-03-27 06:31:59 Thursday
文章检索 我的文章 写文章
C++代码实现Prim算法
2023-07-02 05:14:48 深夜i     7     0
Prim算法 C++代码 最小生成树 堆优化 邻接表

Prim算法是一种用于解决最小生成树问题的算法，它是以节点为中心的贪心算法，可以保证生成树的最小权值。

在C++中，我们可以使用优先队列来实现Prim算法。以下是实现Prim算法的C++代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1e6;
const int INF = 0x3f3f3f3f;
struct Edge {
  int to, w;
  Edge(int to, int w) : to(to), w(w) {}
};
vector<Edge> adj[MAXN];
int dis[MAXN];
bool vis[MAXN];
int prim(int start) {
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  pq.push( start);
  int res = 0;
  while (!pq.empty()) {
    pair<int, int> u = pq.top(); pq.pop();
    int x = u.second;
    if (vis[x]) continue;
    res += u.first; vis[x] = true;
    for (Edge e : adj[x]) {
      if (!vis[e.to] && dis[e.to] > e.w) {
        dis[e.to] = e.w;
        pq.push(e.w);
      }
    }
  }
  return res;
}
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back( w);
    adj[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) dis[i] = INF;
  int st;
  cin >> st;
  dis[st] = 0;
  cout << prim(st) << endl;
  return 0;
}

其中，adj数组是存储节点的邻接表，dis数组用于记录每个节点到生成树的距离，vis数组表示每个节点是否已加入生成树。prim函数返回的是最小生成树的权值。

该程序首先读入图的节点数n、边数m并构建邻接表。然后读入起点st，将dis数组中st节点的距离设为0并将起点加入优先队列中。然后在每次循环中，取队列中的第一个节点，加入生成树并更新其邻接点的距离。需要注意的是，在每次更新dis数组时，都要将边的权值存储到dis数组中，而不是将节点到生成树的距离存储到dis数组中。

最后，该程序输出生成树的权值。

通过以上代码实现Prim算法，我们可以在C++中快速求解最小生成树问题。

  
  

评论区