Глава 19. Орграфы и ориентированные ациклические графы. булевых матриц? Ответ на данный вопрос может быть таким: рассматриваемый алгоритм транзитивного замыкания является оптимальным способом умножения некоторых

булевых матриц? Ответ на данный вопрос может быть таким: рассматриваемый алгоритм транзитивного замыкания является оптимальным способом умножения некоторых типов булевых матриц (число ненулевых элементов которых составляет O(V)). Нижняя грани­ца показывает, что мы не можем надеяться на то, что найдем такой алгоритм транзитив­ного замыкания, который выполняется за время, пропорциональное V² для всех оргра­фов, однако это не исключает возможности, что мы найдем алгоритмы, подобные рассматриваемому, которые работают быстрее на некоторых классах орграфов. Если эти графы суть именно те, которые и требуется обрабатывать, зависимость между транзитив­ным замыканием и умножением булевых матриц не будет иметь для нас особого значе­ния.

Методы, описанные в данном разделе, легко расширить с таким расчетом, чтобы они снабдили клиентские программы средством, позволяющим находить конкретные пути, соединяющие две вершины, путем отслеживания дерева поиска в соответствии с изложен­ным в разделе 17.8. Мы рассмотрим специальные реализации АТД этого вида в контек­сте более общих задач поиска кратчайших путей в главе 21.

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

В случае разреженных графов, транзитивные замыкания которых тоже разрежены, мы можем воспользоваться для вычисления замыканий реализацией, ориентированной на представление графа в виде списка смежных вершин, так что размер ее выхода пропор­ционален числу ребер в транзитивном замыкании. Естественно, это число служит нижней границей стоимости вычисления транзитивного замыкания, которое мы можем получить для различных типов орграфов, используя для этой цели различные алгоритмические тех­нологии (см. упражнения 19.64 и 19.65). Несмотря на наличие такой возможности, мы в общем случае полагаем, что результат транзитивного замыкания есть насыщенная матри­ца. В силу этого обстоятельства, мы можем воспользоваться такой реализацией, как DenseGRAPH, которая способна отвечать на запросы о достижимости, при этом мы рас­сматриваем алгоритмы транзитивного замыкания, вычисляющие матрицу транзитивного замыкания за время, пропорциональное К², как оптимальные, поскольку на их выпол­нение затрачивается время, пропорциональное размерам их выходов.

Таблица 19.1. Эмпирическое исследование алгоритмов транзитивного замыкания

В данной таблице показаны значения времени выполнения различных алгоритмов вычисления транзитивных замыканий случайных орграфов, как насыщенных, так и разреженных. Эти значения разительно отличаются друг от друга. Для всех алгоритмов, за исключением поиска в глубину на орграфе, представленном в виде списков смежных вершин, время выполнения возрастает в 8 раз при увеличении V в два раза. Этот факт подтверждает вывод о том, что по существу это время пропорционально V³. Поиск в глубину на орграфе, представленном в виде списков смежных вершин, требует для своего выполнения время, пропорциональное VE, что может служить объяснением того факта, что время выполнения этого алгоритма возрастает в примерно в 4 раза с увеличением V и Е в два раза каждого (разреженные графы), и примерно в 2 раза, когда мы увеличиваем Е в два раза (насыщенные графы) за исключением тех случаев, когда непроизводительные

Часть 5. Алгоритмы на графах

затраты, связанные с обходом списков, снижают производительность сильно насыщенных графов.

Обозначения:

W Алгоритм Уоршалла (раздел 19.3)

W* Усовершенствованный алгоритм Уоршалла (программа 19.3)

А Поиск в глубину, представление графа в виде матрицы смежности (программы 19.4 и 17.7)

L Поиск в глубину, представление графа в виде списков смежных вершин (программы 19.4 и 17.9)

Если такая матрица смежности симметрична, она эквивалентна неориентированному графу, благодаря чему поиск транзитивного замыкания становится эквивалентным поис­ку связных компонентов — транзитивное замыкание представляет собой объединение пол­ных графов в вершинах связных компонент (см. упражнение 19.48). Алгоритмы опреде­ления связности, которые мы изучали в разделе 18.5, эквивалентны вычислению абстрактного транзитивного замыкания для симметричных орграфов (неориентированных графов), требуют для своего выполнения время, пропорциональное V, и способны давать ответы на запросы о достижимости за постоянное время. Можем ли мы добиваться та­ких же успешных результатов в случае орграфов общего вида? Для каких типов оргра­фов можно вычислить транзитивное замыкание за линейное время? Чтобы ответить на эти вопросы нам придется изучить структуру орграфов более подробно, и в первую очередь — структуру графов DAG.

⇐ Предыдущая919293949596979899100Следующая ⇒