Достижимость в графе DAG

Мы завершим наше изучение графов DAG рассмотрением задачи вычисления транзи­тивного замыкания DAG. Можно ли разработать такие алгоритмы для графов DAG, ко­торые обладают большей эффективностью, чем алгоритмы для обобщенных орграфов, которые исследовались в разделе 19.3?

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

Когда мы используем стандартный поиск в глубину для топологической сортировки (см. программу 19.7), мы можем повысить ее производительность для некоторых видов графов DAG, как показывает программа 19.9. Поскольку в графах DAG нет циклов, то ни в каких поисках в глубину нет обратных ребер. Что еще важнее, как поперечные, так и прямые ребра ведут в узлы, в которых DFS завершен. Чтобы воспользоваться этим об­стоятельством, мы разработаем рекурсивную функцию, вычисляющую все вершины, до­стижимые из заданной исходной вершины, тем не менее (как это характерно для поис­ка в глубину), мы не производим рекурсивных вызовов для вершин, для которых множество достижимых вершин уже было вычислено. В этом случае достижимые верши-

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

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

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

Свойство 19.13. С помощью динамического про­граммирования и поиска в глубину мы можем обеспе­чить постоянное время ответа на запрос на абст­рактное транзитивное замыкание графа DAG, при этом на предварительную обработку (для подготов­ки вычисления транзитивного замыкания) затрачи­вается пространство памяти, пропорциональное V², и время, пропорциональное V² + VX, где X — это число поперечных ребер в лесе DFS.

Доказательство: Доказательство непосредственно следует по индукции из рекурсивной функции, используемой в программе 19.9. Мы посещаем вершины в обратном топологическом порядке. Каждое ребро указывает на вершину, для которой мы уже вычислили множество всех достижимых вершин, в силу этого обстоятельства мы можем вычислить множество достижимых вершин для любой вершины путем слияния множеств дости­жимых вершин, ассоциированных с вершинами назначения каждого ребра. Завершает это слияние

РИСУНОК 19.27. ТРАНЗИТИВНОЕ ЗАМЫКАНИЕ ГРАФА DAG

Рассматриваемая последователь­ность векторов-строк есть транзи­тивное замыкание графа DAG, показанного на рис. 19.21. Эти строки были построены во время выполнения обратной топологической сортировки, вычисленной как завершающее действие рекурсивной функции DFS (см. программу 19.9). Каждая строка является результа­том логической операции or (или) над строками смежных вершин, которые заранее появились в рассматриваемом списке в результате предшествовав­ших вычислений. Например, чтобы вычислить строку для вершины 0, мы выполняем логическую or над строка­ми для вершин 5, 2, 1 и б (и подста­новку 1 вместо самой вершины 0), поскольку ребра 0-5, 0-2, 0-1 и 0-6 приводят нас из вершины 0 в любую вершину, которая достижима их каждой из этих вершин. Мы можем игнорировать прямые ребра, поскольку они не добавляют новой информации. Например, мы игнорируем ребро, ведущее из 0 в 3, поскольку вершины, достижимые из 3 уже фигурируют в строке, соответствующей 2.

Глава 19. Орграфы и ориентированные ациклические графы

выполнение операции логического ог над конкретными строками матрицы смежнос­ти. Мы осуществляем доступ к строке размера V каждого древесного ребра и каждо­го поперечного ребра. В рассматриваемом случае обратные ребра отсутствуют, и мы можем игнорировать прямые ребра, поскольку мы определили все вершины, в кото­рые они приводят, когда проводили обработку предшественников обоих вершин этих ребер на более ранних стадиях поиска. ■

Программа 19.9. Транзитивное замыкание графа DAG_____________________________

Конструктор в этом классе вычисляет транзитивное замыкание DAG при помощи одного поиска в глубину. Он вычисляет в рекурсивном режиме вершины, достижимые из каждой вершины из числа достижимых вершин ее потомков в дереве DFS.

template < class tcDag, class Dag> class dagTC { tcDag T; const Dag & D; int cnt;

vector< int> pre; void tcR(int w) {

pre[w] = cnt++;

typename Dag:: adjIterator A(D, w); for (int t = A.beg();! A.end(); t = A.nxt())

{