用c++写一个邻接表Prim算法的代码
时间: 2024-02-13 12:00:28 浏览: 27
以下是使用C++语言编写的邻接表Prim算法的代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) {}
};
typedef vector<vector<Edge>> Graph;
int prim(const Graph& g, int start) {
int n = g.size();
vector<bool> visited(n, false);
vector<int> dist(n, INF);
vector<int> parent(n, -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, start));
dist[start] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (visited[u]) continue;
visited[u] = true;
for (const Edge& e : g[u]) {
int v = e.to;
int w = e.weight;
if (!visited[v] && w < dist[v]) {
dist[v] = w;
parent[v] = u;
pq.push(make_pair(dist[v], v));
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += dist[i];
}
return ans;
}
int main() {
int n, m;
cin >> n >> m;
Graph g(n);
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(g, 0);
cout << ans << endl;
return 0;
}
```
在这个代码中,我们首先定义了一个`Edge`结构体,用于存储一条边的目标顶点和权重。然后定义了一个`Graph`类型,用于存储邻接表表示的图。接着,我们实现了邻接表Prim算法的主函数`prim`,该函数接受一个邻接表表示的图和一个起始顶点,并返回该图的最小生成树的权值。在函数内部,我们使用了一个`visited`数组来记录每个顶点是否已经被访问过,使用一个`dist`数组来记录每个顶点到已访问顶点的最小距离,使用一个`parent`数组来记录每个顶点在最小生成树中的父节点。我们还使用了一个优先队列来存储当前已有的生成树到未被访问的顶点的所有边。最后,我们在`main`函数中读入图的信息,然后调用`prim`函数求解最小生成树并输出结果。
需要注意的是,在这个代码中我们实现了一个无向图的最小生成树算法。如果需要实现有向图的最小生成树算法,则需要对邻接表中的每个节点进行遍历,而不能直接采用邻接表中存储的边。