Информатика / Алгоритмы и анализ данных

Поиск в ширину: кратчайший путь по числу рёбер

Поиск в ширину, или BFS, находит минимальное число переходов от стартовой вершины в невзвешенном графе. Очередь обрабатывает вершины слоями, поэтому первое открытие уже задаёт кратчайшее расстояние.

Опубликовано: 20 октября 2026 г.Обновлено: 20 октября 2026 г.

Формула

d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u

Схема Слои BFS от A

Каждое ребро стоит один переход

Обозначения

$s$: стартовая вершина, идентификатор
$u,v$: соседние вершины; переход u → v разрешён, идентификатор
$d(v)$: минимальное число рёбер от s до v, число переходов
$V,E$: число вершин и рёбер графа, количество

Условия применения

Каждое ребро имеет одинаковую стоимость перехода, обычно единицу. В ориентированном графе обходят только разрешённые направления. Вершину помечают при добавлении в очередь, а не после обработки; начальная вершина получает расстояние ноль.

Ограничения

BFS минимизирует число рёбер, а не сумму разных весов. Он не гарантирует самый короткий маршрут в километрах или по времени, если переходы неодинаковы. Недостижимой вершине не присваивают ноль: её расстояние остаётся бесконечным или явно неопределённым.

Подробное объяснение

Из старта сначала открываются все соседи на расстоянии одного ребра, затем их ещё не открытые соседи на расстоянии двух рёбер. Очередь FIFO сохраняет этот порядок: раньше добавленная вершина обрабатывается раньше. В этом состоит отличие от обхода в глубину.

Когда из u впервые открывается v, к известному пути до u добавляют одно ребро. Если бы существовал более короткий путь до v, его предпоследняя вершина принадлежала бы более раннему слою и успела открыть v раньше. Это противоречит первому открытию и доказывает минимальность расстояния.

Для восстановления самого пути одного массива расстояний недостаточно. При открытии записывают предшественника: из какой вершины пришли. Затем идут от цели назад к старту и разворачивают цепочку. При нескольких кратчайших путях порядок соседей влияет на выбранную цепочку, но не на её длину.

Пометка при добавлении в очередь не допускает многократного помещения одной вершины через разных соседей. При списках смежности каждая вершина и каждое ребро рассматриваются ограниченное число раз, поэтому время составляет O(V+E), а дополнительная память — O(V).

В ориентированной сети достижимость асимметрична. Даже если из A можно попасть в B за два шага, обратного пути может не быть. Перед расчётом следует также решить, что считается вершиной состояния: иногда номер остановки без направления или времени ещё не описывает допустимые переходы.

Как пользоваться формулой

Пометьте старт, задайте ему расстояние ноль и добавьте его в пустую очередь; для прочих вершин отметьте отсутствие пути.
Извлеките первую вершину и рассмотрите разрешённых соседей; каждому ещё не открытому задайте расстояние на единицу больше.
Сразу пометьте нового соседа и сохраните его предшественника, затем добавьте в конец очереди для последующей обработки.
После опустошения очереди восстановите маршрут по предшественникам; недостигнутые вершины сохраните отдельно от нулевого расстояния.

Историческая справка

Поиск в ширину относится к классическим алгоритмам обхода графов, сформировавшимся в вычислительной традиции XX века. Его естественная постановка — распространять достижимость от источника последовательными слоями, не перечисляя все возможные маршруты. В современном учебном изложении Седжвика и Уэйна этот принцип связан с очередью и массивом предшественников. Такое разделение позволяет одинаково описывать лабиринт, сеть связей и абстрактный граф состояний. История конкретных применений шире одной программной реализации: идея слоёв, доказательство кратчайшего расстояния и выбор структуры данных — разные части метода. Здесь не устанавливается единственный изобретатель обхода. Представлена стандартная схема, чьи свойства можно проверить по учебному коду и прямому доказательству через порядок слоёв.

Историческая линия формулы

BFS приведён как классический алгоритм поиска в ширину без персональной атрибуции первенства. Реализация Седжвика и Уэйна используется как учебный источник очереди, расстояний и предшественников; авторство учебного кода не приравнивается к изобретению идеи.

Пример

В неориентированном графе есть рёбра A–B, A–C, B–D, C–D и D–E. Начинаем из A: d(A) = 0, очередь [A]. После A открыты B и C с расстояниями 1; очередь [B,C]. Обработка B открывает D с расстоянием 2 и предшественником B. Обработка C не добавляет D повторно, поскольку он уже помечен. Из D открывается E с расстоянием 3. Если B перечислялся раньше C, восстановленный путь A–B–D–E содержит три ребра. Маршрут A–C–D–E столь же короток. Проверка: в E входит только D, а D не является соседом A, поэтому пути из одного или двух рёбер не существует. Ответ измеряется числом переходов; длины и времена отдельных рёбер в этих данных не заданы.

Частая ошибка

Не заменяйте очередь стеком, сохраняя утверждение о кратчайшем пути. Не сравнивайте маршруты с разными весами только по числу рёбер. Не помечайте вершину лишь при извлечении, иначе в очередь попадут дубликаты. Не принимайте отсутствие пути за расстояние ноль. Не забудьте развернуть восстановленную цепочку от цели к старту.

Практика

Задачи с решением

Цепочка с коротким ребром

Условие. Даны неориентированные рёбра S–A, A–B, B–T, S–T. Найдите расстояние от S до B.

Решение. Слой 1 содержит A и T. Из A открывается B на слое 2. Также существует путь S–T–B длины 2. Прямого ребра S–B нет.

Ответ. 2 ребра.

Ориентированный маршрут

Условие. Есть дуги A→B, B→C и D→C. Найдите расстояния из A до C и D.

Решение. Из A открываем B с расстоянием 1, затем C с расстоянием 2. Дуга D→C не разрешает переход C→D, поэтому D недостижима.

Ответ. До C — 2; до D пути нет.

Дополнительные источники

https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/BreadthFirstPaths.html
https://algs4.cs.princeton.edu/lectures/keynote/41UndirectedGraphs.pdf

Связанные формулы

Информатика

Алгоритм Дейкстры: релаксация и кратчайшие расстояния

$d(v)\leftarrow\min\bigl(d(v),d(u)+w(u,v)\bigr),\qquad w(u,v)\geq0$

Алгоритм Дейкстры находит кратчайшие пути от одной вершины при неотрицательных весах рёбер. На каждом шаге окончательно выбирается ещё не выбранная вершина с минимальной текущей меткой.

Информатика

Алгоритм Беллмана — Форда: путь с отрицательными весами

$d_k(v)=\min\left(d_{k-1}(v),\min_{(u,v)\in E}\{d_{k-1}(u)+w(u,v)\}\right)$

Алгоритм Беллмана — Форда уточняет расстояния последовательными проходами по рёбрам. Он допускает отрицательные веса и позволяет обнаружить отрицательный цикл, достижимый из выбранного источника.

Информатика

Алгоритм Флойда — Уоршелла: пути между всеми парами

$d_{ij}^{(k)}=\min\left(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\right)$

Алгоритм Флойда — Уоршелла находит расстояния между всеми парами вершин, последовательно разрешая новые промежуточные вершины. Его основа — сравнение прямого известного маршрута с маршрутом через очередную вершину.

Информатика

Алгоритм Краскала: вес минимального остовного дерева

$T\in\underset{\text{остовные деревья }S}{\operatorname{arg\,min}}\sum_{e\in S}w(e),\qquad |T|=V-1$

Алгоритм Краскала строит минимальное остовное дерево неориентированного графа: перебирает рёбра по возрастанию веса и принимает только те, которые соединяют разные текущие компоненты.