19-10-2023
Направленный ациклический граф — случай направленного графа, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса).
DAWG (англ. directed acyclic word graph) — компактная форма хранения префиксного дерева, списка слов, оптимизированная для выяснения, входит ли некое слово в данный список или нет. Сам список получить несложно рекурсивным обходом дерева. С точки зрения программы, осуществляющей обход или поиск, DAWG ничем не отличается от дерева, просто одинаковые поддеревья хранятся в единственном экземпляре.
Сам способ преобразования очевиден: поиск одинаковых поддеревьев и переподключение ссылок на единственный экземпляр. На самом деле помимо буквы в вершинах хранится флажок, указывающий, является ли данная буква последней. Так что для списков неповторяющихся слов преобразование в DAWG и обратно происходит без потерь (с точностью до порядка слов).
Считается, что система категорий в Википедии не должна содержать циклов.
Структуры данных | |
---|---|
Типы | Коллекция · Контейнер |
Массивы | Ассоциативный массив · Multimap · Множество · Мультимножество · Хеш-таблица |
Списки | Связный список · Очередь (Кольцевой буфер, Двусвязная) · Стек · Список с пропусками |
Деревья | B-дерево · Двоичное дерево поиска · Куча |
Графы | Ориентированный граф · Направленный ациклический граф · Бинарная диаграмма решений · Гиперграф |
Список структур данных |
Направленный ациклический граф.