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

Question

在有向图的广度优先搜索中(可能的循环),当节点出列时,其尚未被访问的所有子节点都被排队,并且该过程继续,直到该队列为空.

有一次,我以相反的方式实现它,其中所有节点的子节点都被排队,并且当节点出列时检查访问状态.如果之前已访问过出队的节点,则将其丢弃,并且该过程继续到队列中的下一个节点.

但结果是错误的.维基百科也说

深度优先搜索......非递归实现类似于广度优先搜索,但在两个方面与它不同:它使用堆栈而不是队列,并延迟检查是否已发现顶点顶点从堆栈中弹出,而不是在按下顶点之前进行此检查.

但是,我无法理解究竟是什么区别.为什么在弹出项目时首先进行深度搜索检查,并且在排队之前必须检查广度优先搜索？

Answer 1

DFS

假设你有一个图表:

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

你从A搜索DFS.

如果使用深度优先搜索(假设孩子的某种顺序),你会期望它搜索节点A,B,D,C,E.

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

在某些您只想访问所有连接节点的应用程序中,这是完全有效的事情,但从技术上讲,它不是深度优先搜索.

BFS

在广度优先搜索中,您可以在推送到队列之前或之后将节点标记为已访问.但是,之前检查更有效,因为队列中没有大量重复节点.

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

Answer 2

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

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

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

正如@PeterdeRivaz 所说，对于 BFS，这不是正确性的问题，而是效率的问题，我们是否在入队或出队时检查节点是否被访问过。