Fa questo codice Python impiega ricerca in profondità (DFS) per la ricerca di tutti i percorsi?

Question

Il codice è dato in pitone saggi ufficiali sulla teoria dei grafi . Ecco il codice:

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

Io non sono abili a Python come non ho ancora avuto abbastanza di praticare e la lettura in esso. Si può spiegare il codice relativo questo al concetto di bambino-sibling nel diagramma DFS? Grazie.

Answer 1

La chiave per vedere che si tratta di un DFS è che la ricorsione accade prima l'accumulo di percorsi. In altre parole il ricorsione andrà come profondo come deve andare prima di mettere qualcosa nella lista "percorsi". Tutti i fratelli più profonde sono accumulati su "percorsi", prima di tornare alla lista.

Credo che il codice è corretto con la "accodamento" piuttosto che "estendere", in quanto "percorsi" è l'accumulatore di tutti i percorsi. Anche se potrebbe probabilmente essere scritto come

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

(edit) ... invece di

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

Answer 2

Si consideri il seguente modifiche e l'esecuzione di 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)

Output:

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

Si noti come il primo percorso viene restituito prima di aggiungere 3, e il secondo percorso viene restituito prima di aggiungere 4.

Answer 3

Sì, questo algoritmo è davvero un DFS. Notate come si recurses subito (entrare nel bambino), quando il ciclo sopra i vari nodi, al contrario di una ricerca in ampiezza che in sostanza fare una lista di nodi vitali (ad esempio, tutto sullo stesso livello di profondità, alias i fratelli) e solo recursing quando questi non corrispondano a quanto richiesto.