kruskal_minimum_spanning_tree.cc

#include <boost/format.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>

namespace
{
  namespace b = boost;

  typedef b::adjacency_list<b::vecS, b::vecS, b::undirectedS, b::no_property,
          b::property<b::edge_weight_t, int>> graph_t;
  typedef b::graph_traits<graph_t>::edge_descriptor edge_descriptor_t;
  typedef std::pair<int, int> edge_t;
}

int main()
{
  enum {A, B, C, D, E, F, G};
  const char names[] = "ABCDEFG";

  std::vector<edge_t> edges = {
    edge_t(A, B),
    edge_t(A, D),
    edge_t(B, C),
    edge_t(B, E),
    edge_t(B, D),
    edge_t(C, E),
    edge_t(D, E),
    edge_t(D, F),
    edge_t(E, F),
    edge_t(E, G),
    edge_t(F, G),
  };
  std::vector<int> weights = {7, 4, 11, 10, 9, 5, 15, 6, 12, 8, 13};

  graph_t g(std::begin(edges), std::end(edges), weights.data(), 7);

  b::property_map<graph_t, b::edge_weight_t>::type weight = b::get(b::edge_weight, g);
  std::vector<edge_descriptor_t> spanning_tree;
  b::kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

  int sum = 0;
  for(const auto& edge : spanning_tree) {
    std::cout << b::format("%s -- %s (W: %s)") % names[source(edge, g)] %
      names[target(edge, g)] % weight[edge] << std::endl;
    sum += weight[edge];
  }
  std::cout << sum << std::endl;

  return 0;
}