tratando de encontrar toda la ruta en un gráfico usando DFS recursivo en Python

Encontré una solución que se publicó algunas veces y traté de aplicarla a mi ejercicio, pero no funciona. Tengo un gráfico de clase que tiene nodos y aristas y un método childrenOf que da a todos los hijos de un nodo. Todo esto funciona bien. Este es mi código para la búsqueda DFS y quiero encontrar todas las rutas:

def myDFS(graph,start,end,path=[]): path=path+[start] if start==end: return path paths=[] for node in graph.childrenOf(start): if node not in path: paths.extend(myDFS(graph,node,end,path)) return paths 

Sólo tengo listas vacías. ¿A dónde necesito mirar? Cuando estaba haciendo path = myDFS … en el bucle tenía al menos la última ruta. Intenté path + = myDFS sin éxito. La gráfica fue creada con éxito por lo que no proviene de ella. Gracias

Como solo desea obtener todas las rutas de principio a fin, la ruta se adjunta a su lista de rutas total cuando llega al final. La lista total de rutas no se devuelve sino que se llena:

 paths = [] def myDFS(graph,start,end,path=[]): path=path+[start] if start==end: paths.append(path) for node in graph.childrenOf(start): if node not in path: myDFS(graph,node,end,path) 

He aplanado JSON de los dictados nesteds (la profundidad era cuatro)

 {'output': 'lev1_key1': 'v11', 'lev1_key2': { {'lev2_key1': 'v21', 'lev2_key2': 'v22', } } 

con llamada recursiva de

 paths = [] _PATH_SEPARATOR = '/' def flatten(treeroot, path=''): path=path if isinstance(treeroot, dict): for k in treeroot.keys(): s_path = path + _PATH_SEPARATOR + str(k) flatten(treeroot[k], path=s_path) elif isinstance(treeroot, str): path = path + _PATH_SEPARATOR + treeroot paths.append(path) elif isinstance(treeroot, list): # if node has more than one child for k in treeroot.keys(): s_path = path + _PATH_SEPARATOR + str(k) flatten(k, path=s_path) 

el resultado es

 { 'output/lev1_key1': 'v11', 'output/lev1_key2/lev2_key1': 'v21', 'output/lev1_key2/lev2_key2': 'v22', }