Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Visit(v);
|
|
typename Dag:: adjIterator A(D, v);
for (int t = A.beg();! A.end(); t = A.nxt())
traverseR(D, t); }
однако мы редко используем полный обход этого типа, поскольку обычно стремимся воспользоваться теми же средствами, какие применяются в графах DAG для экономии пространства, чтобы сэкономить время при его обходе (например, маркирование посещенных вершин при обычном поиске в глубину). Та же идея применяется к поиску, по условиям которого мы выполняем рекурсивные вызовы только для одной связи, инцидентной каждой вершине. В таком алгоритме затраты на поиск в графе DAG и дереве оказываются одними и теми же, но в то же время DAG использует намного меньшее пространство памяти.
Поскольку графы DAG обеспечивают способы более компактного представления деревьев, чем идентичные им поддеревья, мы часто пользуемся графами DAG вместо деревьев для представления различных вычислительных абстракций. В контексте конструкции алгоритма, различия между представлением программы в виде DAG и представлением в виде дерева существенны в плане динамического программирования (см., например, рис.
Часть 5. Алгоритмы на графах
| ревьев в некоторых приложениях. Например, как нетрудно видеть из рис. 19.20 и программы 19.5, мы можем сжать trie-дерево существования до двоичного DAG без изменения реализации поиска. Эквивалентное приложение заключается в том, чтобы рассматривать ключи trie-дерева как соответствующие строкам таблицы истинности булевской функции, на которых эта функция принимает истинное значение (см. упражнения 18.84-18.87). Двоичный DAG есть модель экономичной схемы, которая вычисляет эту функцию. В таком приложении двоичные графы DAG называются схемами BDD (binary decision diagram — двоичная схема решений). Данные приложения заставляют нас обратиться в двух следующих разделах к изучению алгоритмов обработки графов DAG. Эти алгоритмы не только приводят к реализации эффективных и полезных функций АТД графов DAG, но и позволяют оценить трудность обработки орграфов. Как мы увидим далее, даже если графы DAG покажутся значительно более простыми структурами, чем орграфы общего вида, очевидно, что некоторые фундаментальные задачи решаются ничуть не проще. |
19.18 и упражнение 19.78). Графы DAG к тому же широко используются в компиляторах в качестве промежуточных представлений арифметических выражений и программ (см., например, рис. 19.19) и в системах расчета электронных схем в качестве промежуточных представлений комбинационных схем.
В соответствии с вышесказанным, при рассмотрении бинарных деревьев возникает важный пример, который находит применение во многих приложениях. Мы можем наложить те же ограничения на графы DAG, какие мы налагали на деревья, чтобы выделить из них бинарные деревья.
Определение 19.6. Двоичный DAG (binary DAG) есть ориентированный ациклический граф с двумя ребрами, исходящими из каждого узла, которые рассматриваются как левое и правое ребро, при этом каждое из них или оба сразу могут быть нулевыми.
Различие между двоичными графами DAG и бинарными деревьями заключается в том, что в двоичном DAG может быть более одной связи, ведущей в конкретный узел. Как и данное нами определение бинарных деревьев, это определение моделирует естественное представление, в рамка которого каждый узел представляет собой структуру с левой связью и с правой связью, указывающими на другие узлы (либо являющимися нулевыми), подчиняются только глобальному ограничению, суть которого заключается в том, что никакие направленные циклы невозможны. Двоичные графы DAG имеют большое значение, поскольку они обеспечивают компактный способ представления бинарных де-
РИСУНОК 19.18.