DFS的实现方式之一是用递归。
递归实现DFS时,似乎不需要使用任何栈。但实际上,使用的是由系统提供的隐式栈,也称为调用栈(Call Stack)。
"""
return True if there is a path from cur to target
"""
def DFS(cur, target, visited):
return true if cur is target
for next in each neighbor of cur:
if next is not in visited:
add next to visited
return true if DFS(next, target, visited) == True
return False