用c++实现prim算法
时间: 2023-12-26 22:28:06 浏览: 28
以下是用C++实现Prim算法的示例代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 定义图的邻接矩阵表示
const int MAX_V = 100;
int graph[MAX_V][MAX_V];
// Prim算法实现
int prim(int start, int V) {
vector<bool> visited(V, false); // 记录顶点是否已访问
vector<int> dist(V, INT_MAX); // 记录顶点到生成树的最小距离
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小顶堆,存储顶点到生成树的距离和顶点编号
int totalWeight = 0; // 最小生成树的总权重
dist[start] = 0; // 起始顶点到自身的距离为0
pq.push(make_pair(0, start)); // 将起始顶点加入堆中
while (!pq.empty()) {
int u = pq.top().second; // 获取距离最小的顶点
pq.pop();
if (visited[u]) {
continue; // 如果该顶点已访问过,则跳过
}
visited[u] = true; // 标记该顶点为已访问
// 遍历与顶点u相邻的顶点v
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] != 0 && graph[u][v] < dist[v]) {
dist[v] = graph[u][v]; // 更新顶点v到生成树的最小距离
pq.push(make_pair(dist[v], v)); // 将顶点v加入堆中
}
}
}
// 计算最小生成树的总权重
for (int i = 0; i < V; i++) {
totalWeight += dist[i];
}
return totalWeight;
}
int main() {
int V, E;
cout << "请输入顶点数和边数:";
cin >> V >> E;
cout << "请输入边的信息(起点、终点、权重):" << endl;
for (int i = 0; i < E; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = w;
graph[v][u] = w;
}
int start;
cout << "请输入起始顶点:";
cin >> start;
int minWeight = prim(start, V);
cout << "最小生成树的总权重为:" << minWeight << endl;
return 0;
}
```