1

我有一组看起来像这样的数据：

Person1 是 Person2 的父级

Person2 是 Person3 和 Person4 的父级

Person3 是 Person1 的父级

如果我尝试计算 Person1 的整个树，则会超出最大递归，并且程序将在错误中终止。预期的结果将是 Person1 -> [Person2, Person3, Person4]，所以基本上在必须对已经在列表中的元素重复计算的情况下，这必须被忽略。你有什么想法，我该如何解决这个问题？我的函数看起来像这样：

def compute_children(self):
    children = []
    children.extend(self.child)
    for child in children:
        temp = child.compute_children()
        if 0 < len(temp):
            children.extend(temp)
    return children
4

1 回答 1

1

一个非常简单的解决方案是在您第一次调用时和在您拥有的循环之前创建一个包含您的起始节点的集合compute_children，将所有子节点添加到集合中，忽略任何已经进入集合的子节点。

在图论中，这种方法通常被称为着色，也就是说，您以某种方式存储已经访问过的节点，因此如果存在循环，将来您将不会重新访问相同的节点。

于 2022-02-10T17:09:27.617 回答