Использует ли этот код Python поиск в глубину (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

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