问题:给定有向循环图中的边对象,找到前 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
最佳答案
您可以通过在节点上使用先进的波前算法(广度优先搜索)来避免使用递归。这是算法的概要,它是一个小的改编以使其适用于边缘:
- 使用最初为空的字典
top_dist
跟踪拓扑距离。 - 令
dist = 0
- 将初始节点放入集合
wavefront
。 - 为
wavefront
中的每个节点设置top_dist[node] = dist
。 - 对于与
wavefront
相邻但不在top_dist
中的每个节点,添加该节点以设置next_wavefront
。 - 增加
dist
- 设置
wavefront = next_wavefront
- 从 4 开始重复,直到无法访问更多节点。
如果某些节点仍未被访问,则该图具有多个弱组件。
如果第 3 步中的初始节点是初始边的端点,那么您可以在边的节点上使用 top_dist
映射来获取到边的距离。我认为到边缘的距离的有用定义是 min(top_dist(e1), top_dist(e2)) + 1
。现在您有了到每条边的距离,您可以抓取最近的 2000 个。
此算法的复杂度为 O(|N|+|E|) -- 与边数和节点数之和呈线性关系。
关于python - 找到前n条边,广度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14765137/