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

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 = path + [start]用path += [start](或者path.extend([start]),我理解同样的事情)替换该行时,我得到以下输出:[['A', 'B', 'E', 'H', 'F', 'I', 'J', 'G', 'D', 'C']]

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

Answer 1

这个

path = path + [start]

与...略有不同

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

对于列表(和其他可变类型),因为它重新创建了一个新的引用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

(但+=在这种情况下不要期望更高的性能,复制品)