![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Поиск в глубину
Наши интерес к исследованиям Тремо объясняется тем обстоятельством, что этот метод непосредственно приводит к классической рекурсивной функции обхода графов: посетив конкретную вершину, мы помечаем ее специальной меткой, свидетельствующей о том, что она посещена, затем, в режиме рекурсии, мы посещаем все смежные с нею вершины, которые еще не были помечены. Этот метод, краткий анализ которого проводился в главах 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 для непосещенных вершин). Для каждого ребра графа отводится две строки, по одной на каждое направление. Величина отступа определяет уровень рекурсии.
|