c++ - 查找 STL 队列中是否已存在项目

Question

我正在使用 STL 队列在图上实现 BFS（广度优先搜索）。如果队列中不存在该节点，我需要将该节点推送到队列中。但是，STL 队列不允许迭代其元素，因此我不能使用 STL 查找功能。

我可以在每个节点被访问时使用一个标志来标记它们，并且仅在标志为假时推送它们，但是，我需要多次运行 BFS 并且每次之后我都必须重置所有标志，所以我结束了使用计数器而不是标志，但我仍然想知道是否有在队列中查找项目的标准方法。

Answer 1

我假设您正在 BFS 中实施“封闭集”的概念？这样做的标准方法是简单地维护一个单独的std::set或std::unordered_set已经遇到的元素。这样，您将获得 O(lg n ) 或 O(1) 查找，而在遍历队列时，如果支持，将花费 O( n ) 时间。

Answer 2

接受的答案是愚蠢的。

BFS 搜索中的每个项目都将经历三种状态：未访问、已访问但未完成、已访问。出于搜索目的，您可以将其缩减为已访问或未访问...

你只需要使用一个标志...

旗帜只是交替出现。

好吧，随着树的第一次遍历，每个节点将从 false（未访问）开始，然后变为 true（已访问）。在第二次遍历时，它将切换为 true（未访问）并转到 false（已访问）。

所以你所要做的就是保留一个单独的标志，它只是在每次遍历时改变状态......

那么你的逻辑是

if ( visitedFlag ^ alternatingFlagStateOfTree )
{
    visitedFlag ^= 1;
}

基本上，alternatingFlagStateOfTree 仅用于指示是否访问了 true 或访问了 false 状态。每次运行交替，所以我们只是交换它们。

这完全消除了对 set()、所有内存开销等的需要，并且消除了在运行之间重置标志值的任何需要。

这种技术可以用于更复杂的状态，只要遍历的所有项目都有一致的结束状态。您只需进行一些数学运算即可重置标志值以将状态返回到基本状态。