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

---

我可以使用哪个递归函数来遍历字典？

- Hani Goc

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 中的默认参数在创建函数对象时被评估而不是在调用函数时进行评估，因此使用可变默认值是有问题的，因为更改将在函数返回后仍然有效。

- 6502

---

非常有趣。抱歉，测试数据集花了一些时间。我能够正确遍历所有节点。@6502，您是否将数据存储在图形中并执行了图形遍历，而不是使用字典？还是它实际上是相同的？ - Hani Goc

@HaniGoc：图是一种抽象的数据结构，可以用几种方式表示...其中之一是列表字典（但你也可以使用包含“链接”列表作为成员之一的对象）。什么更好取决于许多因素（如果您更关心速度还是大小，需要执行什么样的查询，图形是静态还是动态...）。 - 6502

Answer 2

这里有一种方法：在返回元素之前，它会递归地将每个元素简化为字符串形式。这应该是您的一个很好的起点。

def traverse(obj):
    '''
    stringify individual elems of an object where object can be a nested structure
    '''
    if isinstance(obj, dict):
        return dict((str(k),traverse(v)) for k,v in obj.items())
    else:
        return str(obj)  # no container, just values (str, int, float)

- labheshr