Updated 2022-05-21
Viewed 8 times
0

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?

🔴 No definitive solution yet
📌 Solution 1

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
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.