DFS 递归期间 python returns 空列表中的嵌套列表

Question

我有一个使用 defaultdict 的图字典，表示 python3 中的图的邻接列表，并想对该图执行 DFS。现在，问题是找到从起始词 beginWord 到 endWord 的所有路由，我正在为该递归 + 回溯应用 DFS。

例如

beginWord = "hit"   
endWord = "cog"   
graph : defaultdict(<class 'list'>, {'hit': ['hot'], 'hot': ['dot', 'lot'], 'dot': ['dog'], 'lot': ['log'], 'dog': ['cog'], 'log': ['cog']})

输出应该是这样的：

[["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]]

我的做法：
我已经制作了图表并创建了两个新列表：path[] 和 ans[].
path 基本上从 beginWord 开始，直到它到达 endWord，当它到达时，我将它附加到 ans 变量（现在它是一个二维嵌套列表），然后从列表中弹出最后一个单词以触发回溯。我将继续这样做，直到探索所有路径并将其存储在 ans[] 列表中。

问题：
ans[] returns 空列表，但它包含两个嵌套的空列表，这表明它知道答案是两个列表，这是正确的，但为什么弹出这些项目？

我的代码：

def DFS(beginWord, endWord, graph, path, ans):

    path.append(beginWord)
    if beginWord == endWord:
        ans.append(path)
        path.pop()
        return

    for i in graph[beginWord]:
        DFS(i, endWord, graph, path, ans)

    path.pop()

注意：对 ans[] 使用 extend 而不是 append 是可行的（不完全正确，但我得到了路径）但为什么不 append 呢？

Answer 1

您有一个列表 path。当您修改此列表时，您会在它出现的任何地方修改它，包括您将它推到 ans.

的地方

相反，您需要像 ans.append(path.copy()) 这样的东西，它在将路径附加到答案之前复制路径。您对 path 所做的任何后续更改都不会影响您已经推送到 ans.

的内容

DFS 递归期间 python returns 空列表中的嵌套列表

Nested list in python returns empty list during DFS recursion

python

recursion

list

depth-first-search

python-3.6