Лабораторная работа № 23 (к § 53) Поиск в ширину

Определения и обозначения

Поиск в ширину — алгоритм обхода графа, который посещает вершины послойно: сначала ближайшие к стартовой, затем более удалённые. Граф состоит из вершин и соединяющих их рёбер, а стартовая вершина задаёт точку начала поиска. Такой порядок нужен, когда требуется узнать, какие вершины достижимы и сколько шагов до них.

Очередь — структура данных, в которую элементы добавляют в конец, а извлекают из начала, то есть по принципу «первым пришёл — первым вышел». В поиске в ширину в неё помещают обнаруженные вершины. Очередь помогает не перепрыгивать через целый уровень и сохранять порядок обработки.

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

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

Как это устроено

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

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

Отметку посещения ставят при добавлении вершины в очередь, а не при её извлечении. Между этими действиями соседние вершины могут встретить её снова; без отметки они добавят её повторно. Это создаёт лишнюю работу, а также может усложнить правильный учёт расстояний и предков. Если же пометить вершину сразу, алгоритм рассматривает её только один раз.

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

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

Основные элементы алгоритма поиска в ширину

Таблица помогает понять, какие данные нужны для конкретной задачи: для проверки достижимости достаточно отметок посещения, а для расстояний нужен соответствующий массив. Если требуется вывести маршрут, заранее добавьте массив предков. Выберите условие остановки по вопросу задачи: найти одну цель или обработать всю достижимую часть графа.

Разбор задач

Порядок обхода и расстояния

Условие. Неориентированный граф задан списками соседей: A соединена с B и C, B — с A и D, C — с A и D и E, D — с B и C, E — с C. Стартовая вершина — A. Требуется записать порядок посещения и расстояние каждой вершины от старта. Соседей будем просматривать в указанном порядке.

1. Ставим A отметку посещения, задаём расстояние 0 и помещаем её в очередь: [A]. Это единственная известная вершина, поэтому обработка начинается с неё.
2. Извлекаем A и проверяем B, затем C. Обе вершины новые: отмечаем их, задаём расстояние 1 и добавляем в очередь, которая становится [B, C]. Так формируется первый слой.
3. Извлекаем B. Его сосед A уже отмечен, а D ещё нет, поэтому задаём D расстояние 2 и добавляем его в конец: очередь [C, D]. A повторно не добавляется, потому что была отмечена при первом обнаружении.
4. Извлекаем C. A уже посещена, D уже находится в очереди, а E новая. Добавляем E с расстоянием 2; теперь очередь [D, E]. Это показывает, почему отметка нужна и для вершин, ожидающих обработки.
5. Извлекаем D и E. Все их соседи уже отмечены, поэтому новых вершин не появляется и очередь становится пустой. Пустая очередь означает, что достижимая от A часть графа обработана полностью.

Ответ. Порядок посещения: A, B, C, D, E. Расстояния: A — 0, B — 1, C — 1, D — 2, E — 2. При другом порядке просмотра соседей порядок внутри одного уровня может измениться, но минимальные расстояния останутся теми же.

Кратчайшие расстояния до всех вершин

Условие. В невзвешенном графе нужно найти кратчайшее расстояние от вершины S до всех остальных вершин. Список смежности позволяет просматривать только рёбра, выходящие из текущей вершины. Требуется также отличить недостижимые вершины от тех, для которых путь существует.

1. Создаём массив расстояний и отмечаем все значения как неизвестные, например −1. Для S задаём 0, отмечаем её посещённой и помещаем в очередь: ноль указывает, что до старта путь не содержит рёбер.
2. Пока очередь не пуста, извлекаем вершину u и просматриваем её соседей v. Если v ещё не посещена, присваиваем ей расстояние dist[u] + 1 и отмечаем её сразу, чтобы другие соседи не добавили её повторно.
3. Добавляем v в очередь и продолжаем обработку. Поскольку очередь сохраняет послойный порядок, к моменту обнаружения v все вершины с меньшим расстоянием уже рассмотрены, а значит, найденное значение минимально.
4. Когда очередь опустела, значения, отличные от −1, являются кратчайшими расстояниями для всех достижимых вершин. Если осталось −1, вершина недостижима из S: алгоритм не нашёл до неё ни одного пути.

Ответ. Запускаем поиск в ширину, присваивая каждой новой вершине расстояние текущей плюс 1. Массив расстояний после завершения поиска содержит кратчайшие расстояния в рёбрах до всех достижимых вершин, а отметка −1 указывает на недостижимость.

Кратчайший маршрут между помещениями

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

1. Запускаем поиск из A и создаём массив предков. Для A предка нет; при обнаружении каждой новой вершины записываем, из какой вершины в неё пришли.
2. Пока E не обнаружена, извлекаем вершины из очереди и добавляем новых соседей. Обнаружив E, можно закончить поиск: из-за послойной обработки путь до неё уже имеет минимальное число рёбер.
3. Начинаем с E и по массиву предков идём назад. Например, если для E предок C, для C — A, получаем обратную последовательность E, C, A.
4. Разворачиваем последовательность и проверяем, что она начинается в A и заканчивается в E. Число рёбер равно числу вершин в записи минус один; если у цели нет предка и она не совпадает со стартом, маршрута нет.

Ответ. Массив расстояний даёт длину кратчайшего маршрута, а массив предков — его последовательность. В примере восстановленный маршрут A, C, E содержит два прохода; проверка соседних пар подтверждает, что каждый шаг соответствует ребру графа.

Типичные ошибки

Если отмечать вершину посещённой только после извлечения, несколько соседей могут добавить её в очередь одновременно. Так часто поступают, путая обнаружение вершины с её обработкой, но это вызывает дублирование работы. Помечайте вершину сразу при добавлении и проверьте, что каждую вершину очередь получает не более одного раза.

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

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

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

Связь с другими темами

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

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

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

Что запомнить

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