Как хранить значения из функции рекурсивного графа?

Question

У меня есть следующая рекурсивная функция - функция хорошо работает для распечатки всех путей дерева / графа. Но попытка добавить ROUTES в качестве глобальной переменной и добавить к ней приводит к куче пустых вложенных списков: [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], ... et c

Лучшее решение для использования глобальной переменной и лучшее решение для хранения путей - это то, что я ищу, и это моя функция:

 def printAllPathsUtil(self, u, d, visited, path):
        # Mark the current node as visited and store in path
        visited[u] = True
        path.append(u)
        # If current vertex is same as destination, then print
        # current path[]
        if u == d:
            print(path)
            ROUTES.append(path)
        else:
            # If current vertex is not destination
            # Recur for all the vertices adjacent to this vertex
            for i in self.graph[u]:
                if visited[i] == False:
                    self.printAllPathsUtil(i, d, visited, path)
                    # Remove current vertex from path[] and mark it as unvisited

        path.pop()
        visited[u] = False

Answer 1

Источник вашей проблемы в том, что переменная пути, которую вы добавляете в ROUTES, является ссылкой на тот же объект, который вы используете для управления обходом. Этот же объект добавляется каждый раз, когда вы находите пункт назначения, поэтому, когда процесс завершен (и путь снова пуст), ваш список ROUTE содержит несколько ссылок на (теперь пустой) объект пути.

Ваша поправка ROUTES.append([i for i in path]) создает новый экземпляр переменной пути для сохранения в списке МАРШРУТОВ. Вот почему это работает.

Распространенная ошибка в Python - хранить списки в переменных, предполагая, что вы держите копию, когда на самом деле это только ссылка, а содержимое может быть изменено другими частями программа, которая изменяет оригинал.

Обратите внимание, что вы также можете использовать ROUTES.append(path.copy()) или ROUTES.append(list(path)) или ROUTES.append([*path])