algorithm - DFS 与 BFS .2 差异

Question

根据维基百科，DFS 和 BFS 的实现基本上有两个区别。

他们是:
1)DFS用栈，BFS用队列。(这个我理解)。

2)DFS 延迟检查顶点是否已被发现，直到顶点从堆栈中弹出，而不是在推送顶点之前进行此检查。

我无法理解第二个区别。我的意思是为什么 DFS 在从堆栈中删除后访问节点，而 BFS 在将节点添加到队列之前访问该节点。

谢谢!

额外信息:
在上述两种算法的简单实现中，我们采用一个 bool 数组(让我们将其命名为已访问)来跟踪是否访问了哪个节点。问题提到了这个已访问的 bool 数组。

Answer 1

这可能是我第一次听说 DFS 会延迟设置“已发现”属性，直到从堆栈中弹出(即使在 wikipedia 上，递归和迭代伪代码都将当前节点标记为在推送之前已发现堆栈中的子项)。此外，如果您仅在完成处理后才“发现”该节点，我认为您很容易陷入无限循环。

然而，在某些情况下，我为每个节点使用两个标志:一个在进入节点时设置，一个在离开节点时设置(通常，我将 DFS 写为递归的，所以，就在递归函数的末尾)。我想我在需要这样的东西时使用了这样的东西:强连接组件或连接图中的关键点(=“节点，如果删除这些节点，图形将失去其连接性”)。此外，退出节点的顺序通常用于 topological sorting。 (拓扑排序只是您完成处理节点的顺序的倒数)。