1

问题：在有向循环图中给定一个边对象，找到前 n 个最近边（2000）。

数据结构：链接类和节点类。链接类有一个 from 和 to 节点，指向各自的节点对象。节点对象具有链接对象的传入和传出列表。

错误：我遇到了RuntimeError: maximum recursion depth exceeded。你能帮我找到解决方法吗。如果逻辑有问题或代码需要优化，请告诉我。我相信我遵循 BFS 策略，即从对象相关节点中创建一个队列，我可以遍历这些节点并查看它是否已被访问并尝试递归。

def start_search(self,link_object,neighbour_links):
    buffer_links=[]
    link_object.visited_flag=1
    neighbour_links.append(link_object)
    from_node=link_object.from_node
    to_node=link_object.to_node
    [buffer_links.append(link_object) for link_object in from_node.incoming_links]
    [buffer_links.append(link_object) for link_object in from_node.outgoing_links]
    [buffer_links.append(link_object) for link_object in to_node.outgoing_links]
    [buffer_links.append(link_object) for link_object in to_node.incoming_links]
    while len(buffer_links)>0 and len(neighbour_links)<1000:
        link_object=buffer_links.pop()
        if link_object.visited_flag==0:
           self.start_search(link_object,neighbour_links)
    return neighbour_links
4

2 回答 2

1

您可以通过在节点上使用先进的波前算法（广度优先搜索）来避免使用递归。这是算法的概述，它是一个小的适应，使其适用于边缘：

  1. top_dist使用最初为空的字典跟踪拓扑距离。
  2. 让dist = 0
  3. 将初始节点放入 set wavefront。
  4. top_dist[node] = dist为 中的每个节点设置wavefront。
  5. wavefront对于与该节点相邻的每个节点top_dist，将该节点添加到 setnext_wavefront中。
  6. 增量dist
  7. 放wavefront = next_wavefront
  8. 从 4 开始重复，直到无法访问更多节点。

如果某些节点仍未访问，则该图具有多个弱组件。

如果步骤 3 中的初始节点是您的初始边的端点，那么您可以使用top_dist边节点上的地图来获取到边的距离。我认为到边缘的距离的一个有用定义是min(top_dist(e1), top_dist(e2)) + 1. 现在你已经有了到每条边的距离，你可以抓取最近的 2000。

该算法是 O(|N|+|E|)——在边数和节点数的总和上是线性的。

于 2013-02-08T03:55:16.467 回答
0

使用 DAG 表示为映射到其后继节点的节点字典，您可以在发现节点时遍历它们：

>>> def bfs(dag, start, maximum):
        'Breadth-first search up to a given maximum number of nearest nodes'
        nearest = [start]
        seen = {start}
        for pred in nearest:
            for succ in dag.get(pred, ()):
                if succ not in seen:
                    seen.add(succ)
                    nearest.append(succ)
                    if len(nearest) == maximum:
                        return nearest
        return nearest
>>> dag = {'start': ['a', 'b', 'c'],
           'b': ['m', 'n'],
           'c': ['n', 'z'],
           'n': ['z'],
          }
>>> bfs(dag, 'start', 5)
['start', 'a', 'c', 'b', 'z']
于 2013-02-08T04:54:46.173 回答