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

Question

我了解到递归深度优先搜索过程通过深度搜索整个树，跟踪所有可能的选择。

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

标签： algorithmrecursiondepth-first-search

Answer 1

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

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

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