Как отслеживать глубину BFS в C++

Question

Я хочу сделать BFS на 2D-массиве, и каждая ячейка может быть представлена ​​как pair<int,int>. Я использую queue<pair<int,int>> для отслеживания ячеек на каждом уровне, но я не нашел умного способа отслеживать глубину. (Я не хочу определять другую структуру для записи глубины на каждом уровне)

How to keep track of depth in breadth first search? Вот решение на Java. Каждый уровень заканчивается null, и мы увеличиваем глубину, как только видим null.

Мне интересно, есть ли аналогичное элегантное решение на C++. На данный момент я могу думать о следующих путях: 0)

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), вы также можете использовать векторы вместо реальных очередей, потому что вы не нажимаете и не выскакиваете на один и тот же объект. Цикл 2-го уровня - это просто итерация через вектор.

(3) работает, но это довольно расточительно. Другие виды значений маркеров могут работать, но я думаю, что (1) выше, чем это во всех случаях.

В тех случаях, когда вы предпочитаете использовать зЬй :: вместо дека двух векторов, я хотел бы написать это следующим образом:

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

Answer 2

Решение, подобное по духу, вставлять нуль в очередь, состоит в том, чтобы просто вставить значение дозорного значения, которое невозможно выполнить как ячейку. Например. pair<numeric_limits<int>::max(), 0>