boost Graph 动态生成最小生成树详细示例
时间: 2023-07-22 18:40:32 浏览: 51
下面是一个使用 Boost Graph Library 的示例程序,生成一个随机图并计算最小生成树:
```cpp
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
using namespace boost;
int main()
{
typedef adjacency_list<vecS, vecS, undirectedS,
no_property, property<edge_weight_t, int>> Graph;
Graph G;
// 生成一个随机图
generate_random_graph(G, 10, 15, mt19937(42));
// 生成一个随机权重
property_map<Graph, edge_weight_t>::type weight_map = get(edge_weight, G);
graph_traits<Graph>::edge_iterator ei, ei_end;
for (tie(ei, ei_end) = edges(G); ei != ei_end; ++ei)
weight_map[*ei] = rand() % 100;
// 计算最小生成树
std::vector<graph_traits<Graph>::edge_descriptor> tree;
prim_minimum_spanning_tree(G, std::back_inserter(tree));
// 输出最小生成树的边和权重
std::cout << "Minimum Spanning Tree:" << std::endl;
for (auto e : tree)
std::cout << source(e, G) << " -- " << target(e, G)
<< " with weight of " << weight_map[e] << std::endl;
return 0;
}
```
这个程序使用 `adjacency_list` 表示图,其中每个节点存储在一个 `vector` 中,边没有任何属性,但有一个 `edge_weight_t` 属性表示权重。我们使用 `generate_random_graph` 函数生成一个随机图,然后为每条边分配一个随机权重。最后,我们使用 `prim_minimum_spanning_tree` 函数计算最小生成树,并将结果输出到控制台。