我们可以在不回溯的情况下做DFS吗?

Question

是否可以在不使用回溯方法的情况下实现DFS算法？如果是，那么请解释如何做到这一点。

Answer 1

如果不使用回溯，就无法实现 DFS 算法。

想想看，DFS 的核心性质是尽可能远离根节点进行探索，直到它必须返回探索其他潜在路径。这意味着一旦算法命中叶节点，您将回溯到探索该路径以查找其他选项之前的节点。

为了进一步证明这一点 https://medium.com/@andreaiacono/backtracking-explained-7450d6ef9e1a 将回溯定义为"一种通用算法......以增量方式构建解决方案的候选者，并在确定候选者不可能完成有效解决方案后立即放弃每个部分候选者("回溯"(。了解这如何适用于DFS。