Поиск в ширину (BFS) — это стандартный алгоритм для нахождения кратчайших путей в неориентированном графе, где расстояние измеряется как минимальное количество пройденных рёбер. Этот неориентированный граф можно интерпретировать как взвешенный граф, где каждое ребро имеет вес . Для графов с неравномерными весами рёбер обычно используются более общие алгоритмы, такие как алгоритм Дейкстры, которые работают за время или .
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
Однако, когда веса рёбер ограничены значениями или , мы можем оптимизировать решение до времени .
Понимание алгоритма 0-1 BFS включает в себя анализ алгоритма Дейкстры с учетом того, что каждый вес ребра равен либо , либо . В алгоритме Дейкстры расстояния между источником и другими вершинами в приоритетной очереди различаются не более чем на единицу. Это подразумевает, что для любой вершины в очереди выполняется неравенство .
Учитывая это свойство, если бы в очереди была вершина с , она была бы вставлена через другую вершину , где . Однако это невозможно, так как алгоритм Дейкстры обрабатывает вершины в порядке увеличения расстояния.
Следовательно, очередь в 0-1 BFS может быть организована следующим образом:
Эта более простая структура позволяет использовать двустороннюю очередь (deque) вместо приоритетной очереди. Вершины добавляются в начало deque, если соответствующее ребро имеет вес , или в конец, если вес ребра равен . Этот подход гарантирует, что deque остается отсортированным.
0-1 BFS использует двустороннюю очередь (deque) для управления вершинами во время обхода.
Инициализируйте все расстояния до вершин как бесконечные, кроме источника, который устанавливается в . Добавьте источник в deque.
Пока deque не пуст:
Извлеките вершину из начала.
Для каждой смежной вершины вершины :
Реализация 0-1 BFS на C++ с использованием deque выглядит следующим образом:
vector<int> d(n, INF);
// s — это источник.
d[s] = 0;
deque<int> q;
q.push_front(s);
while (!q.empty()) {
int v = q.front();
q.pop_front();
for (auto edge : adj[v]) {
int u = edge.first;
int w = edge.second;
if (d[v] + w < d[u]) {
d[u] = d[v] + w;
if (w == 1)
q.push_back(u);
else
q.push_front(u);
}
}
}