如何解决递归DFS存储图中全路径返回空列表的问题

核心问题是列表引用传递导致的回溯污染：

• 递归过程中，path始终是同一个列表对象，每次向all_paths追加的都是该对象的引用
• 当递归回溯（比如找到目标节点后弹出最后一个元素）时，原path列表的内容会被修改
• 最终all_paths里的所有元素都指向同一个被清空的列表，因此输出全是空数组

向all_paths添加路径时，必须添加path的副本，而非原列表的引用。常用的副本创建方式有两种：

• 使用列表内置的copy()方法：all_paths.append(path.copy())
• 用list()构造器生成新列表：all_paths.append(list(path))

错误写法（导致空列表） #

def printAllPathsUtil(self, u, d, visited, path, all_paths):
    visited[u] = True
    path.append(u)
    if u == d:
        print(path)
        all_paths.append(path)  # 追加的是原列表引用，会被回溯操作修改
    else:
        for i in self.graph[u]:
            if not visited[i]:
                self.printAllPathsUtil(i, d, visited, path, all_paths)
    path.pop()
    visited[u] = False

正确写法（添加副本避免污染） #

def printAllPathsUtil(self, u, d, visited, path, all_paths):
    visited[u] = True
    path.append(u)
    if u == d:
        print(path)
        all_paths.append(path.copy())  # 追加副本，与原列表解耦
    else:
        for i in self.graph[u]:
            if not visited[i]:
                self.printAllPathsUtil(i, d, visited, path, all_paths)
    path.pop()
    visited[u] = False

完整可运行代码 #

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[] for _ in range(vertices)]
    
    def addEdge(self, u, v):
        self.graph[u].append(v)
    
    def printAllPathsUtil(self, u, d, visited, path, all_paths):
        visited[u] = True
        path.append(u)
        if u == d:
            print(path)
            all_paths.append(path.copy())
        else:
            for i in self.graph[u]:
                if not visited[i]:
                    self.printAllPathsUtil(i, d, visited, path, all_paths)
        path.pop()
        visited[u] = False
    
    def getAllPaths(self, s, d):
        visited = [False] * self.V
        path = []
        all_paths = []
        self.printAllPathsUtil(s, d, visited, path, all_paths)
        return all_paths

# 构建目标图
g = Graph(4)
g.addEdge(0, 1) 
g.addEdge(0, 2) 
g.addEdge(0, 3) 
g.addEdge(2, 0) 
g.addEdge(2, 1) 
g.addEdge(1, 3)

# 获取并打印所有路径
paths = g.getAllPaths(2, 3)
print("最终返回的路径列表：")
print(paths)

运行后输出：

[2, 0, 1, 3]
[2, 0, 3]
[2, 1, 3]
最终返回的路径列表：
[[2, 0, 1, 3], [2, 0, 3], [2, 1, 3]]

内容的提问来源于stack exchange，提问作者Stacker