Re: [Boost-users] Creating a mst graph from another, undirected one

From: aitor (aitors2005_at_[hidden])
Date: 2005-02-21 05:49:08

Fri, Feb 18, 2005 egunean, Doug Gregor-k zera esan zuen :
> On Feb 18, 2005, at 9:56 AM, aitor wrote:
> [snip]
> >(0,1),(3,2),(0,2)
> >
> >but if i build the mst the way you indicate, it gives me this graph:
> >
> >              0:a    3:d
> >            /    \   /
> >          1:b     2:c
> >
> >which is not a tree, instead of:
> >
> >              0:a
> >            /    \
> >          1:b     2:c
> >                   |
> >                  3:d
> >
> >that is what i want. Note that the problem is the edge (3,2) in the
> >mst_vertices vector; it should be (2,3) in the directed graph. Any
> >ideas ?
> 
> If you use Prim's algorithm instead of Kruskal's algorithms, you 
> actually get the tree built within a property map (the property map 
> will go from vertices to their predecessors in the tree, leading back 
> to the source).

Yes, that made the trick. Thank you !

                                        aitor