我對在存在回圈的無向（或有向）圖中處理 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中定義它？
uj5u.com熱心網友回復：
如果您對檢測是否存在任何回圈不感興趣，而只是對避免無限回圈（如果有）感興趣，那么類似以下遞回實作的方法對您有用：
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就會盡早回傳，而無需檢查其他鄰居和路徑，因此不會進行額外的遞回呼叫。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/482934.html