有没有退出 DFS 程序的好方法？

Question

我了解到递归 depth-first 搜索过程按深度搜索整棵树，追踪所有可能的选择。

但是，我想修改函数，以便我可以在中间调用一个 "total exit"，这将完全停止递归。有没有有效的方法来做到这一点？

Answer 1

有 3 种方法可以做到这一点。

Return 表示您已完成的值，并在每次调用后检查它。
抛出异常并在顶层捕获。
从递归切换到堆栈，然后 break 循环。

第三种效率最高，但工作量最大。第一个是最清楚的。第二种简单且有效..但往往会使代码更复杂并且在许多语言中效率低下。

Answer 2

一个常见的 DFS 是这样工作的：

DFS(u){
    mark[u] = true
    for each v connected to u:
        if(!mark[v]) DFS(v)
}

您可以尝试这样的操作：

static bool STOP = false;   

DFS(u){
    if(STOP) return;
    mark[u] = true
    for each v connected to u:
        if(!mark[v]) DFS(v)
}

在 DFS 的开头放置一个静态 bool 应该可以保证，一旦将 STOP 设置为 true，从现在开始 DFS 的堆栈递归调用不会做任何重要的事情。不幸的是，它不仅会忽略堆叠的函数调用，而且会立即完成。

Answer 3

协程

比利接受的答案存在错误的三分法。有超过三 (3) 种方法可以做到这一点。 Coroutines 非常适合这个，因为它们是可暂停、可恢复和可取消的 -

def dfs(t):
  if not t:
    return                      # <- stop 
  else:
    yield from dfs(t.left)      # <- delegate control to left branch
    yield t.value               # <- yield a value and pause
    yield from dfs(t.right)     # <- delegate control to right branch

调用者可以控制协同程序的执行 -

def search(t, query):
  for val in dfs(t):
    if val == query:
      return val        # <- return stops dfs as soon as query is matched
  return None           # <- otherwise return None if dfs is exhausted

支持协程的语言通常有一些其他的通用函数，使它们在各种方面都很有用

持久迭代器

另一个类似于协程的选项是流，或持久迭代器。有关具体示例，请参阅。

有没有退出 DFS 程序的好方法？

Is there a good way to exit a DFS procedure?

algorithm

recursion

depth-first-search