Ist dieser Python-Code Tiefensuche (DFS) für die Suche nach allen Pfaden beschäftigt?

Question

Dieser Code gegeben in Python offiziellen Essays über Graphentheorie . 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

bin ich bei Python nicht geschickt, wie ich es noch nicht genug hatte der praktizierenden und darin zu lesen. Können Sie bitte Bezug durch diese auf das Kind-Geschwister Konzept in DFS Diagramm, das den Code erklären? Danke.

Answer 1

Der Schlüssel zu sehen, dass es eine DFS ist, dass die Rekursion vor der Anhäufung von Pfaden geschieht. Mit anderen Worten geht die Rekursion so tief wie es vor der Inbetriebnahme alles auf der „Weg“ Liste gehen muss. Alle die tiefsten Geschwister angehäuft auf „Pfade“, bevor die Liste zurück.

ich glaube, der Code korrekt mit dem „append“ statt „erweitern“, da „Wegen“ ist der Speicher aller Pfade. Obwohl es wahrscheinlich als

geschrieben werden konnte

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

Sie sich die folgenden Modifikationen und Ausführungsskript:

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)

Ausgabe:

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]]

Beachten Sie, wie der erste Weg vor 3 Zugabe zurückgeführt wird, und der zweite Pfad zurückgeführt wird vor 4 hinzugefügt wird.

Answer 3

Ja, dieser Algorithmus ist in der Tat ein DFS. Beachten Sie, wie Sie es sofort recurses (geht in das Kind), wenn die verschiedenen Knoten Schleifen über, im Gegensatz zu einer Breitensuche, die im Grunde eine Liste von lebensfähigen Knoten machen würde (zum Beispiel alles, was auf dem gleichen Niveau der Tiefe, auch bekannt als Geschwister) und nur Rekursion, wenn diese nicht Ihren Anforderungen entsprechen.