Creating a spanning tree using BGL

Question

I have a BGL graph and want to create a spanning tree using BGL.

Starting from a specified vertex, I want to add the shortest edge to my graph which connects with this vertex. From there on, I want to always pick the shortest edge which connects with the graph which exists thus far.

So, I want to add the constraint that every new edge has to be connected to the graph already while staying with the spanning tree criterion that there are no cycles.

It wouldn't be very hard to do this by hand; but since I want to learn something about BGL, I would like to know which algorithm suits my problem best.

Answer 1

That's Prim algorithm : http://en.wikipedia.org/wiki/Prim%27s_algorithm

You'll get a minimum spanning tree !

Not sure if you'll lean of lot a BGL with it but anyway what's difficult in this idea is to find the "minimum edge" : look at the pseudo-code on the wikipedia page to see how it can be done using a binary heap. For better complexity you'll need Fibonacci heap.

Answer 2

It sounds like you are growing a tree, starting with your specified vertex, by adding the lightest edge that connects a vertex in your tree to a vertex that's not in your tree. If that's the case, you are implementing Prim's algorithm, which does give you an MST. It's nicely described in the MST chapter of "Algorithms" by Cormen, Leiserson, Rivest & Stein.

(I say "sounds like" because the statement "shortest edge which connects with the graph which exists thus far" is a big vague.)