在python（圖遍歷）的字典

的遞歸遍歷我有具有以下結構的字典：在python（圖遍歷）的字典

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)

我可以使用哪些遞歸函數來出行dictiona RY？

來源

2015-11-06 Hani Goc

一個簡單的解決辦法是保持一個「拜訪」前設置已知節點：使用

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中的默認參數在創建函數對象時被計算，而不是在函數被調用時被計算，因此使用可變默認值是一個問題，因爲在函數返回後更改仍然有效。

來源

2015-11-06 10:54:30 6502

真的很有意思對不起。花了一些時間在數據集上進行測試。我能夠正確地遍歷所有節點。 @ 6502你會將數據存儲在一個圖表中，並執行圖形遍歷而不是字典嗎？或者它實際上是一樣的？ –

@HaniGoc：圖是一種抽象數據結構，可以用幾種方式表示......其中一種是列表字典（但您可以使用包含「鏈接」列表作爲其中一個成員的示例對象）。什麼是更好的取決於許多因素（如果你更關心速度或大小，如果圖形是靜態或動態的，你需要做什麼樣的查詢）。 – 6502

這裏有一種方法：該遞歸簡化了每個元素爲一個字符串形式返回it..This應作爲一個很好的起點爲您

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)

來源

2015-11-06 10:51:26 labheshr

在python（圖遍歷）的字典

回答

相關問題