Проектирование и анализ алгоритма

На самом деле условие, обратное (3.18), выполняется, и для доказательства этого факта мы воспользуемся эффективным алгоритмом вычисления топологического упорядочения. Ключевым фактором станет определение отправной точки: с какого узла должно начинаться топологическое упорядочение? Такой узел v1 не должен иметь входящих ребер, поскольку любое входящее ребро нарушило бы опреде- ляющее свойство топологического упорядочения (все ребра должны указывать «вперед»).
Следовательно, нужно доказать следующий факт:

(3.19) В каждом направленном ациклическом графе G существует узел v, не имеющий входящих ребер.

Доказательство. Пусть G — направленный граф, в котором каждый узел имеет по крайней мере одно входящее ребро. Мы покажем, как найти цикл в таком гра- фе G; тем самым утверждение будет доказано. Выбираем любой узел v и начинаем переходить по ребрам в обратном направлении от v; так как v содержит как мини- мум одно входящее ребро (u, v), можно перейти к u; так как ребро и содержит как минимум одно входящее ребро (х, u), можно вернуться обратно к х; и т. д. Этот про- цесс может продолжаться бесконечно, так как каждый обнаруженный узел имеет входящее ребро. Но после n + 1 шагов какой-то узел w неизбежно будет посещен дважды. Если обозначить C серию узлов, встреченных между последовательными посещениями w, то C очевидным образом образует цикл. ■

Существование такого узла v — все, что необходимо для построения топологи- ческого упорядочения G. Докажем посредством индукции, что каждый DAG имеет топологическое упорядочение. Это утверждение очевидно истинно для DAG с одним или двумя узлами. Теперь допустим, что оно истинно для DAG с количеством узлов до n. В DAG G с n + 1 узлом будет присутствовать узел v, не имеющий входящих ребер; его существование гарантировано по (3.19). Узел v ставится на первое место в топологическом упорядочении; такое размещение безопасно, поскольку все ребра из v указывают вперед. Теперь заметим, что граф G - {v} является DAG, поскольку удаление v не может привести к образованию циклов, не существовавших ранее. Кроме того, граф G - {v} содержит n узлов, что позволяет нам применить предполо- жение индукции для получения топологического упорядочения G - {v}. Присоединим узлы G - {v} в этом порядке после v; в полученном упорядочении G все ребра будут указывать вперед, а следовательно, оно является топологическим упорядочением.

Итак, положение, обратное (3.18), успешно доказано.

(3.20) Если граф G является DAG, то в нем существует топологическое упоря- дочение.

Доказательство методом индукции содержит следующий алгоритм для вычис- ления топологического упорядочения G.

Чтобы вычислить топологическое упорядочение G:

Найти узел v, не имеющий входящих ребер, и поставить его в начало.

Удалить v из G.

Рекурсивно вычислить топологическое упорядочение G - {v}

и присоединить его после v

На рис. 3.8 изображена последовательность удалений узлов, происходящих при применении к графу на рис. 3.7. Закрашенные узлы на каждой итерации не имеют входящих ребер; здесь важно то, что, как гарантирует (3.19), при примене- нии алгоритма к DAG всегда найдется хотя бы один такой узел, который может быть удален.


Рис. 3.8. Начиная с графа на рис. 3.7 узлы удаляются один за другим для добавления в топологическое упорядочение. Закрашенные узлы не имеют входящих ребер; следует заметить, что на каждой стадии выполнения алгоритма всегда найдется хотя бы один

такой узел

Чтобы сформулировать оценку времени выполнения алгоритма, заметим, что нахождение узла v, не имеющего входящих ребер, и удаление его из G может выполняться за время O(n). Так как алгоритм выполняется за n итераций, общее время выполнения составит O(n2).

Результат не так уж плох; а для сильно разреженного графа G, содержащего Θ(η2) ребер, обеспечивается линейная зависимость от размера входных данных. Но если количество ребер m намного меньше n2, хотелось бы чего-то большего. В таком случае время выполнения O(m + n) было бы значительным улучшением по сравнению с θ(п2).

Оказывается, время выполнения O(m + n) может быть обеспечено тем же высо- коуровневым алгоритмом — итеративным удалением узлов, не имеющих входящих ребер. Просто нужно повысить эффективность поиска таких узлов, а это можно сделать так.

Узел объявляется «активным», если он еще не был удален алгоритмом, и мы будем явно хранить два вида данных:

(a) для каждого узла w — количество входящих ребер, ведущих к w от активных

узлов; и

(b) множество S всех активных узлов G, не имеющих входящих ребер из других

активных узлов.

В начале выполнения все узлы активны, поэтому данные (a) и (b) могут иници- ализироваться за один проход по узлам и ребрам. Тогда каждая итерация состоит из выбора узла v из множества S и его удаления. После удаления v перебираются все узлы w, к которым существовали ребра из v, и количество активных входя- щих ребер, хранимое для каждого узла w, уменьшается на 1. Если в результате количество активных входящих ребер для w уменьшается до 0, то w добавляется в множество S. Продолжая таким образом, мы постоянно следим за узлами, при- годными для удаления, осуществляя постоянный объем работы на каждое ребро в ходе выполнения всего алгоритма.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Проектирование и анализ алгоритма:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  3. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. 2. Специфика и алгоритмы работы с источниками.
  9. Алгоритм обработки результатов.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Этапы социокультурного проектирования
  12. ЛЕКЦИЯ 18 3.2.2.2. Методы социокультурного проектирования
  13. Глава 3. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПЕДАГОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ
  14. 3.2.2. Социокультурная парадигма проектирования города Лекция 17