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

Question

我想对一个二维数组做BFS，每个单元格可以表示为pair<int,int>。我使用 queue<pair<int,int>> 来跟踪每个级别的单元格，但我发现没有聪明的方法来跟踪深度。（我不想定义另一个结构来记录每个级别的深度）

这是 Java 中的解决方案。每个级别都以 null 结束，一旦看到 null，我们就会增加深度。

我想知道在 C++ 中是否有类似的优雅解决方案。目前，我可以想到以下方法：

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

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

3) 也许在队列中存储指向 pair<int,int> 的指针并使用 NULL 来分隔级别？

Answer 1

在本质上类似于将空值插入队列的解决方案是仅插入一个不可能作为单元出现的标记值。例如。 pair<numeric_limits<int>::max(), 0>

Answer 2

(1)可以，但是设置count=queue.size()是better/easier，每次pop的时候减1。当它到达0时，增加深度并再次设置count=queue.size()。

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

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

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

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()

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

How to keep track of BFS depth in C++

c++

algorithm

breadth-first-search