Search code examples
c++visual-c++treegraph-theoryminimum-spanning-tree

tree partitioning

I have a 2d symmteric matrix "myMSTdata[][]" that represents weighted edge minimum spanning tree MST (zero if there is no direct edge) and I need to cut that MST on the edge with maximum weight such that I have two subtree partitions (part1,part2). Is there any easy or cheap way to do so? or is there any library that I can use for doing so?

Solution

  • Have a look at the boost::graph library: http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/prim_minimum_spanning_tree.html