graph - 查找具有目标成本的生成树

Question

我对这个很困惑。刚发帖，如果这是一个愚蠢的问题，请原谅我。

假设我们得到一个带有加权边的图 G=(V,E)。我想创建目标成本为 c 的 G 的生成树，其中生成树的成本定义为其所有边成本的总和。我们如何确定是否存在成本为 c 的 G 的生成树？

Answer 1

这是一个尝试。您可以使用动态编程来解决子集和问题，然后对于每个可能的子集，只需检查它是否形成生成树。子集和的一般公式是：让 C[i,S] 是语句的布尔值

S 的一个子集总和为 i

设 e 为任意边。然后复发通常是：

C[i,S' U e] = true 当且仅当 C[i, S'] 或 C[i - weight(e), S']

（您要么使用边 e，要么不使用，并确保使用边 e 不会形成循环）。

如果目标成本是 c，那么您需要为每个 1 <= i <= c 执行 n 次扫描，其中 n 是边数。

最后验证选择的边数比顶点数少 1 并且它们都是连接的。

另一种方法是仅使用回溯递归来搜索所有生成树 <= targetCost。