存在循环时的图递归DFS ?

Question

我对处理无向(或有向)图中的DFS感兴趣，其中存在循环，因此进入无限循环的风险是非平凡的。

注意:这个问题不是关于LeetCode上的循环检测问题。下面是一个迭代方法:

g = {'a':['b','c'],
'b':['a','f'],
'c':['a','f','d'],
'd':['c','e'],
'e':['d'],
'f':['c','b'],
'g':['h'],
'h':['g']
}
def dfs(graph, node, destination):
stack = [node]
visited = []
while stack:
current = stack.pop()
if current == destination:
return True
visited.append(current)
next_nodes = list(filter(lambda x: x not in visited + stack, graph[current]))
stack.extend(next_nodes)
return False
dfs(g,'h', 'g')  
>>> True 
dfs(g,'a', 'g')  
>>> False

我的问题是，这样的递归方法存在吗?如果是的话，如何在python中定义它呢?

Answer 1

如果您对检测是否存在循环不感兴趣，而只是对避免无限循环(如果有的话)感兴趣，那么像下面这样的递归实现将为您工作:

def dfs(graph, node, destination, visited=None):
if visited is None:
visited = set()
if node == destination:
return True
visited.add(node)
return any(
dfs(graph, neighbor, destination, visited=visited)
for neighbor in graph[node]
if neighbor not in visited
)

请注意，生成器表达式在any中使用，因此它以惰性方式(逐个)求值，并且整个any(...)表达式在找到解决方案(即到达目的地的路径)时尽早返回True，而无需检查其他邻居和路径，因此没有额外的递归调用。