嵌套函数未修改外部变量？图路径查找函数返回空数组求助

原问题代码 #

def findAllPaths(vertices, Alist, source, dest):
    result = []
    path = []
    visited = []

    def find_path(Alist, source, dest, path, visited):
        path.append(source)
        visited.append(source)

        if source == dest:
            result.append(path)
        else:
            for i in Alist[source]:
                if i not in visited:
                    find_path(Alist, i, dest, path, visited)
        visited.pop()
        path.pop()
    find_path(Alist, source, dest, [] ,[])

    return result


INPUT:
    vertices = [1, 2, 3, 4, 5, 6, 7, 8]
    AList = {1: [3, 4], 2: [3], 3: [6], 4: [6, 7], 5: [4, 6], 6: [2], 7: [5]}
    source = 1
    destination = 2
OUTPUT:
    [[], [], []]

这段代码意图查找图中从源节点到目标节点的所有路径，但最终返回[[], [], []]。嵌套函数能找到路径，却无法正确保存到外部的result列表中。

问题原因 #

核心问题是添加路径到result时传递的是列表引用而非副本。当找到目标节点时，result.append(path)把path这个列表对象的引用存入了result，但后续代码执行path.pop()会修改同一个列表对象。等到递归结束，所有被存入result的引用都指向了被清空后的path，所以最终返回全空的列表。

另外，外层定义的path和visited变量未被使用，属于冗余代码，但不影响核心逻辑。

解决方法 #

当找到目标节点时，添加path的副本到result，而非直接添加path本身。可以用list(path)或path.copy()创建副本，这样后续对path的修改不会影响已经存入result的路径。

修改后的代码如下：

def findAllPaths(vertices, Alist, source, dest):
    result = []

    def find_path(Alist, source, dest, path, visited):
        path.append(source)
        visited.append(source)

        if source == dest:
            # 添加路径副本，避免后续修改影响已保存的路径
            result.append(list(path))
        else:
            for i in Alist[source]:
                if i not in visited:
                    find_path(Alist, i, dest, path, visited)
        visited.pop()
        path.pop()
    
    find_path(Alist, source, dest, [], [])
    return result


# 测试代码
vertices = [1, 2, 3, 4, 5, 6, 7, 8]
AList = {1: [3, 4], 2: [3], 3: [6], 4: [6, 7], 5: [4, 6], 6: [2], 7: [5]}
source = 1
destination = 2
print(findAllPaths(vertices, AList, source, destination))

修改后运行输出为：

[[1, 3, 6, 2], [1, 4, 6, 2], [1, 4, 7, 5, 6, 2]]

完全符合预期。

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