Главная » Java, Структуры данных и алгоритмы » Транзитивное замыкание

0

Рассмотрим еще один способ вычисления транзитивного замыкания диграфа. Пусть б будет диграфом из п узлов и т путей. Будем вычислять транзитивное замыкание диграфа серией циклов. Инициируем б0 = б

и в произвольном порядке пронумеруем узлы в б как vi, V2, …, vn. Затем вычисляем первый цикл. В общем случае на шаге к создается диграф бк, начиная с бк = 6к_{ и добавляя направленный путь (v/,vy), если диграф бкА содержит оба пути   и (v^vy). Таким образом, получаем простое

правило, выраженное приведенным ниже утверждением.

Утверждение 12.11. Для / = 1, …, п в диграфе Gk тогда и только тогда имеется путь (v,,vy), когда в диграфе существует направленный путь от v, до Vj, если расположенные между ними узлы (при наличии таковых) будут входить в множество {vi, v^}. В частности, Gn равен G\ транзитивному замыканию диграфа G.

Из утверждения 12.11 вытекает простой алгоритм вычисления транзитивного замыкания диграфа <5, в основу которого положена серия описанных выше циклов. Данный алгоритм получил известность как алгоритм Флойда-Уоршалла, и его псевдокод приведен во фрагменте кода 12.10. С помощью этого псевдокода легко проанализировать время выполнения алгоритма Флойда-Уоршалла, поскольку структура данных, представляющая G, поддерживает выполнение методов areAdjacent и insertDirectedEdge за 0(1) времени. Основной цикл выполняется п раз, а внутренний цикл обрабатывает каждую из 0(п2) пар узлов, выполняя для каждой пары вычислительные операции с постоянным временем. Таким образом, общее время выполнения алгоритма Флойда-Уоршалла составляет 0(я3).

Алгоритм FloydWarshall(G):

Input: диграф G из п узлов.

Output: транзитивное замыкание G* диграфа G.

Пусть vb v2, vn будет произвольной нумерацией узлов диграфа G , Go <~ G

for к <- 1 to п do

Gk Gk_i

for каждого /’, у в {1, п} при / * j и /, ] * к do if узлы (vit vk) и (vk, vj) входят в Gk_^ then

добавить узел (vh vj) к Gk (если такого еще нет)

return Gn

Фрагмент кода 12.10. Псевдокод алгоритма Флойда-Уоршалла. Алгоритм вычисляет транзитивное замыкание G* диграфа G, вычисляя по возрастающей серию диграфов G0, Gv Gn, где k = 1, …, п

Это описание является всего лишь примером алгоритмической проектной модели, известной как динамическое программирование (см. п. 11.5.2). Из этого описания и анализа следует нижеприведенное утверждение.

Утверждение 12.12. Пусть G будет диграфом из п узлов и представлен структурой данных, поддерживающей поиск и обновление информации списка смежности за 0(1) времени. Тогда алгоритм Флойда-Уоршалла вычисляет транзитивное замыкание G* диграфа G за 0(п3) времени.

Пример выполнения алгоритма Флойда-Уоршалла приведен на рис. 12.10.

Рис. 12.10. Последовательность диграфов, вычисляемых алгоритмом Флойда-Уоршалла: (а) исходный диграф G = G0 и нумерация узлов; (Ь) диграф <5,; (с) G2\ (d) G3; (е) G4; (0 Gs. Заметьте, что G5 = G6 =Gr Поскольку в ди- графе Gk_{ имеются пути (v^v^) и (v^vy), но отсутствует путь (v/,vy-), то на рисунке пути  и (v^vj) показаны линиями с точечным штри-

\ > хбм, а путь (vi,vj) — линией с длинным штрихом

Производительность алгоритма Флойда-Уоршалла

\ *

Время выполнения алгоритма Флойда-Уоршалла может оказаться большим, чем время DFS из каждого узла направленного графа, но оно будет зависеть от типа структуры, используемой для представления графа. Если граф представлен матрицей смежности, то выполнение DFS-ме- тода в направленном графе G займет 0(п2) времени. Таким образом, выполнение DFS п раз занимает 0{пг) времени, что ничем не лучше разового выполнения алгоритма Флойда-Уоршалла. Если же граф представлен структурой списка смежности, то для вычисления транзитивного замыкания выполнение DFS-алгоритма п раз займет 0(п(п + т)) времени. Но даже в этом случае, если граф будет насыщенным, то есть имеет 0(я2) пу- ;тей, то все равно потребуется 0{пг) времени, причем гораздо сложнее разового применения алгоритма Флойда-Уоршалла. Единственным случаем, когда повторное обращение к DFS-методу предпочтительнее, является ненасыщенный граф, представленный структурой списка смежности.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии