"Информатика (базовый и углублённый уровень)", Гейн А.Г., Сенокосов А.И.
Обход графа — способ последовательно исследовать его вершины, не обрабатывая одну и ту же вершину снова. Он помогает проверить, какие вершины достижимы, найти путь и исследовать структуру сети. Два основных способа обхода — поиск в глубину и поиск в ширину. В первом случае алгоритм продвигается по одному пути, во втором — рассматривает вершины слоями, начиная с ближайших к исходной. Для полного обхода связного графа оба способа посещают все его вершины.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Связный граф — граф, в котором из любой вершины можно попасть в любую другую по рёбрам. Значит, между любой парой вершин есть путь. Это свойство позволяет начать обход с одной вершины и в итоге добраться до всех остальных.
Обход графа — последовательное посещение его вершин по заданным правилам с отметкой уже посещённых вершин. Отметку обычно хранят в виде списка или множества. Она помогает алгоритму понимать, какие вершины уже обработаны.
Поиск в глубину — обход, при котором из текущей вершины переходят к ещё не посещённому соседу и продолжают идти как можно дальше. Если продолжать путь нельзя, алгоритм возвращается к предыдущей вершине. Такой способ удобен, когда нужно исследовать направления графа одно за другим.
Поиск в ширину — обход, при котором сначала посещают соседей исходной вершины, затем соседей этих вершин и так далее. Вершины рассматриваются по уровням удалённости от начала. Поэтому этот способ полезен для поиска кратчайших путей в невзвешенном графе.
Посещённые вершины отмечают, потому что в графе могут быть циклы: из одной вершины можно пройти по рёбрам и вернуться в неё же. Без отметок алгоритм не отличит уже обработанную вершину от новой и может повторять одни и те же действия. Кроме того, одну вершину часто обнаруживают из нескольких соседних. Отметка предотвращает и бесконечный обход, и лишние повторные обработки.
Обход начинается с выбора исходной вершины. Её сразу помечают посещённой, затем рассматривают её соседей — вершины, соединённые с ней ребром. Правило выбора следующего соседа зависит от способа обхода и принятого порядка перебора. Пометка при обнаружении важна: тогда один и тот же сосед не будет несколько раз добавлен в структуру данных.
Поиск в глубину можно реализовать с помощью стека — структуры, где последним добавляют и первым извлекают элемент, — или рекурсии, то есть вызова алгоритмом самого себя. Каждый переход к новому соседу продолжает текущую ветвь, поэтому обход углубляется. Когда продолжать некуда, алгоритм возвращается к вершине, из которой пришёл, и проверяет другие варианты. Так постепенно исследуются все ветви, достижимые из начала.
Поиск в ширину использует очередь: в ней первым извлекают элемент, который добавили раньше. Обнаруженных соседей помещают в конец очереди, а следующую вершину берут из её начала. Благодаря такому порядку сначала обрабатываются вершины на расстоянии одного ребра от исходной, затем на расстоянии двух и далее. Если расстоянием считать число рёбер, первый найденный путь до вершины будет кратчайшим.
Порядок обхода может меняться, если по-разному перебирать соседей одной вершины. Например, сначала можно рассматривать вершину B, а можно C; тогда изменится последовательность посещений. Однако в связном графе полный обход не пропускает вершины, поскольку от исходной вершины существует путь к каждой. При правильной отметке каждую вершину обрабатывают ровно один раз, хотя порядок этой обработки не обязан быть единственным.
Сравнивайте алгоритмы по тому, как они выбирают следующую вершину и какую структуру данных используют. Это помогает не путать их даже в графе, где оба обхода в итоге посещают одни и те же вершины. Для поиска кратчайшего пути в невзвешенном графе особенно важен порядок обработки BFS.
| Характеристика | Поиск в глубину | Поиск в ширину |
|---|---|---|
| Основной принцип | Углубляется по одному пути | Обходит вершины по уровням |
| Используемая структура данных | Стек или рекурсия | Очередь |
| Порядок посещения вершин | Сначала дальние вершины выбранной ветви | Сначала ближайшие к исходной вершине |
| Что происходит, если новых соседей нет | Возврат к предыдущей вершине | Извлечение следующей вершины из очереди |
| Для каких задач особенно удобен | Исследование структуры графа и его ветвей | Поиск кратчайшего пути по числу рёбер |
Для первых двух задач возьмём один и тот же связный граф со списками соседей: A — B, C; B — A, D, E; C — A, F; D — B; E — B, F; F — C, E. Соседей рассматриваем в алфавитном порядке. Это условие нужно, чтобы у примера был однозначный порядок обхода. Исходная вершина — A.
Задача 1. Выписать порядок обхода в глубину. Здесь нужно идти к первому доступному непосещённому соседу, а не выбирать вершину, которая кажется ближе к началу. Когда путь закончится, возвращаемся назад и ищем следующий выход. Записываем вершину только при первом обнаружении.
Ответ: A, B, D, E, F, C. Вершины D и C оказываются в разных частях последовательности, потому что глубина выбирает одну ветвь до конца, прежде чем вернуться к другой.
Задача 2. Выписать порядок обхода в ширину и очередь после обработки каждой вершины. Помещаем A в очередь и отмечаем её. Обнаруженных непосещённых соседей добавляем в конец очереди по алфавиту, а уже обнаруженные вершины повторно не добавляем.
Ответ: порядок посещения — A, B, C, D, E, F. Очередь каждый раз сохраняет обнаруженные, но ещё не обработанные вершины, поэтому сначала заканчивается уровень соседей A, а затем рассматривается следующий уровень.
Задача 3. Найти кратчайшее расстояние от A до каждой вершины и путь до F. Запускаем поиск в ширину, задаём расстояние до A равным 0, а её предшественника оставляем пустым. Когда впервые обнаруживаем соседа вершины, записываем расстояние на единицу больше и сохраняем вершину, из которой пришли.
Ответ: расстояния: A — 0, B — 1, C — 1, D — 2, E — 2, F — 2. Кратчайший путь от A до F: A — C — F, его длина равна двум рёбрам.
Не отмечать вершину при обнаружении. Тогда её могут несколько раз добавить в очередь или стек, особенно если соседи соединены циклом. Ошибку допускают, откладывая пометку до обработки вершины. Проверка: помечайте вершину сразу, когда впервые добавляете её для дальнейшей обработки.
Считать порядок обхода единственным. При нескольких соседях можно выбрать их в разной последовательности, поэтому изменится и весь маршрут алгоритма. Часто путают один возможный результат с единственно верным. Проверяйте, задан ли порядок перебора соседей, и указывайте его при записи ответа.
Путать стек и очередь. Стек поддерживает углубление и возврат, а очередь обрабатывает вершины по мере обнаружения; замена одной структуры другой меняет принцип обхода. Ошибка возникает, если ориентироваться только на название алгоритма. Проверьте правило извлечения: для глубины нужен последний добавленный элемент, для ширины — первый.
Считать, что поиск в глубину всегда находит кратчайший путь. Он может сначала уйти далеко по длинной ветви, не проверяя более короткий маршрут. Это заблуждение возникает из-за того, что алгоритм действительно находит путь, но не обязательно минимальный. Для кратчайшего пути по числу рёбер в невзвешенном графе используйте поиск в ширину.
Для работы с обходом нужно знать, что такое вершины, рёбра и пути, а также уметь читать списки смежности: в них для каждой вершины перечислены её соседи. Обходы применяют, чтобы выяснить, достижима ли одна вершина из другой, и искать маршруты в сетях. Они служат основой для алгоритмов поиска компонент связности и кратчайших путей. Поэтому понимание очереди, стека и отметок пригодится и в других задачах на графы.
Зачем отмечать вершины, которые уже посетили?
Отметка не позволяет снова обрабатывать вершину и добавлять её в очередь или стек. Это особенно важно в графах с циклами: без отметок алгоритм может ходить по замкнутому маршруту бесконечно.
Почему один и тот же граф можно обходить в разном порядке?
У вершины могут быть несколько непосещённых соседей, и алгоритм вправе рассмотреть их в разном порядке. Если заранее установить правило, например проверять соседей по алфавиту, результат станет определённым.
Чем поиск в глубину отличается от поиска в ширину?
Поиск в глубину старается пройти как можно дальше по одному пути, а при необходимости возвращается к предыдущей вершине. Поиск в ширину сначала рассматривает всех ближайших соседей, а затем вершины на следующем расстоянии; для него используют очередь.
Как понять, когда при поиске в глубину нужно возвращаться назад?
Возвращаться нужно, когда у текущей вершины не осталось непосещённых соседей. Алгоритм переходит к предыдущей вершине и проверяет, есть ли у неё другие ещё не исследованные направления.
Какой алгоритм использовать, чтобы найти кратчайший путь в невзвешенном графе?
Для кратчайшего пути по числу рёбер применяют поиск в ширину. Он исследует вершины по уровням расстояния, поэтому впервые обнаруживает каждую вершину по пути с минимальным числом рёбер.
§ 53. Алгоритмы обхода связного графа
