無限循環，同時尋找所有的圖表蟒蛇

Question

的路徑，這是我使用的詞典：

{ 
    'timar': ['rimar', 'timas'], 
    'lares': ['pares', 'mares', 'laves'], 
    'lomas': ['lamas', 'limas', 'lemas'], 
    'gemas': ['lemas', 'remas', 'gimas'], 
    'lamas': ['lavas', 'latas', 'limas', 'lomas', 'lemas'], 
    'rimar': ['remar', 'timar', 'rimas'], 
    'lavas': ['laves', 'latas', 'lamas'], 
    'rimas': ['rimar', 'remas', 'timas', 'gimas', 'limas'], 
    'lemas': ['lomas', 'lamas', 'remas', 'limas', 'gemas'], 
    'mesas': [], 
    'remas': ['remos', 'rezas', 'remar', 'lemas', 'gemas', 'rimas'], 
    'pares': ['mares', 'lares'], 
    'teñir': ['reñir', 'tañir'], 
    'ceras': [], 
    'regar': ['rogar', 'regir', 'retar', 'rezar', 'remar'], 
    'remos': ['rezos', 'remas'], 
    'moras': [], 
    'regir': ['regar', 'reñir'], 
    'rezar': ['regar', 'rezas', 'retar', 'remar'], 
    'rezos': ['rezas', 'remos'], 
    'broma': [], 
    'lapiz': [], 
    'reñir': ['regir', 'teñir'], 
    'mares': ['pares', 'lares'], 
    'tocas': [], 
    'remar': ['remas', 'regar', 'rezar', 'retar', 'rimar'], 
    'timas': ['timar', 'limas', 'gimas', 'rimas'], 
    'laves': ['lares', 'lavas'], 'tañir': ['teñir'], 
    'bogar': ['rogar'], 
    'gimas': ['gemas', 'timas', 'limas', 'rimas'], 
    'latas': ['lavas', 'lamas'], 
    'rogar': ['bogar', 'regar'], 
    'rezas': ['rezar', 'rezos', 'remas'], 
    'retar': ['regar', 'rezar', 'remar'], 
    'limas': ['lamas', 'lomas', 'lemas', 'timas', 'gimas', 'rimas'] 
} 

這是我用找到的路徑中的代碼

def busqueda(self, start_vertex, end_vertex, path=[]): 
    """ find all paths from start_vertex to end_vertex in graph """ 
    print (start_vertex) 
    graph = self.diccionario 
    path = path + [start_vertex] 
    if start_vertex == end_vertex: 
     return [path] 
    if start_vertex not in graph: 
     return [] 
    paths = [] 
    for vertex in graph[start_vertex]: 
     if vertex not in path: 
      extended_paths = self.busqueda(vertex, end_vertex, path) 
      for p in extended_paths: 
       paths.append(p) 
    return paths 

Answer 1

我發現這些搜索問題比遞歸更容易處理堆棧。
通過非常連接的圖表，可以發現路徑數量隨節點數量呈指數增長。

但這裏是你的圖形快速dfs：

def dfs(graph, start, end): 
    stack = [[start]] 
    while stack: 
     path = stack.pop() 
     if path[-1] == end: 
      yield path 
      continue 
     for next_state in graph[path[-1]]: 
      if next_state in path: # Stop cycles 
       continue 
      stack.append(path+[next_state]) 

>>> paths = list(dfs(graph, 'mares', 'tañir')) 
>>> len(paths) 
12012 
>>> paths[0] 
['mares', 'lares', 'laves', 'lavas', 'lamas', 'lemas', 'gemas', 'gimas', 
'rimas', 'limas', 'timas', 'timar', 'rimar', 'remar', 'retar', 'rezar', 
'regar', 'regir', 'reñir', 'teñir', 'tañir'] 
>>> max(paths, key=len) 
['mares', 'pares', 'lares', 'laves', 'lavas', 'latas', 'lamas', 'lemas', 
'lomas', 'limas', 'rimas', 'rimar', 'timar', 'timas', 'gimas', 'gemas', 
'remas', 'remos', 'rezos', 'rezas', 'rezar', 'remar', 'retar', 'regar', 
'regir', 'reñir', 'teñir', 'tañir']