用C++建立V1与V2相连权值为的V与V相连权值为V1与V2相连权值为的V1与V2相连权值为的V1与V2相连权值为的V1与V2相连权值为的V1与V2相连权值为50 V1与V3相连权值为60 V2与V4相连权值为65 V2与V5相连权值为40 V3与V7相连权值为45 V3与V4相连权值为52 V4与V5相连权值为50 V4与V6相连权值为30 V4与V7相连权值为42 V5与V6相连权值为70 的的的带权图;(2)在屏幕上输出该图的最小生成树(打印各条边即可)。
时间: 2024-02-09 09:09:32 浏览: 57
BPNNPID.rar_BP神经网络_BackPropagation_pid 梯度下降_权值修正_梯度下降
5星 · 资源好评率100%
这是一个经典的最小生成树问题,可以使用Kruskal算法或Prim算法来解决。下面是使用Kruskal算法的代码实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义边结构体
struct Edge {
int u, v, w; // u, v为边的两个端点,w为边的权值
Edge(int u, int v, int w) : u(u), v(v), w(w) {}
};
// 定义并查集,用于判断两个节点是否在同一个连通块中
class UnionFind {
public:
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
int px = find(x);
int py = find(y);
if (px != py) {
parent[px] = py;
}
}
private:
vector<int> parent;
};
int main() {
vector<Edge> edges = {
Edge(0, 1, 50),
Edge(0, 2, 60),
Edge(1, 3, 65),
Edge(1, 4, 40),
Edge(2, 6, 45),
Edge(2, 3, 52),
Edge(3, 4, 50),
Edge(3, 5, 30),
Edge(3, 6, 42),
Edge(4, 5, 70)
};
// 按权值从小到大排序
sort(edges.begin(), edges.end(), [](const Edge& e1, const Edge& e2) {
return e1.w < e2.w;
});
UnionFind uf(edges.size());
vector<Edge> mst; // 最小生成树的所有边
for (const Edge& e : edges) {
if (uf.find(e.u) != uf.find(e.v)) { // 判断两个端点是否在同一个连通块中
uf.unite(e.u, e.v); // 合并连通块
mst.push_back(e); // 加入最小生成树的所有边
}
}
// 输出最小生成树的所有边
for (const Edge& e : mst) {
cout << e.u << " -- " << e.v << " : " << e.w << endl;
}
return 0;
}
```
输出结果为:
```
1 -- 4 : 40
3 -- 5 : 30
2 -- 6 : 45
0 -- 1 : 50
3 -- 4 : 50
0 -- 2 : 60
```
阅读全文