我需要一个算法来查找树中的最大独立集。我想从所有叶节点开始，然后删除直接父节点到这些叶节点，然后选择我们删除的父节点的父节点，递归地重复这个过程，直到我们到达root。这是在O（n）时间内完成的吗？任何回复表示赞赏。谢谢。
并且有人可以请指出一个算法来找到树中的最大支配集。
我需要一个算法来查找树中的最大独立集。我想从所有叶节点开始，然后删除直接父节点到这些叶节点，然后选择我们删除的父节点的父节点，递归地重复这个过程，直到我们到达root。这是在O（n）时间内完成的吗？任何回复表示赞赏。谢谢。
并且有人可以请指出一个算法来找到树中的最大支配集。
您可以通过树中的深度优先搜索来计算最大独立集。
搜索将为图中的每个子树计算两个值：
这些可以通过考虑两种情况递归计算：
子树的根不包括在内。
B（i）=儿童j的总和（max（A（j），B（j））（i））
包含子树的根。
A（i）= 1 +总和（儿童（i）中j的B（j））
整棵树中最大独立集的大小为max（A（root），B（root））。
根据 维基百科中支配集的定义 最大支配集总是平凡地等于包括图中的每个节点 - 但这可能不是你的意思？
为了找到最大的独立顶点集，我们可以使用树的一个重要属性：每个树都是二分的，即我们可以仅使用两种颜色对树的顶点着色，使得没有两个相邻的顶点具有相同的颜色。
执行DFS遍历并使用BLACK和WHITE开始着色顶点。
选择更多数量的顶点集（BLACK或WHITE）。这将为您提供树的最大独立顶点集。
这个算法工作原理背后的一些直觉：
让我们首先重新审视最大独立顶点集的定义。我们必须只选择边缘的一个端点，我们必须覆盖满足此属性的树的每个边缘。我们不允许选择边缘的两个端点。
现在，图的双重组合有什么作用？它简单地将顶点集划分为两个子集（WHITE和BLACK），WHITE彩色顶点直接连接到BLACK。因此，如果我们选择所有WHITE或所有BLACK，我们固有地选择一组独立的顶点。从而选择最大独立 设置，去寻找尺寸较大的子集。