如何存储递归图函数中的值？

Question

我有以下递归函数-该函数可以很好地打印出树/图的所有路径。但是尝试将ROUTES添加为全局变量并附加到它会导致一组空嵌套列表： [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [],…等等

我正在寻找使用全局变量和存储路径的更好解决方案，这是我的功能：

 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的path变量是对用于控制遍历的同一对象的引用。每次找到目的地时都会添加相同的对象，因此，当流程结束（路径再次为空）时，路由列表包含对（现在为空）路径对象的多个引用

您的更正ROUTES.append([i for i in path])创建一个path变量的新实例以存储在ROUTES列表中。这就是它起作用的原因

Python中的一个常见错误是将列表存储在变量中，假设您持有一个副本，而实际上它只是一个引用，并且内容可能会被程序中更改原始内容的其他部分修改

注意，您也可以使用ROUTES.append(path.copy())或ROUTES.append(list(path))或ROUTES.append([*path])