如何在C ++中跟踪BFS深度 [英] How to keep track of BFS depth in C++
问题描述
我想在2D数组上执行BFS，并且每个单元格都可以表示为 pair< int，int> 。我使用 queue< pair< int，int>> 来跟踪每个级别的单元格，但是我找不到跟踪深度的聪明方法。 （我不想定义另一个结构来记录每个级别的深度）
I want to do BFS on a 2D array, and each of the cell can be represented as pair<int,int>. I use queue<pair<int,int>> to keep track of cells at each level, but I find no clever way to keep track of the depth. (I don't want to define another struct to record the depth at each level)
这是Java中的解决方案。每个级别以 null 结尾，一旦看到 null ，我们便增加深度。
How to keep track of depth in breadth first search?
Here is a solution in Java. Each level is ended with null, and we increment the depth once we see null.
我想知道C ++中是否有类似的优雅解决方案。现在，我可以想到以下方法：
I am wondering if there's a similar elegant solution in C++. For now, I can think of the following ways:
1）计算单元格的数量（ push（） ）在每个级别，并在每个 pop（）之后递减计数。一旦 count == 0 ，增加深度。
1) count the number of cells(push()) at each level, and decrement the count after each pop(). Once count == 0, increase the depth.
2）使用两个 queue ，并在每个级别末尾用新的替换旧的。在每次迭代结束时增加深度。
2) use two queue and replace the old one with the new one at the end of each level. Increase the depth at the end of each iteration.
3）可能存储指向 pair< int，int> 在队列中，并使用 NULL 分隔级别？
3) maybe stores a pointer to pair<int,int> in the queue and use NULL to separate levels?
推荐答案
（ 1）可以工作，但是设置count = queue.size（）并在每次弹出时将其递减会更好/更容易。当它变为0时，增加深度并再次设置count = queue.size（）。
(1) can work, but it's better/easier to set count=queue.size(), and decrement it each time you pop. When it gets to 0, increase the depth and set count=queue.size() again.
（2）可以正常工作。使用std :: swap切换队列。这通常是我做的，因为我喜欢外面的 for（int depth = 0;！newnodes.empty（）; ++ depth），您也可以使用矢量代替真正的队列，因为您没有在同一个对象上推送和弹出。第二级循环只是一个向量的迭代。
(2) works fine. Use std::swap to switch queues. This is what I usually do, because I like the outer for(int depth=0; !newnodes.empty(); ++depth) you can also use vectors instead of real queues, because you're not pushing and popping on the same object. The 2nd level loop is just an iteration through a vector.
（3）有用，但是很浪费。其他类型的标记值也可以使用，但我认为上述（1）在所有情况下都比这更好。
(3) works, but it's quite wasteful. Other kinds of marker values can work, but I think the (1) above is better than this in all cases.
在您更喜欢使用std：的情况下： deque而不是两个向量，我喜欢这样写：
In cases where you prefer to use a std::deque instead of two vectors, I like to write it like this:
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）非常相似，但是我得到了不错的深度循环，并在剩余的，我们可以避免对 queue.empty（）
... which is pretty much like my (1) above, but I get my nice depth loop and by writing the loop condition on remaining, we can avoid any other inner loop checks to queue.empty()
这篇关于如何在C ++中跟踪BFS深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
