2

我正在使用最小跨越树（MST），我是使用 boost 的新手。我的问题是我想使用一个权重向量生成一个 MST，然后使用另一个向量重建树。也许我可以用代码更好地解释：

using namespace boost;
typedef adjacency_list < vecS, vecS, undirectedS, property<vertex_distance_t, int>, property < edge_weight_t, int > > Graph;
typedef graph_traits < Graph >::edge_descriptor Edge;
typedef graph_traits < Graph >::vertex_descriptor Vertex;
typedef std::pair<int, int> E;

const int num_nodes = 5;
E edges[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3),
E(3, 4), E(4, 0) };
int weights[] = { 1, 1, 2, 7, 3, 1, 1 };
int weights2[] = { -1, 1, -2, 7, 3, -1, -1 };
Graph g(edges, edges + sizeof(edges) / sizeof(E), weights, num_nodes);
property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);

std::vector < graph_traits < Graph >::vertex_descriptor > parentMap(num_vertices(g));
property_map<Graph, vertex_distance_t>::type distancemap = get(vertex_distance, g);
property_map<Graph, vertex_index_t>::type indexmap;
prim_minimum_spanning_tree (g, *vertices(g).first, &parentMap[0], distancemap, weightmap, indexmap,  default_dijkstra_visitor());

for (std::size_t i = 0; i != parentMap.size(); ++i)
  if (parentMap[i] != i)
    std::cout << "parent[" << i << "] = " << parentMap[i] << std::endl;
  else
    std::cout << "parent[" << i << "] = no parent" << std::endl;

std::cout<<"Weights"<<std::endl;
for (std::size_t i = 0; i != parentMap.size(); ++i)
  std::cout<<"weight["<<i<<"]:  "<<  distancemap(i) <<std::endl;

return EXIT_SUCCESS;

在上面的代码中，我可以生成 MST，并使用 parentMap 和 distanceMap 我可以获得树的每条边的权重。

但是考虑到我想使用向量权重来生成 MST，并使用weights2来获取顶点之间的边值，我该怎么做呢？

4

0 回答 0