Verwendet dieser Python-Code Tiefensuche (DFS) zum Suchen aller Pfade?

Question

Dieser Code ist in python official essays on graph theory angegeben. Hier ist der Code:

def find_all_paths(graph, start, end, path=[]): 
     path = path + [start] 
     if start == end: 
      return [path] 
     if not graph.has_key(start): 
      return [] 
     paths = [] 
     for node in graph[start]: 
      if node not in path: 
       newpaths = find_all_paths(graph, node, end, path) 
       for newpath in newpaths: 
        paths.append(newpath) 
     return paths 

ich bei Python nicht geschickt bin, wie ich noch nicht genug hatte zu praktizieren und zu lesen darin. Können Sie den Code erklären, indem Sie ihn auf das Kind-Geschwister-Konzept im DFS-Diagramm beziehen? Vielen Dank.

Answer 1

Der Schlüssel zu sehen, dass es ein DFS ist, ist, dass die Rekursion vor der Anhäufung von Pfaden passiert. Mit anderen Worten, die Rekursion wird so tief gehen wie nötig, bevor irgendwas auf die "Pfade" -Liste gesetzt wird. Alle tiefsten Geschwister sammeln sich auf "Pfaden" an, bevor sie die Liste zurückgeben.

Ich glaube, dass der Code mit dem "append" statt "extend" korrekt ist, da "Pfade" der Akkumulator aller Pfade ist. Obwohl es wahrscheinlich als

paths += find_all_paths(graph, node, end, path) 

(edit) ... statt

newpaths = find_all_paths(graph, node, end, path) 
for newpath in newpaths: 
    paths.append(newpath) 

Answer 2

Ja, dieser Algorithmus ist in der Tat ein DFS. Beachten Sie, wie es sich sofort rekursiv verhält (in das Kind hinein), wenn Sie die verschiedenen Knoten durchlaufen, im Gegensatz zu einer Breitensuche, die im Grunde nur eine Liste von brauchbaren Knoten (zB alles auf derselben Tiefesebene, auch Geschwister genannt) und nur ergibt rekursiv, wenn diese nicht Ihren Anforderungen entsprechen.

Answer 3

Betrachten Sie die folgende Modifikationen und Ausführungsskript geschrieben werden könnte:

def find_all_paths(graph, start, end, path=[]): 
    path = path + [start] 
    print 'adding %d'%start 
    if start == end: 
     return [path] 
    if not graph.has_key(start): 
     return [] 
    paths = [] 
    for node in graph[start]: 
     if node not in path: 
      paths.extend(find_all_paths(graph, node, end, path)) 
    print 'returning ' + str(paths) 
    return paths 

G = {1:[2,3,4], 2:[1,4], 3:[1,4], 4:[1,2,3]} 
find_all_paths(G, 1, 4) 

Ausgang:

adding 1 
adding 2 
adding 4 
returning [[1, 2, 4]] 
adding 3 
adding 4 
returning [[1, 3, 4]] 
adding 4 
returning [[1, 2, 4], [1, 3, 4], [1, 4]] 

Hinweis wie der erste Pfad wird vor dem Hinzufügen von 3 zurückgegeben, und der zweite Pfad wird vor dem Hinzufügen von 4 zurückgegeben.