如果附加到列表或添加到列表，则Python会产生不同的递归结果

Question

下面的代码“蛮力”创建了一个城市图，然后通过DFS运行它以找到最短路径。无论是使用“visted.append（node）”还是“visted=visted+[node]”，我得到的结果都是不同的。添加到列表不正确，找不到最短路径

DFS中的打印是为了调试差异的原因，但我无法确定差异是什么。谁能给我解释一下这个细节吗？谢谢

def CreateGraph(cities):
  g={}
  for city in cities:
    g[city]=[]
  return g

def AddRouteToGraph(g,src,dest):
  if src in g and dest in g:
    g[src].append(dest)
  else:
    raise ValueError

cities=['Bmore', 'DC', 'SanFran', 'Philly', 'Seattle', 'NYC']
g=CreateGraph(cities)
AddRouteToGraph(g,'Bmore','Seattle')
AddRouteToGraph(g,'Bmore','Philly')
AddRouteToGraph(g,'Philly','NYC')
AddRouteToGraph(g,'DC','NYC')
AddRouteToGraph(g,'SanFran','Philly')
AddRouteToGraph(g,'SanFran','DC')
AddRouteToGraph(g,'SanFran','Seattle')
AddRouteToGraph(g,'Seattle','DC')
 
def DFS_shortest(g,node,dest,visited,shortest):
  visited.append(node)
  #visited=visited + [node]
  print(f'visited={visited} of type {type(visited)}')
  if node==dest:
    return visited
  for city in g[node]:
    if city not in visited:
      if shortest!=None:
        print(city, str(len(visited)), str(len(shortest)))
      else:
        print(city, str(len(visited)), 'None')
      if shortest==None or len(visited)<len(shortest):
        newPath=DFS_shortest(g,city,dest,visited,shortest)
        if newPath!=None:
          shortest=newPath
  return shortest

print(DFS_shortest(g,'Bmore','NYC',[],None))

Answer 1

通过执行visited = visited + ...，您正在创建列表的一个新实例，该实例独立于上一个递归级别的实例

当您使用visited.append(...)时，您正在修改同一个对象实例，因此，当您向下传递递归时，较低级别的更改实际上会修改较高级别的列表

Answer 2

这是因为当您将visited列表传递给其他方法时，会传递一个引用，因此在这些方法中所做的任何更改（例如追加）都会影响原始的visited列表

但是，当您使用visited = visited + [node]时，将创建一个新列表，并将其传递给其他方法

考虑

def func(l):
    # l.append(1)

    l = l + [1]
    if len(l) < 10:
        func(l)

l = []
func(l)
print(l)

尝试一下，一旦你看到它，你就会明白

• 使用l.append(1)

产出

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

原始列表l已更改

• 使用l = l + [1]

产出

[]

原始列表l没有改变