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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-02-18 13:01:17

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).

        Doug