estoy implementando un método de búsqueda en profundidad en lenguaje Python. Lo estoy utilizando para hallar el camino óptimo entre dos nodos de un grafo, el problema está en que usando mi código, solamente consigo obtener el primer nodo del grafo.
Sé que el algoritmo crea una lista de caminos pendientes y que, hasta que llegue al nodo final, expande el primer camino, pero no consigo obtener todo el camino. Dejo mi código para saber si tengo algún elemento erróneo:
Código:
def busqueda_profundidad(self, origen, fin):
cp = [[origen]] # camino pendiente
while cp:
print(cp)
if not cp:
return False
if cp[0][0] == fin:
return list(reversed(cp[0][0]))
expansion = self.expandir(cp[0][0])
cp = expansion + cp[1:]
def expandir(self, camino):
expansion = self.sucesores(camino[0])
nuevos = []
for n in expansion:
if not n in camino:
nuevos.append([n] + camino)
return nuevos
def sucesores(self, station):
"""Devuelve la lista de posibles sucesores"""
return sorted(list(set(self.model[nodo])))
nodo
en la última línea oself.model
).