加法和 += 给出列表的不同结果（深度优先搜索）

Question

我一直在努力理解深度优先搜索，并使用各种在线资源获得了以下代码：

graph = {'A': ['B', 'D'], 'B': ['E'], 'C': [], 'D': ['C', 'E'], 
         'E': ['H', 'I', 'J'], 'F': [], 'G': [], 'H': ['F'], 
         'I': [], 'J': ['G']}

def dfs(graph, start, end, path=None):
    if path == None:
        path = []
    path = path + [start]
    paths = []
    if start == end:
        return [path]
    for neighbour in graph[start]:
        if neighbour not in path:
            paths.extend(dfs(graph, neighbour, end, path))
    return paths

print(dfs(graph, 'A', 'G'))

这将输出所需的结果：

[['A', 'B', 'E', 'J', 'G'], ['A', 'D', 'E', 'J', 'G']]

但是当我用 path += [start]（或 path.extend([start]) 替换行 path = path + [start] 时，据我所知做同样的事情）我得到以下输出：[['A', 'B', 'E', 'H', 'F', 'I', 'J', 'G', 'D', 'C']]

我知道这与操作上的差异有关，但我真的不明白它在这里如何应用。请有人解释一下吗？

Answer 1

这个

path = path + [start]

与

略有不同

path += [start]  # or path.extend([start])

for lists（和其他可变类型），因为它重新创建了 path 的新引用（隐式地是你想要的，你不想写入以前的参考）

path += [start]  # or path.extend([start])

重复使用相同的引用，因为您在循环中多次传递 path（没有制作副本）：

for neighbour in graph[start]:
    if neighbour not in path:
       paths.extend(dfs(graph, neighbour, end, path))

因此，如果其他某个对象将其存储在存储中，您将更改两个列表：行为不同，而不是您想要的行为。

当然你可以这样做paths.extend(dfs(graph, neighbour, end, path.copy()))但是这将违背对调用者最小化的原则（不希望修改最后一个参数）

我的建议：

如果您想要性能并且不关心是否重用引用，请始终对列表使用 +=，因为它只是扩展了列表。 + 运算符创建一个新的列表和副本，这真的很慢。
将 path = path + something 与 list 类型一起使用时，请始终为未来的维护者（包括您自己！）添加注释 不要优化 +=.

也许一些更明确和等效的代码：

path = path.copy() # or path[:], or list(path)...: force creation of a new reference to break dependency with passed parameter
path += [start]

另请注意：它不适用于 str 或 tuple 类型，因为即使 += 也会创建一个新引用，因为字符串 不变性。没有与字符串共享引用的风险，所以在这里使用 tuple 而不是 list 也会修复它：

if path == None:
    path = tuple()
path += (start,)  # += creates a new path reference, cos path is a tuple, immutable

（但不要指望 += 的性能更高，在这种情况下，会制作副本）

加法和 += 给出列表的不同结果（深度优先搜索）

Addition and += give different results for list (depth first search)

python

list

depth-first-search