Search It Again, Sam

[cloud0293644413]

When running the code below for Search It Again, Sam different paths will be returned each time it is run.

I’ve no idea why it does this, is there anyway to solve this?

def dfs(graph, current_vertex, target_value, visited=None):
  if visited is None:
    visited = []
	
  visited.append(current_vertex)
  
  if current_vertex == target_value:
    return visited
	
  # Add your recursive case here:
  for neighbor in graph[current_vertex]:
    if neighbor not in visited:
      path = dfs(graph, neighbor, target_value, visited)
      if path is not None:
        return path


      

the_most_dangerous_graph = {
    'lava': set(['sharks', 'piranhas']),
    'sharks': set(['lava', 'bees', 'lasers']),
    'piranhas': set(['lava', 'crocodiles']),
    'bees': set(['sharks']),
    'lasers': set(['sharks', 'crocodiles']),
    'crocodiles': set(['piranhas', 'lasers'])
  }

# Call dfs() below and print the result:
print(dfs(the_most_dangerous_graph, "crocodiles", "bees"))

[midlindner]

How very observant of you!

That behavior is to be expected with the graph provided. The reason is the use of the set() constructor. When the provided lists are converted to sets the order of the elements is not guaranteed. Try adding a print statement to observe this behavior.

@cloud0293644413

def dfs(graph, current_vertex, target_value, visited=None):
  print(current_vertex, graph[current_vertex]) #try this
  if visited is None:
    visited = []
...

Run the code multiple times, and notice the order of the elements in each set.

Not sure why the lesson author felt the set() constructor was necessary or particularly useful. To get consistent results, you could change set() to sorted().