深度优先搜索是否会产生冗余？

Question

我试图理解维基百科上规范的DFS伪代码(http://en.wikipedia.org/wiki/Depth-first_search)--特别是使用堆栈的非递归实现。

在BFS中，您在将节点推送到队列之前检查它是否已经被探索过，这保证了不会有节点被多次推送到队列上。但是在DFS中，只有当您将节点从堆栈中弹出时，才会检查它是否已经被探索。这似乎是故意的，正如维基百科页面所说：“[DFS]推迟检查是否发现顶点，直到顶点从堆栈中弹出，而不是在推动顶点之前进行检查。”

但是这种延迟似乎会导致节点被多次推送到堆栈上。例如，考虑节点1指向节点2，节点3指向节点4，以此类推，直到节点100的图。这些节点中的每一个都指向节点0。

考虑将维基百科DFS算法应用于此图，节点1作为起始状态。首先，节点0将被推送到堆栈上。然后将推送节点2。接下来，节点2将从堆栈中弹出，由于尚未对其进行探索，其子节点将被推到堆栈上（而不检查它们是否已添加到堆栈中！）。节点2的子节点是节点0和节点3。接下来，将展开节点3，将节点0和节点4推到堆栈上。这将继续，直到堆栈中填满100个节点0。

我的问题是：如果DFS产生这种冗余，它为什么会延迟检查，从而与BFS不同？

Answer 1

我认为你把维基百科算法看得过于字面意思，而不是思考访问/发现一个节点意味着什么。在BFS中，您也可以将节点的所有子节点/相邻节点推送到队列中，但是您必须丢弃已经发现的节点；DFS也是如此。

在BFS和DFS中，您可以选择：

1. 不推送已发现的节点。或

BFS和DFS之间的唯一区别在于，您将进入BFS中的堆栈，而不是DFS中的队列。

Answer 2

我的错，我认为你在最后一句提出的问题是关于DFS的。。。在这个特定的实现中，向堆栈推送确实是多余的，并且可以通过在“推送”之前添加（如果未访问）条件来轻松避免。

也就是说，它不会改变摊销复杂性O（|E||V|）

Answer 3

你是对的，在维基百科的非递归DFS实现中，每个顶点将被放入堆栈中的次数与传入边的数量相同。

但我认为这不是有意的。您可以看到，这里的递归实现取自Cormen等人的“数据结构和算法简介”。这本书可以被认为比非递归DFS伪代码的源代码更“规范”。你们可以看到，在深入递归之前，目标顶点已经被检查过了。这似乎更合理。

总之，我认为维基百科的实现中存在非关键性缺陷。不盲目相信“正典”通常是一个好办法。