Направленный ациклический граф
Направленный ациклический граф или ориентированный ациклический граф (англ. directed acyclic graph, сокращённо англ. DAG) — случай направленного графа, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса).
Применения [править]
- Компиляторы машинных языков;
- Класс искусственных нейронных сетей без обратной связи (en:Feedforward neural networks);
- Статистика: Байесовская сеть доверия.
Оптимизация префиксного дерева [править]
DAWG (англ. directed acyclic word graph) — компактная форма хранения префиксного дерева, списка слов, оптимизированная для выяснения, входит ли некое слово в данный список или нет. Сам список получить несложно рекурсивным обходом дерева. С точки зрения программы, осуществляющей обход или поиск, DAWG ничем не отличается от дерева, просто одинаковые поддеревья хранятся в единственном экземпляре.
Сам способ преобразования очевиден: поиск одинаковых поддеревьев и переподключение ссылок на единственный экземпляр. На самом деле помимо буквы в вершинах хранится флажок, указывающий, является ли данная буква последней. Так что для списков неповторяющихся слов преобразование в DAWG и обратно происходит без потерь (с точностью до порядка слов).
 |
В этой статье не хватает ссылок на источники информации.
Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 14 мая 2011. |
 |
В другом языковом разделе есть более полная статья Directed acyclic graph (англ.)
Вы можете помочь проекту, расширив текущую статью с помощью перевода.
|
| Структуры данных (список) | |
|---|---|
| Типы | |
| Массивы | |
| Списки | |
| Деревья | |
| Графы |
Ориентированный граф • Направленный ациклический граф • Бинарная диаграмма решений • Гиперграф |
