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