Recursive traversal of a dictionary in python (graph traversal)

Question

I have a dictionary with the following structure:

 KEY    VALUES
 v1 = {v2, v3}
 v2 = {v1}
 v3 = {v1, v5}
 v4 = {v10}
 v5 = {v3, v6}

The values of a key are actually links to other keys. By using the values I want to reach the other keys till the end. Some keys are not linked as you can see for v4. I think this is similar to graph traversal?

---

starting from v1 I want to travel to all the other values:

v1 --> v2 --> v1
   --> v3 --> v1
          --> v5 --> v3
                 --> v6      
v4 --> v10 

---

def travel():
  travel_dict = defaultdict(list)
  travel_dict[v1].append(v2)
  travel_dict[v1].append(v3)
  travel_dict[v2].append(v1)
  travel_dict[v3].append(v1)
  travel_dict[v3].append(v5)
  travel_dict[v5].append(v3)
  travel_dict[v5].append(v6)
  travel_dict[v6].append(v5)
  travel_dict[v4].append(v10)

---

What Recursive function can I use to travel the dictionary?

Answer 1

A simple solution is to keep a "visited" set of already known nodes:

def reach(travel_dict, x, visited=None):
    if visited is None:
        visited = set() # see note
    visited.add(x)
    for y in travel_dict.get(x, []):
        if y not in visited:
            yield y
            for z in reach(travel_dict, y, visited):
                yield z

used as

for y in reach(travel_dict, x):
    print("you can go to", y)

NOTE: The only tricky part is that default arguments in Python are evaluated when creating the function object and not when the function is called, therefore using mutable defaults is a problem because changes will remain in effect after the function returns.