Как работает 0-1 BFS на деке для графа с рёбрами весом 0 и 1?
В задаче веса рёбер только 0 или 1 (например, проход по клетке бесплатно, а смена направления стоит 1). Дейкстра проходит, но хочется быстрее — слышал про «0-1 BFS на деке». В чём идея и почему это O(V + E)?
2 ответа
Идея: вместо кучи используем дек (deque). Ребро веса 0 → вершину кладём в начало дека (тот же «слой»), ребро веса 1 → в конец (следующий слой). Так дек всегда содержит вершины не более чем двух соседних значений расстояния, и порядок извлечения сохраняет монотонность — как у Дейкстры, но без log.
const int INF = 1e9;
vector<int> dist(n, INF);
deque<int> dq;
dist[s] = 0; dq.push_front(s);
while (!dq.empty()) {
int v = dq.front(); dq.pop_front();
for (auto [u, w] : g[v]) { // w in {0, 1}
if (dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
if (w == 0) dq.push_front(u);
else dq.push_back(u);
}
}
}
Сложность O(V + E) по времени, O(V) по памяти — каждое ребро обрабатывается O(1) раз.
Важно: как и в Дейкстре, вершина может попасть в дек несколько раз, поэтому при извлечении полезно проверять актуальность через сравнение расстояния (или хранить флаг done). Без проверки ответ верный, но возможны лишние операции. Также 0-1 BFS — частный случай д𝑘-BFS: если веса 0..k, можно завести k+1 очередей (dial's algorithm) и работать за O(V·k + E).