Сначала ближайшие вершины, потом следующие. Разберём, как очередь помогает пройти граф по слоям и найти путь с наименьшим числом рёбер.
Очередь
Расстояния
C++ и Python
Практика Codeforces
Волна от начальной вершины
Вершины — точки графа, рёбра — связи между ними. BFS (Breadth-First Search) сначала находит всех соседей старта. Затем — вершины, до которых нужны два перехода, после них — три и так далее.
Число переходов от старта до вершины запишем в d[v]. У старта d[s] = 0. У недостижимой вершины оставим -1.
Слои от вершины 1: {1}, затем {2, 3}, затем {4, 5}, затем {6}.
Обычный BFS находит кратчайший путь по числу рёбер. Это подходит для графа без весов или с одинаковой положительной стоимостью каждого перехода.
Очередь сохраняет порядок
Кто пришёл первым, тот выходит первым. Новую вершину кладём в конец очереди, следующую для обработки берём из начала. Поэтому вершины следующего слоя ждут, пока будут обработаны вершины текущего.
Поставь d[s] = 0 и добавь старт в очередь.
Достань из начала очереди вершину v.
Для каждого её соседа u с d[u] = -1 поставь d[u] = d[v] + 1 и добавь u в конец.
Повторяй, пока очередь не опустеет.
Отмечай вершину обнаруженной при добавлении в очередь. Иначе два разных соседа могут добавить одну и ту же вершину несколько раз.
Очередь в примере. Соседей выбираем по возрастанию номеров.
Что сделали
Обнаружили
Очередь после действия
Добавили старт
1
1
Обработали 1
2, 3
2, 3
Обработали 2
4, 5
3, 4, 5
Обработали 3
Никого: 5 уже обнаружена
4, 5
Обработали 4
6
5, 6
Обработали 5
Никого: 6 уже обнаружена
6
Обработали 6
Никого
Пусто
Порядок обработки: 1, 2, 3, 4, 5, 6. Если переставить соседей в списках, порядок внутри слоя может измениться. Расстояния останутся прежними.
Один алгоритм на двух языках
Ввод: n m s — число вершин, рёбер и старт, затем m пар концов рёбер. Вершины нумеруются от 1 до n, граф неориентированный. Программа выводит расстояния от старта до всех вершин; -1 означает, что пути нет.
Ввод
6 7 1
1 2
1 3
2 4
2 5
3 5
4 6
5 6
Вывод
0 1 1 2 2 3
C++ · queue
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n, m, s;
cin >> n >> m >> s;
vector<vector<int>> graph(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int> d(n + 1, -1);
vector<int> parent(n + 1, -1);
queue<int> q;
d[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : graph[v]) {
if (d[u] == -1) {
d[u] = d[v] + 1;
parent[u] = v;
q.push(u);
}
}
}
for (int v = 1; v <= n; v++) {
if (v > 1) cout << ' ';
cout << d[v];
}
cout << '\n';
}
Python · deque
from collections import deque
n, m, s = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
d = [-1] * (n + 1)
parent = [-1] * (n + 1)
q = deque([s])
d[s] = 0
while q:
v = q.popleft()
for u in graph[v]:
if d[u] == -1:
d[u] = d[v] + 1
parent[u] = v
q.append(u)
print(*d[1:])
В Python используем deque: извлечение слева через popleft() не сдвигает остальные элементы, как list.pop(0).
Как получить сам путь?
При обнаружении вершины u сохраняем parent[u] = v — откуда пришли. Для цели 6 в примере получится цепочка 6 → 4 → 2 → 1. Развернём её: 1 → 2 → 4 → 6. Это три ребра. Если d[t] = -1, путь восстанавливать нельзя.
Почему BFS находит минимум и как быстро работает?
Очередь сначала отдаёт вершины с расстоянием 0, затем 1, затем 2 и так далее. Когда впервые обнаружили u из вершины с расстоянием k, путь длины k + 1 уже найден, а более короткого нет: предыдущие слои мы проверили. При списках соседей весь обход занимает O(n + m); помимо хранения графа нужны массивы и очередь объёмом O(n).
Проверь понимание
Ответы и пояснения
Очередь станет [3, 4]: новый элемент добавляется в конец. До вершины 6 нужны 3 перехода. Вершину отмечаем при добавлении, чтобы другие соседи не добавили её снова.
Где BFS пригодится
В лабиринте вершинами становятся свободные клетки, а рёбрами — разрешённые шаги. В задаче с числами вершина — текущее число, ребро — одно разрешённое действие. Граф не всегда нужно строить заранее: соседей можно вычислять во время обхода.
Один запуск посещает только вершины, достижимые из выбранного старта. Для подсчёта всех компонент в неориентированном графе запускай BFS из каждой ещё не обнаруженной вершины.
Проверь условия задачи: если разные переходы имеют разную стоимость, обычный BFS не гарантирует минимальную суммарную стоимость. Для таких задач нужны другие алгоритмы.
Задачи Codeforces
Сначала реши учебный пример выше, затем попробуй Two Buttons. Остальные задачи добавляют моделирование графа, работу с компонентами или хранение клеток. Рейтинги — значения Codeforces, а не оценки для школьных классов.
Граф чисел · 1400
520B — Две кнопки (Two Buttons)
На экране положительное число n. Одна кнопка удваивает его, другая уменьшает на 1. Число должно оставаться положительным. Найди минимум нажатий, чтобы получить m.
Ввод: различные n и m, оба от 1 до 10000. Вывод: минимальное число нажатий. Пример: 4 6 → 2, потому что 4 → 3 → 6.
Идея BFS
Соседи числа x — 2x и x − 1, если они в допустимом диапазоне. Каждое нажатие — одно ребро. Для поиска достаточно положительных чисел не больше 2 · max(n, m): удваивать уже слишком большое число незачем.
Сотрудники знают некоторые языки и могут общаться напрямую или через переводчиков. Обучение одного сотрудника одному языку стоит 1. Какова минимальная стоимость, чтобы все смогли общаться друг с другом?
Ввод:2 ≤ n, m ≤ 100 — сотрудники и языки; для каждого сотрудника дано количество известных языков и их номера от 1 до m. Список может быть пуст. Вывод: минимальная стоимость.
Идея BFS
Соедини сотрудников, у которых есть общий язык, и найди компоненты очередью. Если хотя бы один язык уже известен, достаточно k − 1 обучений для k компонент. Отдельно проверь случай, когда все списки пусты: тогда учить нужно всех n сотрудников.
На карте . — вода, * — суша. Водные клетки соединены общей стороной. Озеро — целая связная область воды, которая не касается границы карты. Засыпь минимум водных клеток, чтобы осталось ровно k озёр.
Ввод:1 ≤ n, m ≤ 50, 0 ≤ k ≤ 50, затем карта; исходно озёр не меньше k. Вывод: число засыпанных клеток и изменённая карта.
Идея BFS
Очередью собери каждую водную область, запомни её клетки и проверь касание границы. Среди озёр засыпь самые маленькие, пока их не останется k.
Между каждой парой городов есть либо железная дорога, либо автомобильная; оба вида двусторонние. Поезд и автобус одновременно отправляются из 1 в n. Один переход занимает час; остановок по пути нет. Они не должны одновременно прибывать в один город, кроме конечного; в конечном разрешено ждать. Найди минимальное время прибытия более медленного транспорта.
Ввод:2 ≤ n ≤ 400 и список m железных дорог; остальные пары городов соединены автомобильными дорогами. Вывод: минимальное время или -1, если хотя бы один транспорт не может добраться.
Идея BFS
Один транспорт может сразу перейти из 1 в n: между ними есть ровно один вид связи. Для другого найди кратчайший путь BFS в его графе. Первый уже в конечном городе, поэтому ограничение о встречах не мешает.
Король может за ход перейти в любую из восьми соседних клеток, включая диагональные. На огромной доске разрешены лишь некоторые клетки. Найди минимальное число ходов от заданного старта до цели, двигаясь только по разрешённым клеткам.
Ввод: старт и цель, затем отрезки разрешённых клеток вида строка, первый столбец, последний столбец. Координаты до 10⁹, число отрезков и сумма их длин не больше 100000. Старт и цель разрешены и различны. Вывод: число ходов или -1.
Идея BFS
Храни разрешённые пары координат в множестве, а не в огромной матрице. BFS рассматривает восемь соседей каждой клетки. Отмечай клетки при добавлении в очередь.