Как эффективно реализовать рекурсивную DFS в Python?

Question

Я пытаюсь реализовать рекурсивную DFS в Python. Моя попытка:

def dfs_recursive(graph, vertex, path=[]):
    path += [vertex]

    for neighbor in graph[vertex]:
        # print(neighbor)
        if neighbor not in path:  # inefficient line
            path = dfs_recursive(graph, neighbor, path)

    return path


adjacency_matrix = {"s": ["a", "c", "d"], "c": ["e", "b"],
                    "b": ["d"], "d": ["c"], "e": ["s"], "a": []}

К сожалению, строка if neighbor not in path очень неэффективна, и это не то, что я должен делать. Я хотел бы, чтобы выходные данные были узлами, которые посещаются по порядку, но без дубликатов. Итак, в этом случае:

['s', 'a', 'c', 'e', 'b', 'd']

Как вывести узлы, которые посещаются в порядке DFS, но без дубликатов, эффективно?

Answer 1

Вы можете сделать что-то вроде этого:

def dfs_recursive(graph, vertex, dic, path):

    dic[vertex] = 1;
    path += vertex
    for neighbor in graph[vertex]:

        if not neighbor in dic: 
           dfs_recursive(graph, neighbor, dic, path)



graph = {"s": ["a", "c", "d"], "c": ["e", "b"],
                    "b": ["d"], "d": ["c"], "e": ["s"], "a": []}

path = [];
dic = {}
dfs_recursive(graph,"s",dic,path);

print(path)

Вам нужен словарь для эффективного поиска, если вы хотите путь, вы можете добавить его в другую структуру, как показано выше.

Answer 2

Вы можете использовать OrderedDict для своей переменной path. Это заставит оператор in работать в постоянное время. Затем, чтобы превратить это в список, просто получите ключи от этого dict, которые гарантированно будут в порядке вставки.

Я бы также поместил рекурсивную часть всей функции в отдельную функцию. Таким образом, вам не нужно передавать path в качестве аргумента в каждом рекурсивном вызове:

from collections import OrderedDict

def dfs_recursive(graph, vertex):
    path = OrderedDict()

    def recur(vertex):
        path[vertex] = True
        for neighbor in graph[vertex]:
            if neighbor not in path:
                recur(neighbor)

    recur(vertex)
    return list(path.keys())

adjacency_matrix = {"s": ["a", "c", "d"], "c": ["e", "b"],
                    "b": ["d"], "d": ["c"], "e": ["s"], "a": []}

print(dfs_recursive(adjacency_matrix, "s"))

Answer 3

Использование dict:

def dfs_recursive(graph, vertex, path={}):
    path[vertex] = None

    for neighbor in graph[vertex]:
        if neighbor not in path:
            dfs_recursive(graph, neighbor)

    return path

adjacency_matrix = {"s": ["a", "c", "d"], "c": ["e", "b"],
                    "b": ["d"], "d": ["c"], "e": ["s"], "a": []}

print(*dfs_recursive(adjacency_matrix, "s"))

Вывод:

s a c e b d