Орієнтований (спрямований) ациклический граф - випадок орієнтованого графа, в якому відсутні орієнтовані цикли. тобто шляху, що починаються і закінчуються в одній і тій же вершині. Орієнтований ациклічний граф є узагальненням дерева (точніше, їх об'єднання - ліси).
застосування
- Компілятори машинних мов;
- Клас штучних нейронних мереж без зворотного зв'язку (en: Feedforward neural networks);
- Статистика: Байєсовські мережі довіри.
Оптимізація префіксние дерева
DAWG (англ. Directed acyclic word graph) - компактна форма зберігання префіксние дерева, список слів, оптимізована для з'ясування, входить деякий слово в цей список чи ні. Сам список отримати нескладно рекурсивним проходом дерева. З точки зору програми, проводить обхід або пошук, орієнтований ациклічний граф нічим не відрізняється від дерева, просто однакові піддерева зберігаються в єдиному екземплярі.
Сам спосіб перетворення очевидний: пошук однакових піддерев і перепідключення посилань, одиничний екземпляр. Насправді крім букви в вершинах зберігається прапорець, який вказує, чи є дана буква останньої. Тому для пошуку слів, неповторяються перетворення в DAWG і назад відбувається без втрат (з точністю до порядку слів).