Est-ce que ce code python utilise Depth First Search (DFS) pour trouver tous les chemins?

Question

Ce code est donné en python official essays on graph theory. 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 habile à python comme je l'ai pas encore eu assez de pratiquer et y lire. Pouvez-vous s'il vous plaît expliquer le code en reliant cela au concept enfant-frère dans le diagramme DFS? Merci.

Answer 1

La clé pour voir que c'est un DFS est que la récursion se passe 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 soeurs les plus profonds sont accumulés sur des «chemins» avant de retourner la liste.

Je crois que le code est correct avec "append" plutôt que "extend", puisque "paths" est l'accumulateur de tous les chemins. Bien qu'il pourrait probablement être écrit comme

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

Oui, cet algorithme est en effet un DFS. Remarquez comment il récursera tout de suite (allez dans l'enfant) lors de la boucle sur les différents noeuds, par opposition à une première recherche qui ferait essentiellement une liste de noeuds viables (par exemple tout sur le même niveau de profondeur, frères et soeurs) récursif lorsque ceux-ci ne correspondent pas à vos exigences.

Answer 3

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 chemin est renvoyé avant d'ajouter 3, et le second chemin est retourné avant d'ajouter 4.