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