如何在 Python 中有效地实现递归 DFS？

Question

我正在尝试在 Python 中实现递归 DFS。我的尝试是：

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

使用 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

Answer 2

你可以这样做：

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 3

您可以为 path 变量使用 OrderedDict。这将使 in 运算符在常数时间内变为运行。然后将其转换为列表，只需从该字典中获取键，这些键保证按插入顺序排列。

我也会把整个函数的递归部分放到一个单独的函数中。这样你就不必在每个递归调用中将 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"))

如何在 Python 中有效地实现递归 DFS？

How to implement recursive DFS in Python efficiently?

python

algorithm

depth-first-search