Рекурсивная функция для вычисления дочерних элементов родителя

У меня есть набор данных, которые выглядят следующим образом:

Персона1 является родителем Персоны2

Персона2 является родителем Персоны3 и Персоны4

Персона3 является родителем Персоны1

Если я попытаюсь вычислить все дерево для 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

Очень простым решением было бы создать коллекцию, содержащую ваш начальный узел, когда вы вызываете compute_children в первый раз и перед циклом, который у вас есть, добавить все дочерние узлы в коллекцию, игнорируя любой дочерний узел, который уже попал в коллекцию.

В теории графов такой подход обычно называют раскраской, то есть вы запоминаете, какие узлы уже были посещены, чтобы в будущем не возвращаться к тем же узлам при наличии цикла.

Вернуться на верх