在Python中比較超出最大遞歸深度？

我試圖找到從起始節點每個節點的距離和節點之間的連接在字典中給出在Python中比較超出最大遞歸深度？

我的代碼以小字典這樣的例子，但問題與詞典有超過20個節點運行良好我得到了一個錯誤

if child != parent and child not in my_list: 
RecursionError: maximum recursion depth exceeded in comparison

我卡在這裏，任何人都可以幫助我嗎？

我的代碼

def compute_distance(node, dic, node_distance, count, parent, my_list): 
    children = dic[node] 
    node_distance[node].append(count) 
    for child in children: 
     if child != parent and child not in my_list: 
      compute_distance(child, dic, node_distance, count + 1, node, children) 
    node_distance_dic = {} 
    node_distance_dic = {k: min(v) for k, v in node_distance.items()} 
    return node_distance_dic 

if __name__ == '__main__': 
    starting_node = 9 
    dic = {0: [1, 3], 1: [0, 3, 4], 2: [3, 5], 
       3: [0, 1, 2, 4, 5, 6], 4: [1, 3, 6, 7], 
       5: [2, 3, 6], 6: [3, 4, 5, 7, 8], 
       7: [4, 6, 8, 9], 8: [6, 7, 9], 9: [7, 8]} 
    print(compute_distance(starting_node, dic, defaultdict(list), 0, 0, []))

輸出（鍵=節點，值=距離）

{0: 4, 1: 3, 2: 4, 3: 3, 4: 2, 5: 3, 6: 2, 7: 1, 8: 1, 9: 0}

來源

2016-05-22 Joe

這是因爲您的遞歸堆棧呈指數增長。嘗試使用迭代算法或某種形式的記憶。雖然通過增加堆棧深度，該算法對於像20個節點這樣的小數量應該是可以的，但對於更大或更密集的圖形來說，這將不是有效的。 – EvilTak

對不起，我的編輯我的帖子 – Joe

我改變了它node_distance – Joe

我猜my_list在這裏跟蹤已訪問節點，但你永遠不更新它。因此，您應該添加正在處理的節點，以便不會在您已經通過的節點上調用遞歸。目前，只要圖形中存在循環，代碼就會無限循環。另外，不要忘記將其傳遞到一個新的水平：

def compute_distance(node, dic, node_distance, count, parent, my_list): 
    my_list.append(node) 
    ... 
    compute_distance(child, dic, node_distance, count + 1, node, my_list) 
    ...

然而，這種方法並不能計算到每一個其它從起始節點的最短路徑，它只是做圖的簡單穿越（底層算法是DFS）。

爲了實現你想要的，即從源到每個其他節點的最小距離，你應該看看廣度優先搜索（通常稱爲BFS）。

它會在線性時間內解決您的問題。

來源

2016-05-22 15:25:25

我保持卡車插入兒童再次在5行 – Joe

因爲你使用'children'作爲最後一個參數在第5行。 –

謝謝Breadth-First搜索解決我的問題 – Joe

實際上與圖表大小沒有任何關係。即使對於這個小圖，您也已經有了無限遞歸：

dic = {0: [1, 3], 1: [2, 0], 2: [3, 1], 3: [0, 2]} 
compute_distance(0, dic, defaultdict(list), 0, 0, [])

來源

2016-05-22 15:54:23

如果0：[1]之間存在連接，則必須是1：[0]之間的連接，因此dic爲{0：[1,3]，1：[0,2]，2：[1 ，3]，3：[0,2]} – Joe

啊，對。雖然這仍然已經讓你無限遞歸。嗯，顯然我已經這麼想過了，對於有向圖，**三個**節點就足夠了（'{0：[1]，1：[2]，2：[0]}'）。 –

在Python中比較超出最大遞歸深度？

回答

相關問題