Firstadjvex(g,v)算法代码c++
时间: 2024-01-03 16:03:26 浏览: 29
以下是使用邻接表表示图的无向图中求最小生成树的Prim算法代码实现,时间复杂度为O(ElogV):
```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> adj[MAXN];
int dist[MAXN]; // 记录当前节点到生成树的最小距离
bool vis[MAXN]; // 记录当前节点是否已经加入生成树
int Prim(int u, int n) {
memset(dist, INF, sizeof(dist));
memset(vis, 0, sizeof(vis));
dist[u] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, u));
int ans = 0;
while (!pq.empty()) {
int d = pq.top().first, x = pq.top().second;
pq.pop();
if (vis[x]) continue;
vis[x] = true;
ans += d;
for (int i = 0; i < adj[x].size(); i++) {
int y = adj[x][i].to, w = adj[x][i].w;
if (!vis[y] && dist[y] > w) {
dist[y] = w;
pq.push(make_pair(dist[y], y));
}
}
}
return ans;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(Edge(v, w));
adj[v].push_back(Edge(u, w));
}
int ans = Prim(1, n);
cout << ans << endl;
return 0;
}
```
其中,函数 `Prim(u, n)` 表示从节点 `u` 开始生成无向图 `G` 的最小生成树,并且 `G` 有 `n` 个节点。