用目標成本找到一棵生成樹

Question

我非常難過這個。張貼新內容，如果這是一個愚蠢的問題，請原諒我。

假設我們給出了一個具有加權邊的圖G =（V，E）。我想創建一個目標成本爲c的生成樹G，其中生成樹的成本被定義爲所有邊緣成本的總和。我們如何確定是否存在具有代價c的G的生成樹？

Answer 1

這是刺傷它。您可以使用動態規劃解決子集求和問題，然後針對每個可能的子集檢查它是否構成生成樹。子集和的一般製劑雲：讓C [I，S]是聲明

的布爾值有求和至i

設E是任意的邊緣S的一個子集。然後復發通常去：

C [I，S」 U E] =真當且僅當C [I，S ']或C [I - 重量（e）中，S']

（你要麼使用邊e，要麼不要，並且確保使用邊e不會形成循環）。

如果目標成本是c，那麼您需要對每個掃描執行n次掃描，其中n是邊的數量。

最後驗證拾取的邊的數量是1小於頂點的數量，並且它們都已連接。

另一種方法是使用回溯遞歸來搜索所有生成樹< = targetCost。