使用python生成器在图上使用DFS
|
我正在使用生成器在图形上进行全面搜索，实际数据集相当大，这是我在小型数据集上编写的部分代码：
class dfs:
def __init__(self):
self.start_nodes = [1,2] # not used, see below explanation
self.end_nodes = [5,7] # not used, see below explanation
_graph={
1 : [4,5,6,2],
2 : [1,3,5],
4 : [1,5],
3 : [5,2],
5 : [3,1,4,6,2,7],
6 : [1,5],
7 : [5],
}
def __iter__(self):
return self.find_path(self._graph, 2, 7)
def find_path(self, graph, start, end, path=[]):
path = path + [start]
if start == end:
yield path
if not graph.has_key(start):
return
for node in graph[start]:
if node not in path:
for new_path in self.find_path(graph, node, end, path):
if new_path:
yield new_path
d = dfs()
print list(d)
没有找到相关结果
已邀请:
1 个回复
森含械
函数：def __iter__(self): for start in self.start_nodes: for end in self.end_nodes: for path in self.find_path(self._graph, start, end): yield path