python - 找到前n条边，广度优先搜索

Question

问题:给定有向循环图中的边对象，找到前 n 个最近的边 (2000)。

数据结构:Link类和Node类。链接类有一个 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

Answer 1

您可以通过在节点上使用先进的波前算法(广度优先搜索)来避免使用递归。这是算法的概要，它是一个小的改编以使其适用于边缘:

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

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

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

此算法的复杂度为 O(|N|+|E|) -- 与边数和节点数之和呈线性关系。