DFS vs BFS.2差异

Question

根据维基百科，DFS和BFS的实现基本上有两种不同。

它们是：
1）DFS使用堆栈，而BFS使用队列。（我理解这一点）。

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

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

谢谢

额外信息：
在上述两种算法的一个简单实现中，我们使用一个布尔数组（让我们命名它已访问）来跟踪哪个节点被访问或未被访问。问题提到了这个已访问的布尔数组。

Answer 1

wikipedia文章提到了两种执行DFS的方法：使用递归和使用堆栈。

为完整起见，我在此复制以下两种内容：

使用递归

procedure DFS(G,v):
   label v as discovered
   for all edges from v to w in G.adjacentEdges(v) do
      if vertex w is not labeled as discovered then
         recursively call DFS(G,w)

使用堆栈

procedure DFS-iterative(G,v):
   let S be a stack
   S.push(v)
   while S is not empty
      v ← S.pop() 
      if v is not labeled as discovered:
         label v as discovered
         for all edges from v to w in G.adjacentEdges(v) do
            S.push(w)

这里要知道的重要一点是方法调用是如何工作的。有一个底层堆栈，let调用是T。在调用该方法之前，将其参数推送到堆栈上。然后，该方法再次从堆栈中获取参数，执行其操作，并将其结果推回到堆栈上。然后调用方法从堆栈中获取该结果。

作为一个例子，考虑下面的片段：

function caller() {
    callResult = callee(argument1, argument2);
}

就堆栈T而言，发生的情况如下（示意图）：

// inside method caller
T.push(argument1);
T.push(argument2);
"call method callee"

// inside method callee
argument2 = T.pop();
argument1 = T.pop();
"do something"
T.push(result);
"return from method callee"

// inside method caller
callResult = T.pop();

这与第二个实现中发生的情况差不多：显式使用堆栈。您可以将在第一个代码段中调用DFS与在堆栈上推动顶点进行比较，并将在第一个代码段中执行对DFS的调用与从堆栈中弹出顶点进行比较。

从堆栈中弹出顶点v后的第一件事是将其标记为已发现。这相当于将其标记为已发现，作为执行DFS的第一步。

Answer 2

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

然而，当我为每个节点使用两个标志时，也有这样的情况：进入时设置一个标志，离开节点时设置一个标志（通常，我将DFS写成递归的，所以，就在递归函数的末尾）。我想当我需要像这样的东西时，我使用了这样的东西：连通图中的强连通分支或临界点（=节点，如果删除，图将失去连通性）。此外，退出节点的顺序通常用于拓扑排序（拓扑排序只是处理节点的顺序的倒数）。