如何在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

您可以对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"))

Answer 2

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

你可以做这样的事情：

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)

你需要有一个字典来进行有效的查找，如果你想要路径，你可以把它添加到一个不同的结构中，如上所示。