prim算法程序c++
时间: 2023-12-06 17:37:58 浏览: 66
以下是使用C++实现Prim算法的代码,该算法用于生成无向图的最小生成树:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
struct Edge {
int to, w;
Edge(int to, int w) : to(to), w(w) {}
};
vector<Edge> G[MAXN];
int d[MAXN];
bool used[MAXN];
int prim(int s, int n) {
memset(d, INF, sizeof(d));
memset(used, false, sizeof(used));
d[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
q.push(make_pair(0, s));
int res = 0;
while (!q.empty()) {
pair<int, int> p = q.top();
q.pop();
int v = p.second;
if (used[v]) continue;
used[v] = true;
res += d[v];
for (int i = 0; i < G[v].size(); i++) {
Edge e = G[v][i];
if (d[e.to] > e.w && !used[e.to]) {
d[e.to] = e.w;
q.push(make_pair(d[e.to], e.to));
}
}
}
return res;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
G[u].push_back(Edge(v, w));
G[v].push_back(Edge(u, w));
}
int ans = prim(1, n);
cout << ans << endl;
return 0;
}
```