Cheers, that works perfectly. Yeah it’s just a consequence of the search you’re using, there’s a chance you’ll take paths that don’t actually go towards your goal. The bit that might be unexpected is the way the sets work, they’re hashed much like dictionaries (hence the constant time membership tests) but they’re not ordered, not even insertion ordered like the newer Python dicts are. This is what’s giving you different results, the order in which the neighbouring vertices are being traversed.
Technically there’s an underlying order from the hash itself but Python’s interpreter actually seeds the hash (at least for strings, not sure about everything else) with a random number each time you run the interpreter so the “order” of the set appears to change.
If you ran the code on the cc interpreter several times I think you’d get a different order each time. The Jupyter session on the other hand is a single python session so the seed would be exactly the same and the order would never change (until you restarted the kernel).
Edit: You can even test your code in the snippet below. Each time you run it you’ll probably get a different result (might need to run a few times to actually see the effect since there are only so many possibilities)-
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:
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:
search = dfs(the_most_dangerous_graph, "crocodiles", "bees")
print(search)
If you were to change the dangerous_graph to something ordered like lists or tuples, e.g.
the_most_dangerous_graph = {
'lava': ['sharks', 'piranhas'],
'sharks': ['lava', 'bees', 'lasers'],
'piranhas': ['lava', 'crocodiles'],
'bees': ['sharks'],
'lasers': ['sharks', 'crocodiles'],
'crocodiles': ['piranhas', 'lasers'],
}
then you should get the same result each time.
