广度优先搜索：检查访问状态的时间

Question

在有向图的广度优先搜索（可能的循环）中，当一个节点退出队列时，其所有尚未访问的子节点都将进入队列，并且该过程将继续，直到队列为空为止。

有一次，我以另一种方式实现它，其中节点的所有子节点都排队，当节点出队时，检查访问状态。如果之前访问过正在退出队列的节点，则该节点将被丢弃，并继续到队列中的下一个节点。

但结果是错的。维基百科还说

深度优先搜索。。。。。。非递归实现类似于广度优先搜索，但在两个方面与之不同：它使用堆栈而不是队列，它延迟检查顶点是否已被发现，直到顶点从堆栈中弹出，而不是在推送顶点之前进行此检查。

然而，我无法理解到底有什么不同。为什么在弹出项目时深度优先搜索检查，而在排队前广度优先搜索必须检查？

Answer 1

DFS检查节点是否在解队列时被访问，因为它可能在“更深”级别被访问。例如：

A--B--C--E
|     |
-------

如果我们从A开始，那么B和C将被放在堆栈上；假设我们把它们放在堆栈上，那么B将首先被处理。当B现在被处理时，我们想向下到C，最后到E，如果我们从A发现C时将C标记为已访问，则不会发生这种情况。现在，一旦我们从B开始，我们会找到尚未访问的C，并再次将其放在堆栈上。在我们处理完E之后，堆栈上的所有C条目都需要被忽略，标记为visited将为我们提供帮助。

正如@PeterdeRivaz所说，对于BFS来说，无论我们在排队还是退出排队时检查节点是否被访问，这都不是正确性的问题，而是效率的问题。

Answer 2

假设您有一个图形：

 A---B---E
 |   |
 |   |
 C---D

您可以从A中搜索DFS。

如果使用深度优先搜索（假设子节点的顺序），您会期望它搜索节点A、B、D、C、E。

但是，如果您在将节点放置到堆栈之前将其标记为访问过的节点，那么您将访问A，B，D，E，C，因为当我们检查A时，C被标记为访问过的节点。

在某些应用程序中，您只想访问所有连接的节点，这是一种完全有效的方法，但从技术上讲，这不是深度优先搜索。

在广度优先搜索中，您可以在推送到队列之前或之后将节点标记为已访问。但是，由于队列中不会出现大量重复节点，因此在检查之前进行检查更为有效。

我不明白为什么你的BFS代码在这种情况下失败，也许如果你发布代码，它会变得更清晰？