随着给定一个无向加权图,包含 n 个顶点和 m 条边,编写一段代码来找出一棵最小生成树
时间: 2024-05-12 13:14:22 浏览: 11
最小生成树算法有多种,其中比较常用的是Prim和Kruskal算法。以下是Prim算法的实现代码。
```
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1000;
const int INF = 0x3f3f3f3f;
struct Edge {
int to, w;
Edge(int _to, int _w): to(_to), w(_w) {}
};
int n, m; // n个顶点,m条边
vector<Edge> G[MAXN]; // 邻接表存图
bool vis[MAXN]; // 标记顶点是否已在生成树中
int dist[MAXN]; // 存储当前已经找到的生成树到每个点的最短距离
int prim(int s) { // s为起点
fill(dist, dist + n, INF); // 初始化距离
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, s}); // {距离,顶点},按距离从小到大排序
int ans = 0; // 最小生成树的权值
while (!pq.empty()) {
int u = pq.top().second; // 取出当前距离最小的顶点
pq.pop();
if (vis[u]) continue; // 如果已经在生成树中,跳过
vis[u] = true; // 标记为已访问
ans += dist[u]; // 更新最小生成树的权值
for (auto& e : G[u]) { // 遍历u的所有邻接边
int v = e.to, w = e.w;
if (!vis[v] && dist[v] > w) { // 如果v未被访问且到u的距离更短
dist[v] = w;
pq.push({dist[v], v});
}
}
}
return ans;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
G[u].emplace_back(v, w); // 加入一条u->v的边
G[v].emplace_back(u, w); // 加入一条v->u的边
}
cout << prim(0) << endl; // 从0号顶点开始构建最小生成树
return 0;
}
```
该代码的时间复杂度为O(mlogn),其中m为边数,n为顶点数。