Boost kruskals algorithm find sum of edges between vertex 0 and the one farthest from it?

Question

I have to use kruskals algorithm in the boost library to find the weight of the minimum spanning tree. I think I managed that one

#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;

}

Now I need to find the distance(sum of weights) between vertex 0 and the one farthest from it? Any hints as to how I could do it?

I was thinking of using vertex iterator, but then I store the weight in weightMap so how do I access it if I iterate through the vertices of my graph?

EDIT: I have modified my program,decided to use kruskal and prim

1.kruskal for the spanning tree weight 2.prim algorithm for the distance of each vertex from the vertex 0(in spanning tree stored in map distance)

Unfortunately something goes wrong, distance[*vertex] which is the third vertex doesnt give the answer 2,but gives one

Also the weight of spanning tree is 14 instead of 7

my dummy input is:

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

here my programs:

#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;
}

THank you :)

Answer 1

I'm not really sure how to interpret the result of the Kruskal MST algorithm (in particular the edge list). Could this be what you were looking for:

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;

Otherwise, you'd probably want to pass a predecessor map to Kruskal and read that for your desired path.

Meanwhile see my above sketch Live On Coliru