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