使用BGL創建生成樹

Question

我有一個BGL圖並且想要使用BGL創建生成樹。

從指定頂點開始，我想將最短邊添加到與此頂點相連的圖形中。從那裏開始，我總是選擇與迄今爲止存在的圖形相連的最短邊。

因此，我想添加約束條件，即每個新邊緣必須已連接到圖形，而與生成樹標準保持不存在循環。

手工操作不會很困難;但由於我想了解一些關於BGL的知識，我想知道哪種算法最適合我的問題。

Answer 1

這聽起來像你正在生長的樹，從您指定的頂點，通過添加在你的樹的頂點，這不是在你的樹連接頂點最輕的邊緣。如果是這樣，你正在實施Prim的算法，它給你一個MST。它在Cornet，Leiserson，Rivest & Stein的「Algorithms」的MST章節中有很好的描述。

（我說「聽起來像」，因爲聲明「與迄今存在的圖形連接的最短邊緣」有點含糊）。

Answer 2

這是普里姆算法：http://en.wikipedia.org/wiki/Prim%27s_algorithm

你會得到一個最小生成樹！

不知道你是否會依賴BGL來做這件事，但無論如何，這個想法的難點在於找到「最小邊緣」：查看維基百科頁面上的僞代碼，看看它是如何完成的使用二進制堆。爲了更好的複雜性，你需要Fibonacci堆。