Лабораторная работа № 22 (к § 53) Поиск в глубину

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

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

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

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

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

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

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

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

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

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

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

Основные характеристики поиска в глубину

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

Разбор задач

Порядок посещения вершин

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

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

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

Проверка существования пути

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

1. Запустите обход из A и отметьте её посещённой.
2. При каждом переходе сравнивайте новую вершину с B. Если они совпали, путь существует, и поиск можно завершить.
3. Если цель не найдена, продолжайте возвраты и переходы к другим непосещённым соседям.
4. Если все достижимые вершины обработаны, а B не встретилась, пути из A в B нет.

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

Компоненты связности

Условие. Для неориентированного графа требуется найти группы вершин, соединённых путями внутри группы. Один запуск поиска в глубину из непосещённой вершины как раз собирает все вершины её компоненты.

1. Создайте общий массив меток и просмотрите вершины по порядку.
2. Если вершина уже отмечена, пропустите её; иначе начните из неё новый поиск.
3. Добавляйте в текущую группу стартовую вершину и каждую вершину, достигнутую рекурсивными переходами.
4. После завершения запуска выведите группу и продолжите просмотр, пока не будут отмечены все вершины.

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

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

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

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

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

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

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

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

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

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