使用BGL创建生成树

听起来像是你正在生长一棵树,从你指定的顶点开始,通过添加最轻的边来连接你树中的一个顶点到一个不在你树中的顶点。如果是这样的话,您将实现Prim的算法,它确实会给您一个MST。这在Cormen,Leiserson,Rivest&Stein的“算法”的MST章节中有很好的描述。

(我之所以说“听起来像”,是因为“最短边连接到目前为止存在的图”这句话有点模糊。)

这是Prim算法: http://en.wikipedia.org/wiki/Prim%27s_algorithm

你将得到一个最小生成树!

不确定是否会大量使用BGL,但无论如何,在这个想法中,最困难的是找到“最小边”:查看wikipedia页面上的伪代码,看看如何使用二进制堆来完成它。为了更好的复杂性,你需要斐波纳契堆。