![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 18. Поиск на графе. время выполнения поиска в глубину линейно зависит от размеров самого графа: если речь идет о насыщенном графе (число ребер которого пропорционально V2)
Как будет показано далее, все эти рассуждения применимы к любому алгоритму, для которого характерны несколько основных свойств поиска в глубину. Если алгоритм помечает каждую вершину и проверяет все вершины, инцидентные рассматриваемой вершине (и проделывает другую работу, на выполнение которой затрачивается время, ограниченное некоторой константой), то эти свойства характерны и для него. В более общей формулировке это звучит так: если время, затрачиваемое на просмотр каждой вершины, ограничено некоторой функцией f(V, E), то есть гарантия того, что время поиска в глубину пропорционально Е + f(V, E). В разделе 18.8 мы увидим, что поиск в глубину является одним из алгоритмов из семейства, которому свойственны эти характеристики; в главах 19—22 мы убедимся в том, что алгоритмы этого семейства служат основой достаточно большого числа программ, которые рассматриваются в данной книге. Большая часть изучаемых нами программ обработки графов представляет собой программы реализации АТД для некоторых конкретных задач, в рамках которых мы разрабатываем класс, выполняющий базовый поиск для вычисления структурированной информации в других векторах, проиндексированных именами вершин. Мы можем построить такой класс на основе программы 18.2 или, в более простых случаях, просто реализовать поиск повторно. Многие из построенных нами классов обработки графов обладают этими свойствами, поскольку, как привило, при выполнении поиска на графе мы получаем представление о его структуре. Обычно мы расширяем код функции поиска, которая выполняется, когда каждая вершина помечена, вместо того, чтобы работать с алгоритмом поиска более общего характера (например, с алгоритмом поиска, который вызывает некоторую специальную функцию каждый раз, когда встречается помеченная вершина) только из желания сделать программный код модульным и более компактным. Построение для клиентских программ механизма АТД более общего характера, обеспечивающего обработку всех вершин с помощью функций, предоставляемых самими клиентами, несомненно заслуживает всяческого внимания (см. упражнения 18.13 и 18.14). В разделах 18.5 и 18.6 мы проведем исследование многочисленных функций обработки графов, которые основаны на использовании алгоритма DFS. В разделах 18.5 и 18.6 мы рассмотрим другие реализации функции search и ряда других функций обработки графов, в основе которых лежат реализации этой функции. Хотя мы и не встроили этот уровень абстракции в наш программный код, мы, тем не менее, позаботимся о том, чтобы было понятно, какая основная стратегия поиска на графе лежит в основе разрабатываемого алгоритма. Например, мы применяем термин класс DFS для ссылки на любую реализацию, основанную на рекурсивной схеме поиска в глубину. Программы, определяющие класс поиска простого пути (программа 17.16) и класс основного леса (программа 18.3) могут служить примерами классов DFS.
|