Главная » Java, Структуры данных и алгоритмы » Направленные ацикличные графы

0

Направленные графы, не’имеющие направленных циклов, встречаются во многих приложениях. Подобный тип диграфа принято называть направленным ацикличным графом (directed acyclic graph), или, для краткости, DAG. Такие графы применяются:

•        при наследовании между классами в Java-nporpaMMax;

•      выполнении йредварительных условий прохождения дисциплин при получении степени;

•        планировании этапов выполнения заданий проекта.

Пример 12.8. Для удобства управления большой проект обычно разбивают на несколько заданий. Задания редко бывают независимы друг от друга, поскольку между ними существуют внутренние связи (например, при проектировании дома задача покупки гвоздей непосредственным образом предшествует задаче покрытия крЫши дранкой, при которой эти гвозди применяются). Следовательно, планирование последовательности выполнения каждого из заданий не может быть цикличным (например, чтобы получить работу, требуется опыт работы, необходимый для этой должности). Планирование этапов проекта предполагает определенные ограничения порядка выполнения рабЬт. А именно, если согласно техническому заданию, этап а) должен быть выполнен до начала выполнения этапа б), то этап а) должен предшествовать этапу б). Таким образом, если смоделировать план выполнения работ как узлы направленного графа и провести путь от v до w при необходимости исполнения задания v прежде задания wi имеем/дело*с направленным щдиедичным графом.

Допустим, G — диграф из п узлов. Топологическим порядком G будет порядок узлов v\, vn, при котором для каждого пути (vi,vj) выполняется условие / < у. То есть топологическим порядком диграфа G будет порядок, при котором обход узлов выполняется в возрастающем порядке (см. рис. 12.11). Заметим, что диграф G может иметь более одного топологического порядка.

Рис. 12.11. Два топологических порядка одного и того же ацикличного диграфа

Утверждение 12.13. В диграфе G имеется топологический порядок только, если он ацикличен.

Доказательство. Условие необходимости («толе^о, если» в утверждении) легко показать. Предположим, G топологически упорядочен. Будем исходить от противного, то есть из того, что в G имеются циклы, состоящие из путей (vjo, v/i), (v/i, va), …, (vikA, v,0).

При топологическом порядке должно соблюдаться /q < i\ <  i < /’о,

что, естественно, невозможно. Следовательно, G должен быть ацикличным.

Теперь докажем справедливость самого условия («если»). Предположим, С является ацикличным. Опишем алгоритм организации топологического порядка в G. Поскольку G ацикличен, то он должен иметь узел без входящих путей (то есть с нулевой степенью). Пусть v\ будет таким узлом. Действительно, если vi не существует, то при отслеживании направленного маршрута из произвольного узла отправление существует возможность наткнуться на уже пройденный узел, что противоречит идее ацикличности диграфа. Если удалить v\ из G вместе с его исходящими путями, то полученный в результате дйграф по-прежнему будет ацикличным. Следовательно, этот результативный диграф тоже имеет узел без входящих путей, и пусть этим узлом будет v2. Повторяя весь процесс до тех пор, пока диграф не опустеет, получим порядок vi, vn узлов в G. Исходя из описанной конструкции, если (v,,vy) — путь в G, то V/ должен быть удален ранее, чем может быть удален vy, а значит, / < у. Таким образом, v\, vn является топологическим порядком.

Из обоснования утверждения 12.13 вытекает описание алгоритма вычисления топологического порядка диграфа (фрагмент кода 12.11) под названием топологическая сортировка (topological sorting).

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

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

Output: топологический порядок v\, vn диграфа G.

Пусть S — изначально пустой стек for каждого узла и в G do

Пусть счетчик нумерации (и) будет входящей степенью и. if incounter (и) = 0 then

S.push(u) / <- 1

while S не будет пустой do и <- S.pop()

Пусть и будет номером узла / в топологической сортировке. / <- i + 1

for каждого входящего пути (и, w) узла и do incounter(w) <- incounter(w) – 1 if incounter (w) = 0 then S.push(w)

Фрагмент кода 12.11. Псевдокод алгоритма топологической сортировки (применение алгоритма приведено на рис. 12.12)

Утверждение 12.14. Пусть G будет диграфом из п узлов и т путей. Алгоритм топологической сортировки выполняется за 0(п + т) времени, используя О(п) дополнительного времени, и либо топологически упорядочивает G, либо не может пронумеровать некоторые узлы, что означает наличие в G направленных циклов.

Доказательство. Предварительные вычисления входящих степеней и настройка счетчиков нумерации могут быть выполнены с помощью простого обхода графа, занимающего 0(п + т) времени. Соответствие нумерации узлам произведем с помощью модели «декоратор». Предположим, узел и проходится алгоритмом топологической сортировки после удаления из стека S. Узел и может быть пройден только в том случае, если счетчик (и) = 0, то есть все предшественники (узлы с исходящими путями

Рис. 12.12. Пример выполнения алгоритма топологической сортировки Topolo- gicalSort (фрагмент кода 12.11): (а) исходная конфигурация; (b-i) результат последовательно выполняемых итераций. Маркировки узлов показывают номер узла и текущее значение счетчика. Пройденные пути изображены пунктирными стрелками. Жирными пунктирными • ? • ? линиями обозначены узлы Я пути, проходимые в текущей итерации

в узел и) были пройдены до него. Как следствие, любой узел, находящийся в направленном цикле, никогда не будет пройден, а любой другой будет пройден только один раз. Алгоритм проходит все исходящие пути каждого из встреченных узлов один раз, так что время его выполнения будет пропорционально количеству исходящих путей проходимых узлов. Из этого следует, что алгоритм выполняется за время 0(п + т). С учетом требуемого пространства отметим, что стек S и переменные для счетчиков, присоединяемые к узлам, занимают О(п) места.

В качестве побочного эффекта алгоритм топологической сортировки, показанный во фрагменте кода 12.11, во время работы проверяет исходный диграф на ацикличность. Если алгоритм закончит работу, не пройдя все узлы диграфа, это будет означать, что подграф из непройденных узлов содержит направленный цикл (см. рис. 12.13).

Рис. 12.13. Обнаружение направленного цикла: (а) исходный диграф; (Ь) после окончания работы алгоритма топологической сортировки (фрагмент кода 12.11), подграф с непронумерованными узлами содержит направленный цикл

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

По теме:

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