![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Модель DAG вычислений
ЧИСЕЛ ФИБОНАЧЧИ Дерево в верхней части диаграммы указывает на зависимость вычисления очередного числа от вычисления двух его предшественников. Граф DAG, изображенный в нижней части диаграммы, демонстрирует ту же зависимость, используя лишь часть узлов. Глава 19. Орграфы и ориентированные ациклические графы
РИСУНОК 19.19. ПРЕДСТАВЛЕНИЕ АРИФМЕТИЧЕСКОГО ВЫРАЖЕНИЕ С ПОМОЩЬЮ ГРАФА DAG Оба изображенные на диаграмме графы BAG являются представлениями одного и того же арифметического выражения (c*(a+b))-((a+b)*(a+b)+e)). В двоичном дереве грамматического разбора, которое показано в левой части диаграммы, листы представляют операнды, а все внутренние узлы — операции, выполняемые над выражениями, представленными двумя поддеревьями (см. рис. 5.31). Граф DAG, изображенный в правой части диаграммы, — это более компактное представление того же дерева. Более того, мы можем вычислить значение выражения за время, пропорциональное размеру DAG, который обычно значительно меньше, чем размер дерева (см. упражнения 19.112 и 19.113). Программа 19.5. Представление бинарного дерева Представленный здесь фрагмент программного кода реализует обход в обратном направлении, который выполняет построение двоичного DAG, соответствующего структуре двоичного дерева (см. глава 12) путем выявления общих поддеревьев. Он использует индексирующий класс, подобный классу ST из программы 17.15 (скорректированный с целью обеспечения ввода пар чисел вместо ввода строк с клавиатуры) с тем, чтобы присвоить уникальное целочисленное значение каждой отдельной древовидной структуре для применения в представлении DAG в виде вектора двоичных целочисленных структур (см. рис. 20). Пустому дереву (нулевая связь) присваивается индекс 0, дереву с единственным узлом — индекс 1 и т.д. Индекс, соответствующий каждому поддереву, вычисляется в рекурсивном режиме. Затем создается ключ, обладающий таким свойством, что каждый узел одного и того же поддерева будет иметь тот же индекс, и этот индекс возвращается после заполнения связей соответствующего ребра графа DAG (поддерево). int compressR(link h) { STx st; if (h == NULL) return 0; 1 = compressR (h-> l); r = compressR (h-> r); t = st.index(1, r); adj[t].l = 1; adj[t].r = r; return t; РИСУНОК 19.20. СЖАТИЕ БИНАРНОГО ДЕРЕВА Таблица из девяти пар целых чисел, приведенная в левой нижней части рисунка, является компактным представлением двоичного DAG (внизу справа), которое представляет собой сжатую версию двоичного BAG двоичной древовидной структуры, показанной в верхней части рисунка. Метки узлов не хранятся в явном виде в рассматриваемой структуре данных: таблица представляет восемнадцать ребер 1-0, 1-0, 2-1, 2-1, 3-1, 3-2 и т.д., однако обозначает левое и правое ребра, исходящие из каждого узла (как в бинарном дереве), при этом исходная вершина каждого ребра табличном индексе выражается неявно. 198 Часть 5. Алгоритмы на графах
|