python中字典的递归遍历（图遍历）

Question

我有一个具有以下结构的字典：

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

一个键的值实际上是到其他键的链接。通过使用我想要到达其他键直到最后的值。正如您在v4 中看到的那样，某些键没有链接。我认为这类似于图遍历？

---

从v1我想旅行到所有其他价值观开始：

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)

---

我可以使用什么递归函数来遍历字典？

Answer 1

一个简单的解决方案是保留一组“已访问”的已知节点：

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

用作

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

注意：唯一棘手的部分是 Python 中的默认参数是在创建函数对象时而不是在调用函数时计算的，因此使用可变默认值是一个问题，因为更改将在函数返回后仍然有效。