Hi!
Hello, I wondered are there way to count connected components in the minimum spanning tree? Currently I just making copy of graph to be able to count and collect connected components are there more efficient way to do that?
If you just want to know the number of connected components define your own predecessor_map for kruskal_minimum_spanning_tree. Then you can count the vertices with themselves as predecessor. These vertices are the roots of the spearate trees: std::vector < Edge > spanning_tree; Graph graphMST; std::vector < Graph::vertex_descriptor > pred(num_vertices(graphMST)); // Use the vertex index map just in case of vertices are not numbered 0...n-1 property_map< Graph, vertex_index_t>::type vi_map = get(vertex_index_t(), graphMST); kruskal_minimum_spanning_tree(graphFOREST, std::back_inserter(spanning_tree), predecessor_map(make_iterator_property_map(pred.begin(), vi_map)) ); int num_components = 0; Graph::vertex_iterator vi, vi_end; for(tie(vi, vi_end) = vertices(graphMST); vi != vi_end; ++vi) if(*vi == pred[get(vi_map, *vi)]) num_components++; Cheers, Gabe