避免连接组件分析中的最大递归深度？

我想标记连接组件的所有元素。图表的链接使用字典词典进行格式化。递归算法似乎很快，不幸的是对于较大的图，最大递归深度造成了问题，我不想每次都增加最大递归长度。你知道如何重写这段代码，所以深度不会再麻烦了吗？避免连接组件分析中的最大递归深度？

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

避免连接组件分析中的最大递归深度？

回答

相关问题