boost 自定义边的最小生成树 c++ 代码
时间: 2023-07-22 19:45:19 浏览: 57
以下是使用 Boost Graph Library 实现自定义边的最小生成树的 C++ 代码示例:
```c++
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
using namespace std;
using namespace boost;
// 定义自定义边结构
struct Edge {
int from, to, weight;
Edge(int f = 0, int t = 0, int w = 0) : from(f), to(t), weight(w) {}
};
// 定义图的类型
typedef adjacency_list<vecS, vecS, undirectedS, no_property, Edge> Graph;
int main() {
int n = 5; // 顶点数
vector<Edge> edges = {{0, 1, 2}, {0, 2, 4}, {1, 2, 1}, {1, 3, 5}, {2, 3, 3}, {2, 4, 6}, {3, 4, 8}}; // 边集合
// 构建图
Graph g(edges.begin(), edges.end(), n);
// 定义最小生成树的存储变量
vector<Graph::edge_descriptor> tree;
// 计算最小生成树
prim_minimum_spanning_tree(g, back_inserter(tree));
// 输出结果
for (auto e : tree) {
cout << "(" << g[e].from << ", " << g[e].to << ") " << g[e].weight << endl;
}
return 0;
}
```
在这个例子中,我们自定义了一个 `Edge` 结构体,用来表示边的起点、终点和权值,然后使用 `adjacency_list` 定义了图的类型,将 `Edge` 结构体作为边的属性存储在图中。最后使用 `prim_minimum_spanning_tree` 计算最小生成树,将结果存储在 `tree` 变量中,并输出结果。
相关推荐
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)