用c++实现最小生成树普里姆算法
时间: 2023-12-03 11:40:46 浏览: 101
以下是使用C++实现最小生成树Prim算法的代码,其中使用了邻接表来表示图,使用了C++自带的优先队列(堆)来选择下一个最短路径,减少查找最短路径的时间。
```c++
#include <iostream>
#include <vector>
#include <queue>
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 vis[MAXN]; // 标记每个点是否已经在已选点集中
struct cmp {
bool operator() (const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second; // 小根堆
}
};
void prim(int s) {
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q; // 优先队列
fill(d, d + MAXN, INF);
fill(vis, vis + MAXN, false);
d[s] = 0;
q.push(make_pair(s, 0));
while (!q.empty()) {
int u = q.top().first;
q.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].to;
int w = G[u][i].w;
if (!vis[v] && w < d[v]) {
d[v] = w;
q.push(make_pair(v, d[v]));
}
}
}
}
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));
}
prim(1);
int ans = 0;
for (int i = 1; i <= n; i++) {
if (d[i] == INF) {
cout << "No Answer" << endl;
return 0;
}
ans += d[i];
}
cout << ans << endl;
return 0;
}
```
阅读全文
相关推荐














