Tiefe zuerst ändern Suche mit Wörterbüchern

Question

Es gibt viele wirklich gute DFS-Python-Implementierungen wie this one, aber keine von ihnen enthalten Kosten. Ich möchte in der Lage sein, die Gesamtkosten eines DFS-Pfads aufzuzeichnen, aber diese Implementierung stellt das Diagramm als ein Wörterbuch von Sätzen dar.

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'} 

Ich glaube nicht, Sets könnten angemessen Kosten erfassen. Ich denke also, dass es eine gute Möglichkeit wäre, die Grafik als Wörterbücherwörterbuch darzustellen. d. h .:

Meine Frage ist, wie könnte dieser Algorithmus geändert werden, um stattdessen eine neue Art von Graphen zu verwenden? Ich bin mit der Python-Syntax immer noch nicht vertraut, ein solches Beispiel zu sehen hilft also wirklich.

Alternativ kann, wenn es eine noch einfachere Möglichkeit ist kostengünstig darzustellen, ich bin offen für Vorschläge

EDIT: Okay, hier ist eine andere Möglichkeit, darüber nachzudenken. Wie kann ich den obigen Code so ändern, dass er die verschachtelten Wörterbücher ähnlich behandelt wie Sätze?

EDIT2: Ich glaube, ich habe es selbst gelöst, jetzt, da ich die Tasten() Funktion von Wörterbüchern verstehe, gibt eine Liste zurück.

Answer 1

Sieht aus wie NetworkX ist, was Sie suchen. DFS ist in dem Paket enthalten und seine Graphimplementierung ist was Sie möchten. Ich hoffe es hilft.