Направленный ациклический граф

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

Направленный ациклический граф — случай направленного графа, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса).

Применения

Оптимизация префиксного дерева

DAWG (англ. directed acyclic word graph) — компактная форма хранения префиксного дерева, списка слов, оптимизированная для выяснения, входит ли некое слово в данный список или нет. Сам список получить несложно рекурсивным обходом дерева. С точки зрения программы, осуществляющей обход или поиск, DAWG ничем не отличается от дерева, просто одинаковые поддеревья хранятся в единственном экземпляре.

Сам способ преобразования очевиден: поиск одинаковых поддеревьев и переподключение ссылок на единственный экземпляр. На самом деле помимо буквы в вершинах хранится флажок, указывающий, является ли данная буква последней. Так что для списков неповторяющихся слов преобразование в DAWG и обратно происходит без потерь (с точностью до порядка слов).

Другие применения

Считается, что система категорий в Википедии не должна содержать циклов.


de:Gerichteter azyklischer Graph

en:Directed acyclic graph fr:Graphe acyclique orienté hu:Irányított körmentes gráf pl:Skierowany graf acykliczny pt:Grafos acíclicos dirigidos

Личные инструменты

Served in 0.102 secs.