最小生成树的算法代码c++
时间: 2024-04-13 17:22:27 浏览: 115
![ZIP](https://csdnimg.cn/release/download/static_files/pc/images/minetype/ZIP.png)
最小生成树有很多种生成方法,主要有普利姆算法和克鲁斯卡尔算法,通过C语言easyx图形库实现
![star](https://csdnimg.cn/release/wenkucmsfe/public/img/star.98a08eaa.png)
最小生成树是图论中的一个重要概念,用于找到一个连通图的最小权重生成树。常用的算法有Prim算法和Kruskal算法。
以下是Prim算法的C++代码示例:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9; // 无穷大
// 边的结构体
struct Edge {
int to, weight;
};
// Prim算法
int prim(vector<vector<Edge>>& graph, int start) {
int n = graph.size(); // 图的节点数
vector<int> dist(n, INF); // 存储节点到最小生成树的距离
vector<bool> visited(n, false); // 记录节点是否已经加入最小生成树
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; // 将节点标记为已访问
for (auto& edge : graph[u]) {
int v = edge.to;
int weight = edge.weight;
if (!visited[v] && weight < dist[v]) {
dist[v] = weight; // 更新节点到最小生成树的距离
pq.push(make_pair(dist[v], v)); // 将节点加入堆中
}
}
}
for (int i = 0; i < n; i++) {
totalWeight += dist[i]; // 计算最小生成树的总权重
}
return totalWeight;
}
int main() {
int n, m; // 节点数和边数
cin >> n >> m;
vector<vector<Edge>> graph(n); // 图的邻接表表示
for (int i = 0; i < m; i++) {
int u, v, weight;
cin >> u >> v >> weight;
graph[u].push_back({v, weight});
graph[v].push_back({u, weight});
}
int start; // 起始节点
cin >> start;
int totalWeight = prim(graph, start);
cout << "最小生成树的总权重为:" << totalWeight << endl;
return 0;
}
```
阅读全文
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)