Этот Python Code использует первый поиск глубины (DFS) для поиска всех путей?

Question

Этот код приведен в Официальные очерки Python по теории графика. Отказ Вот код:

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

Я не адепт на Питоне, так как у меня еще не было достаточно практиковых и читать в нем. Можете ли вы объяснить код, связывая это к концепции брата для детей в диаграмме DFS? Спасибо.

Answer 1

Ключ к тому, что это DFS, заключается в том, что рекурсия происходит до накопления путей. Другими словами, рекурсион будет работать так же глубоко, как следует пойти, прежде чем делать что-либо на списке «Пути». Все самые глубокие братья и сестры накапливаются на «Пути», прежде чем вернуться в список.

Я верю, что код правильный с «Добавить», а не «продлить», поскольку «Пути» - это аккумулятор всех путей. Хотя это может быть написано как

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

(редактировать) ... вместо

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

Answer 2

Рассмотрим следующие модификации и сценарий выполнения:

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)

Выход:

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

Обратите внимание, как первый путь возвращается до добавления 3, а второй путь возвращается перед добавлением 4.

Answer 3

Да, этот алгоритм действительно DF. Обратите внимание, как он сразу рекует (уходит в ребенок), когда они зацикливаются по различным узлам, в отличие от широта первого поиска, который в основном составлял список жизнеспособных узлов (например, все на том же уровне глубины, ака-братьев и сестер) и только Оценка, когда те не соответствуют вашим требованиям.