Modification de la profondeur de recherche en premier avec les dictionnaires

Question

Il existe de nombreuses implémentations PFS de DFS, telles que this one, mais aucune d'entre elles n'inclut le coût. J'aimerais pouvoir enregistrer le coût total d'un chemin DFS, mais cette implémentation représente le graphe comme un dictionnaire d'ensembles.

graph = {'A': set(['B', 'C']), 
     'B': set(['A', 'D', 'E']), 
     'C': set(['A', 'F']), 
     'D': set(['B']), 
     'E': set(['B', 'F']), 
     'F': set(['C', 'E'])} 

def dfs(graph, start): 
    visited, stack = set(), [start] 
    while stack: 
     vertex = stack.pop() 
     if vertex not in visited: 
      visited.add(vertex) 
      stack.extend(graph[vertex] - visited) 
    return visited 

dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'} 

Je ne pense pas que les ensembles pourraient enregistrer adéquatement les coûts. Donc, je pense qu'au lieu de représenter le graphique comme un dictionnaire de dictionnaires serait un bon moyen de mettre en œuvre le coût. Je me demande comment cet algorithme peut-il être modifié pour utiliser un nouveau type de graphe à la place? Je ne suis toujours pas familier avec la syntaxe python, donc voir un exemple comme ça aide vraiment.

Sinon, s'il y a un moyen encore plus facile de représenter le coût, je suis ouvert aux suggestions

EDIT: D'accord, voici une autre façon de penser. Comment puis-je modifier le code ci-dessus afin qu'il traite les dictionnaires imbriqués de la même manière que les ensembles?

EDIT2: Je crois que je l'ai résolu moi-même, maintenant que je comprends la fonction keys() des dictionnaires renvoie une liste.

Answer 1

On dirait que NetworkX est ce que vous cherchez. DFS est inclus dans le package et sa mise en œuvre graphique est ce que vous voulez. J'espère que cela aide.