当循环存在时图形递归 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(...)表达式returnsTrue 在不检查其他邻居和路径的情况下尽早找到解决方案（即到达目的地的路径），因此不会进行额外的递归调用。

当循环存在时图形递归 DFS？

Graph recursive DFS when cycles exist?

python

recursion

traversal

graph

depth-first-search