查找树中最大独立集的算法
我需要一种算法来查找树中的最大独立集。我想从所有叶节点开始，然后将直接父节点删除到这些叶节点，然后选择我们删除的父节点的父节点，递归地重复此过程，直到到达根目录为止。这是在O（n）时间内完成的吗？任何答复表示赞赏。谢谢。
谁能给我指出一种算法，以找到树中的最大支配集。
回答：
回答：
您可以通过在树中进行深度优先搜索来计算最大独立集。
搜索将为图中的每个子树计算两个值：
- A（i）=根于i的子树中最大独立集的大小，约束条件是必须将节点i包含在集合中。
- B（i）=根于i的子树中最大独立集的大小，并且限制节点i不得包含在集合中。
可以通过考虑以下两种情况来递归计算这些：
- 不包括子树的根。
B（i）= sum（max（A（j），B（j））for children（i）中的j）
- 包含子树的根。
A（i）= 1 + sum（B（j）对于孩子中的j（i））
整个树中最大独立集的大小为max（A（root），B（root））。
回答：
根据Wikipedia中的支配集定义，最大支配集总是微不足道地等于包括图中的每个节点-
但这可能不是您的意思吗？
以上是 查找树中最大独立集的算法 的全部内容， 来源链接： utcz.com/qa/413475.html
