Модель 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__________________

Представленный здесь фрагмент программного кода реализует обход в обратном направлении, который выполняет построение двоичного 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. Алгоритмы на графах