这是我正在使用的词典:
{
'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
我发现使用堆栈比递归更容易解决这些搜索问题。
对于非常连通的图,你会发现路径的数量随着节点的数量呈指数增长。你知道吗
但是在你的图表上有一个快速的
dfs
:相关问题 更多 >
编程相关推荐