Информатика · объяснение и практика
Почему поиск в ширину находит кратчайший путь в невзвешенном графе
Находим минимальное число рёбер от стартовой вершины поиском в ширину, сохраняем предшественников для маршрута и объясняем, почему взвешенный путь требует другой модели.

В теме Графы и маршруты · Учебная карта
Главная мысль
BFS обходит достижимые вершины слоями с помощью FIFO-очереди. В невзвешенном графе первый найденный слой даёт минимальное число рёбер от старта. Для произвольных весов минимальное число рёбер не равно минимальной стоимости.
Как очередь создаёт последовательные слои
Пусть из А идут рёбра к Б и В, из Б — к Г, из В — к Д, из Д — к Г. Сначала расстояние А равно 0, в очередь добавлены Б и В с расстоянием 1. Затем Б обнаруживает Г с расстоянием 2. Поздний путь через В и Д имел бы три ребра и уже не улучшает минимальный слой Г.
Причина в FIFO: все вершины слоя 1 обрабатываются раньше вершин слоя 2. Чтобы дойти до ещё не открытой вершины короче, нужен был бы предшественник более раннего слоя, который уже проверен. Такой порядок и доказывает кратчайшее число переходов. Стек LIFO уходит вдоль одной ветви и этой гарантии сам по себе не даёт.
Когда отмечать вершину и как восстановить путь
Вершину обычно помечают обнаруженной при добавлении в очередь. Тогда одна вершина не попадает туда многократно от разных соседей, а её первый предшественник фиксирует короткий путь. В примере для Г сохраняется Б, для Б — А. Обратный проход Г→Б→А разворачивают и получают маршрут А→Б→Г.
Если кратчайших путей несколько, выбранный зависит от порядка обхода соседей. Длина при этом остаётся минимальной. Не нужно обещать единственный маршрут, если граф допускает разные. Если цель недостижима, её расстояние оставляют специальным признаком отсутствия, а не нулём: ноль уже принадлежит старту и не означает «не найдено».
Пример
В невзвешенном графе есть прямое ребро А–В и путь А–Б –Г–В. Какую длину найдёт BFS от А до В?
Одно ребро. Более длинный обход может существовать, но не меняет минимальный слой прямого соседа.
Какие границы у гарантии
Если прямое ребро имеет стоимость 100, а путь из трёх рёбер по 1 стоит 3, BFS всё равно предпочитает один переход по числу рёбер. Это правильный ответ для невзвешенной задачи, но неверный для минимальной стоимости. При одинаковых положительных весах число рёбер пропорционально цене; при разных нужны соответствующие алгоритмы.
Списки смежности позволяют обработать каждую достижимую вершину и её рёбра за O(V+E) для всего обхода при подходящих операциях очереди. Матрица может потребовать просмотра всех возможных соседей. Проверяют ориентированность графа, существование стартовой вершины и направление рёбер. Поиск от одного старта не объявляет все остальные компоненты исследованными: недостижимые вершины остаются вне его результата.
От чтения к действию
А теперь — вы
Частые вопросы
BFS всегда минимизирует сумму весов?
Нет. Он минимизирует число рёбер в невзвешенной задаче; разные веса требуют другого алгоритма.
Если кратчайших путей несколько, результат ошибочен?
Нет. Один из них может выбираться порядком соседей, при сохранении минимальной длины.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему алгоритму Дейкстры нужны неотрицательные веса
Находим кратчайшие стоимости при неотрицательных весах, различаем предварительную оценку и окончательную вершину и показываем точную причину ограничения на отрицательные рёбра.
Открыть темуКогда список смежности выгоднее матрицы
Сравниваем список смежности и матрицу по памяти и операциям, сохраняем направление и вес рёбер и выбираем структуру под разреженность и требуемые запросы.
Открыть тему