Спрямований орієнтований ациклічний граф англ directed acyclic graph DAG випадок орієнтованого графа в якому відсутні ор

Спрямований (орієнтований) ациклічний граф (англ. directed acyclic graph, DAG) — випадок орієнтованого графа, в якому відсутні орієнтовані цикли, тобто шляхи, що починаються і закінчуються в одній і тій самій вершині. Орієнтований ациклічний граф є узагальненням дерева (точніше, їх об'єднання — лісу).

Застосування

Компілятори машинних мов;
Клас штучних нейронних мереж без зворотного зв'язку (Нейронна мережа прямого поширення);
Статистика: Баєсова мережа довіри.

Оптимізація префіксного дерева

DAWG (англ. directed acyclic word graph) — компактна форма збереження префіксного дерева, списку слів, оптимізована для з'ясування, чи входить деяке слово в цей список чи ні. Сам список отримати нескладно рекурсивним проходом дерева. З точки зору програми, що провадить обхід чи пошук, орієнтований ациклічний граф нічим не відрізняється від дерева, просто однакові піддерева зберігаються в одиничному екземплярі.

Сам спосіб перетворення очевидний: пошук однакових піддерев і перепідключення посилань, одиничний екземпляр. В дійсності окрім букви в вершинах зберігається прапорець, що вказує, чи є дана буква останньою. Через це для пошуку слів, що не повторюються перетворення в DAWG і назад відбувається без втрат (з точністю до порядку слів).

Інші застосування

Вважається, що у Вікіпедії не повинна включати циклів.

Посилання

Weisstein, Eric W. Орієнтований ациклічний граф(англ.) на сайті Wolfram MathWorld.