c++ - 如何在 C++ 中跟踪 BFS 深度

Question

我想对一个2D数组进行BFS，每个单元格可以表示为pair<int,int> 。我用queue<pair<int,int>>跟踪每个级别的细胞，但我发现没有聪明的方法来跟踪深度。 (我不想定义另一个结构体来记录每个级别的深度)

How to keep track of depth in breadth first search?这是Java中的解决方案。每个级别都以null结束。 ，一旦看到 null，我们就增加深度.

我想知道 C++ 中是否有类似的优雅解决方案。目前我能想到的办法有以下几种:

1) 计算每个级别的单元格数量 ( push() )，并在每个 pop() 之后递减计数。一次count == 0 ，增加深度。

2) 使用两个 queue并在每一关结束时用新的替换旧的。在每次迭代结束时增加深度。

3) 可能存储一个指向 pair<int,int> 的指针在队列中并使用 NULL划分级别？

Answer 1

(1) 可以工作，但最好/更简单地设置 count=queue.size()，并在每次弹出时递减它。当它达到0时，增加深度并再次设置count=queue.size()。

(2) 工作正常。使用 std::swap 来切换队列。这是我通常做的，因为我喜欢外在for(int depth=0; !newnodes.empty(); ++depth)您还可以使用 vector 而不是真正的队列，因为您不是在同一个对象上推送和弹出。第二级循环只是 vector 的迭代。

(3) 有效，但相当浪费。其他类型的标记值也可以工作，但我认为上面的 (1) 在所有情况下都比这个更好。

如果您更喜欢使用 std::deque 而不是两个 vector ，我喜欢这样写:

queue.push_back(root);
for (int depth=0; !queue.empty(); ++depth)
{
    for (size_t remaining=queue.size(); remaining>0; --remaining)
    {
        auto item = queue.pop_front();
        //.... queue.push_back(...), etc.
    }
}

...这与上面的 (1) 非常相似，但是我通过在 remaining 上编写循环条件得到了很好的深度循环。 ，我们可以避免对 queue.empty() 进行任何其他内部循环检查。