问题:求有向循环图中给定边对象的前n个最近边(2000)。
数据结构:链路类和节点类link类有一个from和to节点,它指向各自的节点对象。节点对象具有链接对象的传入和传出列表。
错误:我正遭受一个运行时错误:最大递归深度超过了。你能帮我找到一个解决方法吗?如果逻辑错误或者代码需要优化,请告诉我。我相信我遵循bfs的策略,用对象相关的节点创建一个queu,我可以遍历它,看看它是否被访问过,然后尝试递归。
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
。
为top_dist[node] = dist
中的每个节点设置wavefront
。
对于不在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 |)线性的边和节点数之和。