Ориентированный (направленный) ациклический граф - случай ориентированного графа, в котором отсутствуют ориентированные циклы, т.е. пути, начинающиеся и заканчивающиеся в одной и той же вершине. Ориентированный ациклический граф является обобщением дерева (точнее, их объединение - леса ).
Применение
- Компиляторы машинных языков;
- Класс искусственных нейронных сетей без обратной связи ( en: Feedforward neural networks );
- Статистика: Байесовские сети доверия.
Оптимизация префиксные дерева
DAWG ( англ. directed acyclic word graph ) - компактная форма хранения префиксные дерева, список слов, оптимизированная для выяснения, входит некоторое слово в этот список или нет. Сам список получить несложно рекурсивным проходом дерева. С точки зрения программы, проводит обход или поиск, ориентированный ациклический граф ничем не отличается от дерева, просто одинаковые поддеревья хранятся в единственном экземпляре.
Сам способ преобразования очевиден: поиск одинаковых поддеревьев и переподключение ссылок, единичный экземпляр. В действительности кроме буквы в вершинах хранится флажок, указывающий, является ли данная буква последней. Поэтому для поиска слов, неповторяються преобразования в DAWG и обратно происходит без потерь (с точностью до порядка слов).
