depth-first-search - 非递归 DFS 与 BFS，仅在堆栈与队列方面有所不同？

Question

我正在查看一般图的非递归 DFS和BFS。除了前者使用堆栈而不是队列这一事实之外，唯一的区别是它“延迟检查是否已发现顶点，直到顶点从堆栈中弹出，而不是在推送顶点之前进行检查”。为什么这个“访问”检查顺序不同？或者换一种说法，我们可以通过简单地将 BFS 中的队列替换为堆栈来将 BFS 更改为非递归 DFS 吗？

我检查了我能找到的所有帖子，例如this和this，但没有一个可以澄清这个问题。

Answer 1

是的，这是唯一的区别。

您从 wikipedia 显示的 DFS 算法有一个错误（好吧，至少是严重的低效率）——它将重新插入到已经访问过的 S 节点中。BFS 的设计更加合理，您可以将其更改为具有堆栈。