使用Python生成器在图上进行DFS遍历

Question

我正在使用一个生成器来对一个图进行全面搜索，实际的数据集相当大，这里是我在一个小数据集上写的一部分代码：

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)

运行这个代码后，它会如预期那样输出从'2'到'7'的所有路径：

[[2, 1, 4, 5, 7], [2, 1, 5, 7], [2, 1, 6, 5, 7], [2, 3, 5, 7], [2, 5, 7]]

我想做的是修改这个生成器，让它做同样的事情，不过我希望能根据设定的起点和终点来返回路径，也就是我想用self.start_nodes和self.end_nodes来指定起点和终点。

因为我的生成器是一个递归函数，这让循环不同的起点和终点变得有些困难，我一直在思考这个问题，有没有什么好主意呢？

Answer 1

也许我没有理解你的问题，但我觉得你想把你的 __iter__ 函数换成下面这样的东西：

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

你可以在这个问题中找到更多关于生成器的信息：在这里。