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


Направленный ациклический граф
Directed acyclic graph.png

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

Применения

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

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

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



Wikimedia Foundation. 2010.

Смотреть что такое "Направленный ациклический граф" в других словарях:

  • Граф зависимостей — В математике, информатике и цифровой электронике, граф зависимостей представляет собой ориентированный граф, отражающий зависимости нескольких объектов друг к другу. По графу зависимостей можно определить порядок вычислений или его недостатки,… …   Википедия

  • Объектный граф — Граф объектный  это совокупность узлов и ребер, соединяющих эти узлы. Объектные графы обеспечивают простой способ учёта взаимных связей в множестве объектов, и не обязательно, чтобы эти связи в точности проецировались в классические связки… …   Википедия

  • Ориентированный граф — (кратко орграф)  (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках (Оре) и просто рёбрами …   Википедия

  • Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф …   Википедия

  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С …   Википедия

  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) …   Википедия

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • Список структур данных — …   Википедия

  • Дерево (структура данных) — У этого термина существуют и другие значения, см. Дерево (значения). Простой пример неупорядоченного дерева Дерево  одна из наиболее широко распространённых структу …   Википедия