Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






19.9. Еще раз о транзитивном замыкании

Объединяя результаты двух предыдущих разделов, мы можем разработать алгоритм решения задачи вычисления абстрактно-транзитивного замыкания для орграфов, который хотя и не вводит никаких усовершенствований в решение для худшего случая, основан­ное на поиске в глубину, но в то же время обеспечивает оптимальное решение во мно­гих других случаях.

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

Для реализации абстрактного транзитивного замыкания мы выполним предваритель­ную обработку графа в следующем объеме:

■ Найдем его сильные компоненты.

■ Построим его базовый DAG.

■ Вычислим транзитивное замыкание базового DAG.

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

Если в нашем распоряжении имеется вектор, индексированный именами вершин с сильными компонентами орграфа, построение представления его базового DAGв виде матрицы смежности не представляет трудностей. Вершины графа DAGсуть номера ком­понент орграфа. Для каждого ребра s-t исходного графа мы просто устанавливаем D->adj[sc[s]][sc[t]]в 1.Нам пришлось бы решать проблему дубликатов ребер в базовом DAG, если бы мы воспользовались представлением графа в виде списков смежных вер­шин, в то же время в матрице смежности дубликаты ребер просто соответствуют установ­ке элемента матрицы в 1, который уже имел значение 1. Это небольшой нюанс приоб­ретает важное значение, поскольку потенциально в рассматриваемом приложении число дубликатов ребер огромно (по отношению к размеру базового DAG).



Свойство 19.17.Заданы две вершины s и t в орграфе D, пусть sc(s) и sc(t) — соответству­ющие им вершины в базовом DAG К орграфа D. Тогда t достижима из s в D тогда и только тогда, когда sc(t) достижима из sc(s) в К.



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


Этот простой факт следует из определений. В частности, это свойство предполагает, что действует соглашение, согласно которому вершина достижима сама из себя (все вершины имеют петли). Если эти вершины находятся в одной и той же сильной ком­поненте (sc(s) = sc(t)), то они взаимно достижимы. ■

Мы определим, достижима ли вершина t из заданной вершины s тем же способом, ка­ким мы строили базовый DAG: воспользуемся вектором, индексированным именами вер­шин, вычисленным с помощью алгоритма сильных компонент, чтобы получить числа sc(s) и sc(t) (за постоянное время), которые мы будем рассматривать как индексы абстракт­ных вершин (abstract vertex) базового DAG. Их использование в качестве индексов для транзитивного замыкания базового DAG даст искомый результат.

Программа 19,13. Транзитивное замыкание на основе сильных компонент________________

Данный класс реализует интерфейс (абстрактного) транзитивного замыкания орграфов путем вычисления сильных компонентов (с использованием, скажем, программы 19.11), базового DAG и транзитивного замыкания базового DAG (с использованием программы 19.9). Он предполагает, что класс SC обладает общедоступной функцией-элементом ID, которая возвращает индекс сильной компоненты (из массива id) для любой заданной вершины. Эти числа суть индексы вершин в базовом DAG. Вершина t орграфа достижима из вершины s тогда и только тогда, когда ID(t) достижима из ID(s) в базовом DAG.



template <class 6raph> class TC { const Graph &G; DenseGRAPH *K; dagTOCDenseGRAPH, Graph> *Ktc; SC<Graph> *Gsc; public:

TC (const Graph &G) : G(G) {

Gsc = new SC<Graph>(G) ;

К = new DenseGRAPH(Gsc->count(), true); for (int v = 0; v < G.V(); v++) { typename Graph::adjIterator A(G, v) ;

for (int t = A.beg(); !A.end(); t = A.nxt())

K->insert(Edge(Gsc->ID(v), Gsc->ID(t))); } Ktc = new dagTC<CDenseGRAPH, Graph>(*K) ;

}

~TC() { delete K; delete Ktc; delete Gsc; } bool reachable (int v, int w)

{ return Ktc->reachable(Gsc->ID(v), Gsc->ID(w));} };

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

Свойство 19.18.Мы можем поддерживать постоянное время запроса АТД абстрактно­го транзитивного замыкания орграфа при затратах пространства памяти, пропорциональ­ных V + v2, и времени, пропорциональных Е + v2 + vx, на предварительную обработку (на вычисление транзитивного замыкания); здесь v есть число вершин в базовом DAG, ах — число поперечных ребер в его лесе DFS. Доказательство: Непосредственно следует из свойства 19.13. ■



mylektsii.ru - Мои Лекции - 2015-2018 год. (0.008 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал