Алгоритмы с нуля
Кратчайший путь в невзвешенном графе с BFS
В прошлом уроке ты выучил что BFS исследует граф слой за слоем используя очередь, и что первый раз когда он достигает вершину, он достигает её по наименьшему числу рёбер. Это последнее предложение — полный алгоритм кратчайшего пути, спрятанный внутри обхода. Если ты также помнишь из какой вершины ты пришёл, ты не просто узнаёшь расстояние — ты можешь восстановить настоящий маршрут, шаг за шагом. Этот урок превращает обычный BFS в машину кратчайших путей для невзвешенных графов: веди массив dist[] и отображение parent[] по ходу, потом иди по parent[] назад чтобы напечатать конкретный путь. Одно предупреждение наперёд: этот трюк работает только когда каждое ребро считается одинаково. Поставь веса на рёбра (стоимость 1 здесь, стоимость 7 там) и BFS тихо даёт неправильный ответ — вот где Dijkstra берёт верх в следующем уроке.
После этого урока ты можешь запустить BFS заполняя массив dist[] (расстояние в рёбрах от источника к каждой достижимой вершине) и отображение parent[] (вершина из которой ты пришёл). Ты понимаешь почему это правильно: BFS извлекает вершины в порядке неубывающего расстояния, так что первый раз когда ты достигаешь вершину это по пути с наименьшим числом рёбер. Ты можешь восстановить конкретный кратчайший путь идя по parent[] назад от цели к источнику и развернув список. Ты знаешь границу техники: она валидна только для невзвешенных (или единично-взвешенных) графов; взвешенные рёбра ломают её и требуют Dijkstra. Ты можешь расширить BFS на несколько источников сразу (многоисточниковый BFS) засеяв очередь несколькими стартами на расстоянии 0. Ты знаешь что стоимость остаётся O(V + E) по времени и O(V) по памяти. Следующий урок: алгоритм Dijkstra для взвешенных графов.
Вопрос кратчайшего пути
В невзвешенном графе, длина пути это просто число рёбер на нём. Кратчайший путь от источника к цели это путь с наименьшим числом рёбер. Мы хотим две вещи для каждой достижимой вершины: её расстояние от источника, и конкретный маршрут к ней.
Почему обычный BFS уже решает это
BFS процессирует вершины в порядке неубывающего расстояния: он опустошает уровень 0 (источник, расстояние 0), потом весь уровень 1 (расстояние 1), потом уровень 2, и так далее. Из-за этого порядка, самый первый раз когда BFS достигает вершину, он достиг её по наименьшему возможному числу рёбер. Нет более короткого маршрута, ждущего быть найденным позже, потому что любой более поздний маршрут обнаруживается на равном или большем расстоянии. Так что момент когда мы добавляем вершину это момент когда мы узнаём её настоящее кратчайшее расстояние.
Два массива чтобы записать ответ
Мы добавляем два кусочка учёта к обычному BFS:
- dist[v] — расстояние (число рёбер) от источника к v. Установи
dist[u] = dist[v] + 1когда мы впервые достигаем u из v. - parent[u] — вершина из которой мы пришли когда впервые достигли u. Это хлебная крошка, что позволяет нам идти назад к источнику.
Оба заполняются в один и тот же момент: когда мы впервые видим непосещённого соседа u процессируя v.
Пример графа
Неориентированный, невзвешенный граф с 6 вершинами:
Список смежности:
A: [B, C]
B: [A, D, E]
C: [A, F]
D: [B]
E: [B, F]
F: [C, E]
Визуально:
A
/ \
B C
/ \ \
D E---FЕсть два маршрута от A к F: A-C-F (2 ребра) и A-B-E-F (3 ребра). BFS должен найти 2-рёберный.
Трассировка BFS с dist и parent (источник = A)
Отмечай вершину когда ты её добавляешь (отметка это “уже имеет значение dist”).
Init: queue = [A] dist[A]=0, parent[A]=null
Pop A. neighbors B, C (both new)
dist[B]=1 parent[B]=A enqueue B
dist[C]=1 parent[C]=A enqueue C
queue = [B, C]
Pop B. neighbors A(seen), D(new), E(new)
dist[D]=2 parent[D]=B enqueue D
dist[E]=2 parent[E]=B enqueue E
queue = [C, D, E]
Pop C. neighbors A(seen), F(new)
dist[F]=2 parent[F]=C enqueue F
queue = [D, E, F]
Pop D. neighbors B(seen) queue = [E, F]
Pop E. neighbors B(seen), F(seen) queue = [F]
Pop F. neighbors C(seen), E(seen) queue = []
Done.
dist: A=0 B=1 C=1 D=2 E=2 F=2
parent: A=null B=A C=A D=B E=B F=CЗаметь что F получила parent=C (не E), потому что C была извлечена раньше E, так что F была впервые достигнута из C. Это ровно более короткий маршрут.
Восстановление конкретного пути A -> F
Иди по parent[] назад от цели, потом разверни:
start at F path = [F] parent[F]=C
go to C path = [F, C] parent[C]=A
go to A path = [F, C, A] parent[A]=null -> stop
reverse path = [A, C, F]Восстановленный кратчайший путь это A -> C -> F, длина 2 ребра, совпадает с dist[F]=2.
Ловушка взвешенного графа
Предположим та же форма, но ребро A-C стоит 10 пока A-B, B-E, E-F каждое стоит 1. Теперь самый дешёвый маршрут это A-B-E-F (стоимость 3), но BFS всё равно сообщает A-C-F как “кратчайший” потому что он считает рёбра, не стоимость. BFS слеп к весам. Исправление это другой алгоритм — Dijkstra — что всегда расширяет границу с наименьшей стоимостью следующей. Кратчайшие пути BFS правильны только когда каждое ребро имеет один вес (что мы можем считать за 1).
BFS что заполняет dist[] и parent[]
1
function bfsShortestPath(source, adj) {
2
const dist = {}; // distance in edges from source
3
const parent = {}; // vertex we arrived from
4
const queue = [source];
5
6
dist[source] = 0; // source is 0 edges from itself
7
parent[source] = null; // source has no parent
8
9
while (queue.length > 0) {
10
const v = queue.shift(); // dequeue (FIFO)
11
for (const u of adj[v]) {
12
if (!(u in dist)) { // first time we reach u
13
dist[u] = dist[v] + 1; // one edge farther than v
14
parent[u] = v; // remember the breadcrumb
15
queue.push(u); // enqueue (mark-on-enqueue)
16
}
17
}
18
}
19
20
return { dist, parent };
21
}
- L2 dist служит и маркером посещения: 'u in dist' значит u уже была достигнута.
- L3 parent[u] записывает предшественника на кратчайшем пути к u.
- L6 Источник находится на расстоянии 0 от самого себя.
- L7 У источника нет предшественника; null останавливает обратный обход позже.
- L10 shift() удаляет из начала очереди: FIFO, ключ к порядку по расстоянию.
- L12 Проверка 'in dist', не отдельное множество, так что мы никогда не достигаем одну вершину дважды.
- L13 Первое прибытие = кратчайшее расстояние, так что dist[v]+1 окончательно для u.
- L14 Установи parent в тот же момент когда устанавливаем dist.
- L15 Отметь при добавлении (дав ей dist) чтобы она никогда не добавлялась снова.
Восстановление конкретного пути
1
function reconstructPath(target, parent) {
2
const path = [];
3
let cur = target;
4
while (cur !== null && cur !== undefined) {
5
path.push(cur); // collect from target back to source
6
cur = parent[cur]; // step to the predecessor
7
}
8
path.reverse(); // flip so it reads source -> target
9
return path;
10
}
- L4 null значит мы достигли источника; undefined значит цель недостижима.
- L5 Мы собираем вершины в обратном порядке: цель сначала.
- L6 Следуй по цепи хлебных крошек на один шаг к источнику.
- L8 Разверни чтобы получить естественный порядок источник-к-цели.
Запуск на примере графа
1
adj = { A:[B,C], B:[A,D,E], C:[A,F], D:[B], E:[B,F], F:[C,E] };
2
dist[A]=0; parent[A]=null;
3
queue = [A];
Сложность по времени: O(V + E)
Это BFS с двумя дешёвыми дополнительными записями на вершину, так что стоимость не меняется. Каждая вершина добавляется ровно раз (проверка u in dist это гарантирует), и когда извлекается мы сканируем все её инцидентные рёбра. Установка dist[u] и parent[u] это O(1) каждая. Суммарно по всему запуску: V добавлений + E сканирований рёбер = O(V + E).
Восстановление пути это O(L), где L это длина пути, что самое большее V вершин. Это доминируется самим BFS, так что итог остаётся O(V + E).
Сложность по памяти: O(V)
Отображение dist[] хранит до V записей: O(V). Отображение parent[] хранит до V записей: O(V). Очередь удерживает самое большее V вершин одновременно: O(V). Итого: O(V).
Почему первое прибытие это кратчайшее
BFS извлекает в порядке неубывающего расстояния. Конкретно, каждая вершина добавленная из вершины на расстоянии d получает расстояние d+1, и все вершины на расстоянии d извлекаются перед любой вершиной на расстоянии d+1. Так что когда вершина впервые достигается, более короткого неисследованного маршрута не может существовать — любой другой маршрут находится на том же расстоянии или позже.
Distances grow monotonically across the queue:
queue: [ d=1, d=1, d=2, d=2, d=2 ] (never [d=2, d=1])Почему веса ломают это
A --1-- B --1-- E --1-- F total cost 3
A --10- C --1-- F total cost 11
BFS counts edges, not cost:
A->C->F = 2 edges -> BFS calls this "shortest"
A->B->E->F = 3 edges
But by COST, A->B->E->F (3) beats A->C->F (11).BFS сообщает путь с наименьшим числом рёбер, что неправильно когда рёбра имеют разные веса. Используй Dijkstra для взвешенных графов.
Почему первый раз когда BFS достигает вершину соответствует её кратчайшему расстоянию от источника?
Какова роль отображения parent[] (предшественник) в кратчайших путях BFS?
Ты восстанавливаешь путь следуя по parent[] назад от цели. В каком порядке выходят вершины, и что это исправляет?
Граф имеет рёбра с разными положительными весами и ты хочешь путь минимальной стоимости. Правилен ли обычный BFS?
Многоисточниковый BFS находит, для каждой вершины, расстояние до ближайшего из нескольких источников. Как ты это настраиваешь?
В графе урока (A:[B,C], B:[A,D,E], C:[A,F], D:[B], E:[B,F], F:[C,E]), какое dist[F], кратчайшее число рёбер от A к F?
Почему это работает
Почему dist[] служит и множеством посещённых. Нам никогда не нужна отдельная структура посещённых. Тест u in dist истинен ровно когда u уже была достигнута и добавлена. Переиспользование dist[] держит учёт в одном месте: вершина “посещена” в момент когда она получает расстояние, что также момент когда мы устанавливаем её parent. Меньше массивов, меньше шансов забыть обновить один из них.
Частая ошибка
Установка dist или parent на более позднем посещении. Вершина может быть соседом нескольких других, так что ты можешь встретить её снова после того как она уже в dist[]. Не перезаписывай dist[u] или parent[u] на этих более поздних встречах — первое присваивание это кратчайшее, а более позднее ребро только когда-либо предлагает равный или более длинный маршрут. Защищай каждое обновление через if (!(u in dist)).
Граничные случаи
Недостижимые цели. Если цель в другой компоненте чем источник, BFS никогда не присваивает ей расстояние, так что dist[target] это undefined и parent[target] тоже undefined. Цикл восстановления останавливается сразу же (cur это undefined), возвращая список что не начинается с источника. Проверь сначала target in dist, и сообщи “нет пути” если он отсутствует.
Ещё практика
Кратчайшие пути на сетке. Лабиринт или сетка это граф в маскировке: каждая открытая клетка это вершина, и смежные открытые клетки (вверх/вниз/влево/вправо) соединены единично-взвешенными рёбрами. BFS из стартовой клетки даёт путь с наименьшим числом шагов к выходу, и parent[] восстанавливает маршрут. Это повседневное использование BFS для кратчайших путей без весов в играх и поиске пути на однородной местности.
Объясни как BFS вычисляет кратчайшие пути без весов, для чего dist[] и parent[], как восстановить конкретный путь, и когда эта техника перестаёт быть правильной.
BFS это уже алгоритм кратчайшего пути для невзвешенных графов: он извлекает вершины в порядке неубывающего расстояния, так что первый раз когда он достигает вершину это по пути с наименьшим числом рёбер.
Учёт: веди dist[v] (рёбра от источника) и parent[v] (вершина из которой ты пришёл). Установи оба в момент когда ты впервые добавляешь v — и никогда не перезаписывай их позже.
Восстанови путь: иди по parent[] назад от цели к источнику, потом разверни. Длина равна dist[target].
Расширение: многоисточниковый BFS засеивает очередь несколькими источниками на расстоянии 0 и находит расстояние каждой вершины до её ближайшего источника за один проход.
Время: O(V + E). Память: O(V).
Граница: это работает только когда каждое ребро считается одинаково. Разные веса рёбер ломают BFS, потому что он минимизирует число рёбер, не стоимость. Следующий урок: алгоритм Dijkstra — кратчайшие пути на взвешенных графах.