Глава 18. Поиск на графе. время выполнения поиска в глубину линейно зависит от размеров самого графа: если речь идет о насыщенном графе (число ребер которого пропорционально V2)

время выполнения поиска в глубину линейно зависит от размеров самого графа: если речь идет о насыщенном графе (число ребер которого пропорционально V²), то любое представление дает этот результат; если речь идет о разреженном графе, то мы предпо­читаем пользоваться представлением в виде списков смежных вершин. В самом деле, обычно мы полагаем, что время выполнения поиска в глубину линейно зависит от Е. Это утверждение формально неверно, если для представления разреженных графов не исполь­зуются матрицы смежности, или для исключительно разреженных графов, для которых Е«V и большая часть вершин изолирована; однако мы обычно избегаем второй ситу­ации за счет удаления изолированных вершин (см. упражнение 17.34).

Как будет показано далее, все эти рассуждения применимы к любому алгоритму, для которого характерны несколько основных свойств поиска в глубину. Если алгоритм по­мечает каждую вершину и проверяет все вершины, инцидентные рассматриваемой вер­шине (и проделывает другую работу, на выполнение которой затрачивается время, огра­ниченное некоторой константой), то эти свойства характерны и для него. В более общей формулировке это звучит так: если время, затрачиваемое на просмотр каждой вершины, ограничено некоторой функцией 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.