1

我必须在 boost 库中使用 kruskals 算法来找到最小生成树的权重。我想我成功了

#include <iostream>
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include<vector>

using namespace std;
using namespace boost;



int main(){

typedef adjacency_list <vecS,vecS,undirectedS,no_property,property <edge_weight_t,int> > Graph;

typedef graph_traits <Graph>::edge_descriptor Edge;
typedef graph_traits <Graph>::vertex_descriptor Vertex;

int a,b,c,no_vertices,no_edges;

cin>>no_vertices>>no_edges;

Graph g(no_vertices);

property_map <Graph,edge_weight_t>::type weightmap=get(edge_weight,g);
vector <Edge> spanning_tree;

for(int i=0;i<no_edges;i++)
{
    bool success;
    Edge e;
    cin>>a>>b>>c;
    tie(e,success)=add_edge(a,b,g);
    weightmap[e]=c;
}

kruskal_minimum_spanning_tree(g,back_inserter(spanning_tree));

//weight of spanning tree
int ww=0;
graph_traits<Graph>::edge_iterator ei, ei_end;
  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
{
   ww=ww+weightmap[*ei];
}

cout<<"\n"<<ww;


return 0;

}

现在我需要找到顶点 0 和离它最远的那个之间的距离（权重总和）？关于我该怎么做的任何提示？

我正在考虑使用顶点迭代器，但后来我将权重存储在 weightMap 中，那么如果我遍历图形的顶点，我该如何访问它？

编辑：我修改了我的程序，决定使用 kruskal 和 prim

1.kruskal 用于生成树权重 2.prim 算法用于每个顶点到顶点 0 的距离（在生成树中存储在地图距离中）

不幸的是，出了点问题，距离 [*vertex] 是第三个顶点并没有给出答案 2，而是给出了一个

生成树的权重也是 14 而不是 7

我的虚拟输入是：

5 6
0 1 1
0 2 2 
1 2 5
1 3 1
3 2 2
2 4 3

这是我的程序：

#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
using namespace std;

int
main()
{
  using namespace boost;

  typedef adjacency_list < vecS, vecS, undirectedS,
    property<vertex_distance_t, int>, property < edge_weight_t, int > > Graph;

    int num_nodes,num_edges,a,b,c;
    cin>>num_nodes>>num_edges;



  Graph g(num_nodes);

  property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);

  for (int j = 0; j < num_edges ; ++j) {
        cin>>a>>b>>c;
    graph_traits<Graph>::edge_descriptor e;
  bool inserted;
    tie(e, inserted) = add_edge(a, b, g);
    weightmap[e] = c;
  }

    vector < graph_traits < Graph >::vertex_descriptor > p(num_vertices(g));
    cout<<num_vertices(g);


  property_map<Graph, vertex_distance_t>::type distance = get(vertex_distance, g);
  property_map<Graph, vertex_index_t>::type indexmap = get(vertex_index, g);

  prim_minimum_spanning_tree
    (g, *vertices(g).first, &p[0], distance, weightmap, indexmap,
     default_dijkstra_visitor());

  vector <graph_traits<Graph>::edge_descriptor> spanning_tree;

  kruskal_minimum_spanning_tree(g,back_inserter(spanning_tree));
  int ww=0;
  typedef graph_traits < Graph >::edge_descriptor Edge;

  for (vector<Edge>::iterator et= spanning_tree.begin(); et != spanning_tree.end(); ++et)
{
   ww=ww+weightmap[*et];
}

typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first)
{
    cout<<distance[*vp.first];
}






prim_minimum_spanning_tree
    (g, *vertices(g).first, &p[0], distance, weightmap, indexmap,
     default_dijkstra_visitor());

  return EXIT_SUCCESS;
}

谢谢你 ：）

4

1 回答 1

1

我不太确定如何解释 Kruskal MST 算法的结果（特别是边缘列表）。这可能是您正在寻找的：

int ww = 0;
for (auto const& e : spanning_tree) {
    std::cout << "Traversing: " << source(e,g) << " -> " << target(e,g) << ", cost " << weightmap[e] << "\n";
    ww += weightmap[e];
}

cout << "\n" << ww;

否则，您可能希望将前任地图传递给 Kruskal 并阅读您想要的路径。

同时看我上面的素描Live On Coliru

于 2014-10-14T23:07:52.167 回答