1

我在想每个子树有两种情况：根在独立集中，根不在集中。如何编写递归算法来查找树中独立集的数量？这棵树是 n 元的。

https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

到目前为止，这是我的解决方案，但它不正确。如果当前子树的父节点已经包含在独立集中，则变量 parentIncluded 等于 true，因此当前子树的根不能添加到独立集中。如果 parentIncluded 等于 false，则可以将当前子树的根添加到独立集中。当 parentIncluded 为 false 时，有两种情况。第一种情况：将根添加到集合中。第二种情况：不添加根。

public static int numberOfIndependentSets(Binary root) {
        if (root == null) {
            return 1;
        }
        return numberOfIndependentSets(root, false) + 1;
    }

    private static int numberOfIndependentSets(Binary current, boolean parentIncluded) {
        if (current.left == null && current.right == null) {
            if (parentIncluded) {
                return 0;
            } else {
                return 1;
            }
        }
        int total = 0;
        if (parentIncluded) {
            int left = numberOfIndependentSets(current.left, false);
            int right = numberOfIndependentSets(current.right, false);
           total += (left + 1) * (right + 1) - 1;
        } else {
            // include current node
            int left = numberOfIndependentSets(current.left, true);
            int right = numberOfIndependentSets(current.right, true);
            total = (left+1) *( right +1);

            // not include current node
            left = numberOfIndependentSets(current.left, false);
            right = numberOfIndependentSets(current.right, false);
            total += (left+1) * (right+1) -1;
        }
        return total;
    }
4

1 回答 1

2

你的基本想法应该有效。

您可以在有根树的集合上定义两个相互递归的函数：

f(T) = number of independent sets containing the root
g(T) = number of independent sets not containing the root

你想计算f(T) + g(T)

对于 1 节点树，L作为基本情况，我们有：

f(L) = 1
g(L) = 1

说这T_1, T_2, .. T_n是根的子树。那么递归方程为：

f(T) = g(T_1)*g(T_2)* ... *g(T_n)
g(T) = (f(T_1)+g(T_1))*(f(T_2)+g(T_2)) * ... * (f(T_n)+g(T_n))

n作为检查：您可以使用它来获取具有级别（等效于 height n-1）的独立完整二叉树集的数量。使f,g成为水平的函数。一个 Python 实现：

def f(n):
    if n == 1:
        return 1
    else:
        return (g(n-1))**2

def g(n):
    if n == 1:
        return 1
    else:
        return (f(n-1) + g(n-1))**2

def h(n): return f(n)+g(n)

[h(n) for n in range(1,7)]评估为

2, 5, 41, 2306, 8143397, 94592167328105

这是在线百科全书中的序列A076725（略有偏移），它被描述为“具有 2^(n-1)-1 个节点的完整二叉树上的独立集合的数量”，所以看起来这种方法是有道理的。

于 2017-01-28T15:30:12.263 回答