使用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 

您可以找到有關發電機in this question的更多信息。