Ce code Python utilise-t-il Depth First Search (DFS) pour trouver tous les chemins ?

Question

Ce code est donné dans essais officiels de python sur la théorie des graphes.Voici le 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

Je ne suis pas adepte de Python car je n'en ai pas encore assez de m'entraîner et de lire.Pouvez-vous s'il vous plaît expliquer le code en le reliant au concept enfant-frère et sœur dans le diagramme DFS ?Merci.

Answer 1

La clé pour voir qu'il s'agit d'un DFS est que la récursion se produit avant l'accumulation de chemins.En d’autres termes, la récursivité ira aussi loin que nécessaire avant de mettre quoi que ce soit sur la liste des « chemins ».Tous les frères et sœurs les plus profonds sont accumulés sur des « chemins » avant de renvoyer la liste.

Je crois que le code est correct avec "ajouter" plutôt que "étendre", puisque "chemins" est l'accumulateur de tous les chemins.Même si cela pourrait probablement s'écrire ainsi

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

(modifier) ​​... au lieu de

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

Answer 2

Considérez les modifications suivantes et exécution d'un script:

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)

Sortie:

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

Notez comment le premier trajet est retourné avant d'ajouter 3, et le second trajet est retourné avant d'ajouter 4.

Answer 3

Oui, cet algorithme est en effet un DFS. Remarquez comment il récursif tout de suite (aller dans l'enfant) lors de la boucle sur les différents nœuds, par opposition à une largeur d 'abord la recherche qui essentiellement faire une liste de nœuds viables (par exemple, tout sur le même niveau de profondeur, alias frères et sœurs) et seulement récursion lorsque ceux-ci ne correspondent pas à vos besoins.