Спрямований ациклічний граф або орієнтований ациклічний граф (англ. Directed acyclic graph. Скорочено англ. DAG) - випадок спрямованого графа. в якому відсутні спрямовані цикли. тобто шляху. починаються і закінчуються в одній і тій же вершині. Спрямований ациклічний граф є узагальненням дерева (точніше, їх об'єднання - ліси).
застосування
Оптимізація префіксного дерева
DAWG (англ. Directed acyclic word graph) - компактна форма зберігання префіксного дерева. списку слів, оптимізована для з'ясування, чи входить якесь слово в даний список чи ні. Сам список отримати нескладно рекурсивним обходом дерева. З точки зору програми, що здійснює обхід або пошук, DAWG нічим не відрізняється від дерева, просто однакові піддерева зберігаються в єдиному екземплярі.
Сам спосіб перетворення очевидний: пошук однакових піддерев і перепідключення посилань на єдиний екземпляр. Насправді крім букви в вершинах зберігається прапорець, який вказує, чи є дана буква останньої. Так що для списків неповторяющихся слів перетворення в DAWG і назад відбувається без втрат (з точністю до порядку слів).
У цій статті не вистачає посилань на джерела інформації.
Дивитися що таке "Спрямований ациклічний граф" в інших словниках:
Граф залежностей - У математиці, інформатиці та цифровій електроніці, граф залежностей є орієнтований граф, що відображає залежність кількох об'єктів один до одного. За графу залежностей можна визначити порядок обчислень або його недоліки, ... ... Вікіпедія
Об'єктний граф - Граф об'єктний це сукупність вузлів і ребер, що з'єднують ці вузли. Об'єктні графи забезпечують простий спосіб обліку взаємних зв'язків в безлічі об'єктів, і не обов'язково, щоб ці зв'язки в точності проектувалися в класичні зв'язки ... ... Вікіпедія
Орієнтований граф - (коротко орграф) (мульти) граф, ребрам якого присвоєно напрямок. Спрямовані ребра іменуються також дугами, а в деяких джерелах (Оре) і просто ребрами ... Вікіпедія
Вершина (граф) - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія
Словник термінів теорії графів - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И К Л М Н О П Р С ... Вікіпедія
Глосарій теорії графів - Ця сторінка глосарій. Див. Також основну статтю: Теорія графів Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці) ... Вікіпедія
Список термінів, що відносяться до алгоритмів і структур даних - Це службовий список статей, створений для координації робіт з розвитку теми. Дане попередження не встановлюється на інформаційні списки та глосарії ... Вікіпедія
Список термінів - Список термінів, що відносяться до алгоритмів і структур даних Це сл ... Вікіпедія
Дерево (структура даних) - Цей термін має також інші значення див. Дерево (значення). Простий приклад невпорядкованого дерева Дерево одна з найбільш широко поширених структур ... Вікіпедія