Поиск в глубину

Наши интерес к исследованиям Тремо объясняется тем об­стоятельством, что этот метод непосредственно приводит к классической рекурсивной функции обхода графов: посетив конкретную вершину, мы помечаем ее специальной меткой, свидетельствующей о том, что она посещена, затем, в режиме рекурсии, мы посещаем все смежные с нею вершины, кото­рые еще не были помечены. Этот метод, краткий анализ ко­торого проводился в главах 3 и 5 и который использовался для решения задачи нахождения путей в разделе 17.7, носит назва­ние метода поиска в глубину (DFS — depth-first search). Это один из наиболее важных алгоритмов, с которыми доведется стол­кнуться. Метод DFS обманчиво прост, поскольку в его осно­ве лежит знакомая идея и его реализация не вызывает трудно­стей; фактически это очень гибкий и мощный алгоритм, который применяется для решения множества трудных задач обработки графов.

Программа 18.1 представляет класс DFS, который посеща­ет все вершины и исследует все ребра связного графа. Подоб­но функциям поиска простого пути, которые рассматривались в разделе 17.7, он базируется на рекурсивной функции и по­зволяет поддерживать приватный вектор, в котором отмечают­ся пройденные вершины. В этой программной реализации ord представляет собой вектор целых чисел, в котором вершины записываются в порядке их посещения. Рисунок 18.5 отража­ет трассировку, которая показывает, в каком порядке про­грамма 18.1 производит обход ребер и вершин для примера, показанного на рис. 18.2 и 18.3 (см. также и рис. 18.17); в рас-

РИСУНОК 18.5. ТРАССИРОВКА DFS

Эта трассировка показы­вает, в каком порядке алгоритм поиска в глубину проверяет ребра и вершины графа, представленного в виде матрицы смежности и соответствующего примеру, изображенному на рис. 18.2 и 18.3 (вверху), и отслеживает содержимое вектора ord (справа) по мере продвижения поиска (звездочки означают -1 для непосещенных вершин). Для каждого ребра графа отводится две строки, по одной на каждое направле­ние. Величина отступа определяет уровень рекурсии.