Graph recursive DFS when cycles exist?-CodePudding

I'm interested in handling DFS in undirected (or directed) graphs where cycles exist, such that the risk of entering an infinite-loop is non-trivial.

Note: This question is not about the cycle-detection problem(s) on LeetCode. Below is an iterative approach:

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

My question is, does such a recursive approach exist? And if so, how can it be defined in python?

CodePudding user response：

If you're not interested in detecting if there are any loops or not and just interested in avoiding infinite loops (if any), then something like the following recursive implementation would work for you:

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
    )

Note that a generator expression is used inside any, so it's evaluated in a lazy manner (one by one), and the whole any(...) expression returns True early as soon as a solution (i.e. a path to the destination) is found without checking the other neighbors and paths, so no extra recursive calls are made.