作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在编写网络的递归广度优先遍历。我遇到的问题是网络经常是这样的:
1
/ \
2 3
\ /
4
|
5
所以我的遍历从1开始,然后遍历到2,然后是3。下一站是进行到4,所以2遍历到4。之后,3遍历到4,突然我在重复工作,因为两者行尝试遍历到 5。
我找到的解决方案是创建一个名为 self.already_traversed
的列表,每次遍历一个节点时,我都会将其附加到列表中。然后,当我从节点 4 开始遍历时,我检查以确保它尚未被遍历。
这里的问题是我为此使用了一个实例变量,所以我需要一种在第一次递归之前设置列表并在之后清理它的方法。我目前这样做的方式是:
self.already_traversed = []
self._traverse_all_nodes(start_id)
self.already_traversed = []
当然,在使用它们的函数之外使用两个变量是很糟糕的。有没有更好的方法可以将其放入我的遍历函数中?
这是实际的代码,虽然我知道它有点密集:
def _traverse_all_nodes(self, root_authority, max_depth=6):
"""Recursively build a networkx graph
Process is:
- Work backwards through the authorities for self.cluster_end and all
of its children.
- For each authority, add it to a networkx graph, if:
- it happened after self.cluster_start
- it's in the Supreme Court
- we haven't exceeded a max_depth of six cases.
- we haven't already followed this path
"""
g = networkx.Graph()
if hasattr(self, 'already_traversed'):
is_already_traversed = (root_authority.pk in self.visited_nodes)
else:
# First run. Create an empty list.
self.already_traversed = []
is_already_traversed = False
is_past_max_depth = (max_depth <= 0)
is_cluster_start_obj = (root_authority == self.cluster_start)
blocking_conditions = [
is_past_max_depth,
is_cluster_start_obj,
is_already_traversed,
]
if not any(blocking_conditions):
print " No blocking conditions. Pressing on."
self.visited_nodes.append(root_authority.pk)
for authority in root_authority.authorities.filter(
docket__court='scotus',
date_filed__gte=self.cluster_start.date_filed):
g.add_edge(root_authority.pk, authority.pk)
# Combine our present graph with the result of the next
# recursion
g = networkx.compose(g, self._build_graph(
authority,
max_depth - 1,
))
return g
def add_clusters(self):
"""Do the network analysis to add clusters to the model.
Process is to:
- Build a networkx graph
- For all nodes in the graph, add them to self.clusters
"""
self.already_traversed = []
g = self._traverse_all_nodes(
self.cluster_end,
max_depth=6,
)
self.already_traversed = []
最佳答案
关于python - 如何干净利落地避免递归函数中的循环(广度优先遍历),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32361493/
所以我有一个有向图,我添加了顶点和边。该图表示机场和它们之间的航类。当我运行广度优先或深度优先搜索以找到两个机场之间的路径时,我第一次得到了正确的答案,但是当我第二次使用完全相同的机场运行它时,它找不
我是一名优秀的程序员,十分优秀!