boost 自定义顶点和自定义边的最小生成树 c++ 代码
时间: 2023-11-08 07:05:46 浏览: 39
以下是使用 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 Vertex {
int id;
Vertex(int i = 0) : id(i) {}
};
// 定义自定义边结构
struct Edge {
int weight;
Edge(int w = 0) : weight(w) {}
};
// 定义图的类型
typedef adjacency_list<vecS, vecS, undirectedS, Vertex, Edge> Graph;
int main() {
int n = 5; // 顶点数
vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}}; // 边集合
vector<Vertex> vertices(n); // 顶点集合
// 初始化顶点
for (int i = 0; i < n; i++) {
vertices[i] = Vertex(i);
}
// 构建图
Graph g(edges.begin(), edges.end(), vertices.begin(), n);
// 定义最小生成树的存储变量
vector<Graph::edge_descriptor> tree;
// 计算最小生成树
prim_minimum_spanning_tree(g, back_inserter(tree));
// 输出结果
for (auto e : tree) {
cout << "(" << g[source(e, g)].id << ", " << g[target(e, g)].id << ") " << g[e].weight << endl;
}
return 0;
}
```
在这个例子中,我们自定义了一个 `Vertex` 结构体,用来表示顶点的标识符,然后使用 `adjacency_list` 定义了图的类型,将 `Vertex` 结构体作为顶点的属性存储在图中。同时,我们也自定义了一个 `Edge` 结构体,用来表示边的权值,将 `Edge` 结构体作为边的属性存储在图中。最后使用 `prim_minimum_spanning_tree` 计算最小生成树,将结果存储在 `tree` 变量中,并输出结果。
相关推荐
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)