避免連接組件分析中的最大遞歸深度？

我想標記連接組件的所有元素。圖表的鏈接使用字典詞典進行格式化。遞歸算法似乎很快，不幸的是對於較大的圖，最大遞歸深度造成了問題，我不想每次都增加最大遞歸長度。你知道如何重寫這段代碼，所以深度不會再麻煩了嗎？避免連接組件分析中的最大遞歸深度？

import numpy as np 
def find_components(dists): 

    N = len(dists.keys()) 
    labels = np.zeros(N, dtype = np.int) - 1 
    n = 0 
    steps = 0 

    def walk(j): 
     for k in dists[j].keys(): 
      if (labels[k] == -1): 
       labels[k] = labels[j] 
       walk(k) 

    remains = (labels == -1) 
    while n < N: 
     i = np.arange(0,N,1)[remains][np.random.randint(0,N - n)] 
     labels[i] = i 
     walk(i) 
     remains = (labels == -1) 
     n = N - len(np.nonzero(remains)[0]) 
    unique = np.unique(labels) 
    labels_ = np.zeros(N, dtype = np.int) - 1 
    for i, label in enumerate(unique): 
     labels_[labels == label] = i 
    return labels_

來源

2016-03-21 varantir

好像你使用DFS（深度優先搜索）在這裏，這可能會走得很深的特定的輸入數據。我認爲你可以用BFS（廣度優先搜索）方式重寫它。 – starrify

轉換walk()從遞歸函數的迭代版本：

import collections 

def walk(j): 
    lifo = collections.deque(j) 

    while lifo: 
     for k in dists[lifo.pop()].keys(): 
      if labels[k] == -1: 
       labels[k] = labels[j] 
       lifo.append(k)

來源

2016-03-22 05:33:37 RootTwo

這也是BFS。謝謝！ – varantir

避免連接組件分析中的最大遞歸深度？

回答

相關問題