Hello, I have the problem with the vertex structure definition. I don´t know, how to create graph with variable vertices count without vertices renaming. Source graph: (n=5 vertices) Edges { E(130, 27), E(1, 83), E(1, 204), E(27, 1), E(27, 130), E(83, 204), E(204, 130)}; To find minimal spannig tree using Prim leeds to vertices renaming <0,n-1>. Renamed graph: Edges { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 0), E(3, 4), E(4, 0)}. But it is very uncomfortable. How could I use original vertices number in graph definition? Thanks Tomas My source code: #include <boost/config.hpp> #include <boost/utility.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/prim_minimum_spanning_tree.hpp> #include <boost/graph/subgraph.hpp> typedef boost::adjacency_list_traits< boost::vecS, boost::vecS, boost::undirectedS >::vertex_descriptor vertex_descriptor; typedef boost::property<boost::vertex_color_t, boost::default_color_type, boost::property< boost::vertex_predecessor_t, vertex_descriptor > > VertexProperty; typedef boost::property<boost::edge_color_t, boost::default_color_type, boost::property<boost::edge_weight_t, int, boost::property<boost::edge_index_t, int > > > EdgeProperty; typedef boost::subgraph< boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty > > Graph; typedef boost::graph_traits < Graph >::edge_descriptor Edge; int main(void) { int num=5; Graph g(num); boost::property_map<Graph, boost::edge_weight_t>::type weightmap = boost::get(boost::edge_weight, g); Edge e; bool inserted; //Here I would like to use original vertices numbers boost::tie(e, inserted) = boost::add_edge(0, 2, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(1, 3, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(1, 4, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(2, 1, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(2, 0, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(3, 4, g); weightmap[e] = 1; boost::tie(e, inserted) = boost::add_edge(4, 0, g); weightmap[e] = 1; std::vector < boost::graph_traits < Graph >::vertex_descriptor > p(num_vertices(g)); boost::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; }