algorithm - 为什么在执行广度优先搜索时节点需要“访问”状态？

Question

我编写了一个用于在图表中搜索的算法，并使用一个标志来指示是否访问了一个节点，这样我就不会陷入循环，以防我的图表中有一个圆圈。

我后来检查了一本算法书，它使用了 3 个状态而不是 2 个，第 3 个是“访问”状态。我想知道为什么它在那里，因为我可以在没有它的情况下执行搜索？

Answer 1

“访问”状态没有多大意义——每个节点只有在你处理它的邻居并将它们排入队列时才会处于这种状态——而且你完全知道你当时正在访问哪个节点。

有意义（但仍然不需要）是“排队”状态，例如此动画中的灰色节点（来自维基百科）

Answer 2

它不是严格需要的，但是一些使用 BFS 作为基本构建块的算法使用此信息，因此额外的状态。

我想从教育的角度来看这也是一个好处，因为插图可以更好地理解正在发生的事情。