Python - Different recursive result if append to list or add to the list

Question

The code below brute force creates a graph of cities and then runs it through a DFS to find the shortest path. The result I get is different whether I use 'visited.append(node)' or 'visited=visited + [node]'. Appending to the list is incorrect does not find the shortest path.

The print within the DFS is to debug why there is a difference, but I cannot determine what the difference is. Can anyone explain this detail to me? Thanks!

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))

Alain T. · Accepted Answer · 2020-10-17 14:36:07Z

3

By doing visited = visited + ... you are creating a new instance of the list which is independent from the one at the previous level of recursion.

When you use visited.append(...) you are modifying the same object instance so, when you pass it down the recursion, the alterations at the lower levels actually modify your list at the higher level

answered Oct 17, 2020 at 14:36

Alain T.

42.2k4 gold badges36 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

CaptainDaVinci · Accepted Answer · 2020-10-17 14:37:56Z

1

This is because when you pass the visited list to the other methods a reference is passed, so any changes (e.g append) made in those methods will affect the original visited list.

However, when you use visited = visited + [node] a new list is created and that is passed to the other methods.

E.g consider

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

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

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

Try it out, you'll understand it once you see it.

Using l.append(1)

Output,

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

The original list l has changed.

Using l = l + [1]

Output,

[]

The original list l hasn't changed.

answered Oct 17, 2020 at 14:37

CaptainDaVinci

1,0659 silver badges28 bronze badges

1 Comment

chrispy Over a year ago

Alain and CaptainDaVinci - thank you for your quick and complete responses. Very helpful!

Collectives™ on Stack Overflow

Python - Different recursive result if append to list or add to the list

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related