这是一个作业问题，所以我很高兴能得到一些提示。
我有一个图G，其中每个顶点v都有一个权重w(v)。
S(G)是图中所有顶点的权重之和。
我需要找到一种算法，确定是否存在一个顶点组A，当G[A]（由A诱导的G的图）是一棵树时，执行S(G[A]) = S(G[V\A])。
我知道应该遍历所有顶点，求出它们的权重之和，然后尝试找到一个达到该和一半的树，但我不确定具体是怎么做的。我相当确定它涉及到动态规划。
非常感谢，
Yaron。
诱导图中顶点之和 - 动态规划
3
- user76508
2
所需的复杂度是多少？ - Herokiller
@Herokiller 没有一个确定的答案。虽然，我认为这是动态规划问题，所以我在思考一下复杂度可能是O(N^2)或类似的。 - user76508
1个回答
0
这不是一个动态规划问题，而是一个搜索问题，关键在于要找到一棵树。
如果你想一想，就会知道一两个算法可以告诉你最小生成树。同样的逻辑，你也可以构建一棵最大生成树。例如，如果你找到了最大生成树，而且它的权重之和小于50%（或目标值），那么你就知道这个问题是不可能解决的。
因此，按照这个逻辑，你可以继续像构建生成树一样进行，并拒绝任何超过目标数量的路径。这种策略称为“分支界限”。让我们来想象一下如何用Kruskal算法实现这个过程：
（1）你将有一组树；从每个顶点开始将其作为单独的“树”
（2）维护一个你还没有使用的边的队列，从小到大排序
（3）维护一个你已经使用的边的堆栈
（4）查找连接两个不同树的边，并且两个树的权重之和小于（或等于目标值，即找到一个解决方案）
（4a）如果不存在这样的边，则从堆栈中弹出一个值（删除边并分离树），并尝试队列中的下一个值
（4b）如果存在这样的边，则添加该边（合并两个树），将其推入堆栈并返回步骤4
显然，有不同的方法来执行相同的过程。例如，您也可以使用Prim算法的变体。
- Tyler Durden
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接