#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>

int
main()
{
    using namespace boost;
    typedef adjacency_list < vecS, vecS, undirectedS,
    property<vertex_distance_t, int>, property < edge_weight_t, int > > Graph;
    typedef std::pair < int, int >E;
    const int num_nodes = 5;
    E edges[] = {
        E(0,1), E(0,2), E(0,3), E(0,4), E(0,5), E(0,6), E(0,7), E(1,2), E(1,3), E(1,4), E(1,5), E(1,6), E(1,7), E(2,3), E(2,4), E(2,5), E(2,6), E(2,7), E(3,4), E(3,5), E(3,6), E(3,7), E(4,5), E(4,6), E(4,7), E(5,6), E(5,7), E(6,7)
    };
    int weights[] = {403, 406, 411, 511, 507, 508, 505, 407, 403, 511, 516, 517, 509, 413, 511, 507, 515, 511, 507, 508, 509, 506, 412, 408, 410, 408, 413, 409
    };

    Graph g(edges, edges + sizeof(edges) / sizeof(E), weights, num_nodes);

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

    prim_minimum_spanning_tree(g, &p[0]);
    
    for (std::size_t i = 0; i != p.size(); ++i)
        if (p[i] != i)
            std::cout << "parent[" << i << "] = " << p[i] << std::endl;
        else
            std::cout << "parent[" << i << "] = no parent" << std::endl;
    
    return EXIT_SUCCESS;
}