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

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

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

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

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

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

См. также

• Топологическая сортировка

Ссылки

• Weisstein, Eric W. [mathworld.wolfram.com/AcyclicDigraph.html Acyclic Digraph] / Wolfram MathWorld  (англ.)
• [ericsink.com/vcbe/html/directed_acyclic_graphs.html]

Отрывок, характеризующий Направленный ациклический граф

– Вы ошибаетесь, – неторопливо, с смелою и несколько насмешливою улыбкой проговорил Борис. – Я Борис, сын княгини Анны Михайловны Друбецкой. Ростова отца зовут Ильей, а сына – Николаем. И я m me Jacquot никакой не знал.
Пьер замахал руками и головой, как будто комары или пчелы напали на него.
– Ах, ну что это! я всё спутал. В Москве столько родных! Вы Борис…да. Ну вот мы с вами и договорились. Ну, что вы думаете о булонской экспедиции? Ведь англичанам плохо придется, ежели только Наполеон переправится через канал? Я думаю, что экспедиция очень возможна. Вилльнев бы не оплошал!
Борис ничего не знал о булонской экспедиции, он не читал газет и о Вилльневе в первый раз слышал.
– Мы здесь в Москве больше заняты обедами и сплетнями, чем политикой, – сказал он своим спокойным, насмешливым тоном. – Я ничего про это не знаю и не думаю. Москва занята сплетнями больше всего, – продолжал он. – Теперь говорят про вас и про графа.
Пьер улыбнулся своей доброю улыбкой, как будто боясь за своего собеседника, как бы он не сказал чего нибудь такого, в чем стал бы раскаиваться. Но Борис говорил отчетливо, ясно и сухо, прямо глядя в глаза Пьеру.
– Москве больше делать нечего, как сплетничать, – продолжал он. – Все заняты тем, кому оставит граф свое состояние, хотя, может быть, он переживет всех нас, чего я от души желаю…
– Да, это всё очень тяжело, – подхватил Пьер, – очень тяжело. – Пьер всё боялся, что этот офицер нечаянно вдастся в неловкий для самого себя разговор.
– А вам должно казаться, – говорил Борис, слегка краснея, но не изменяя голоса и позы, – вам должно казаться, что все заняты только тем, чтобы получить что нибудь от богача.
«Так и есть», подумал Пьер.
– А я именно хочу сказать вам, чтоб избежать недоразумений, что вы очень ошибетесь, ежели причтете меня и мою мать к числу этих людей. Мы очень бедны, но я, по крайней мере, за себя говорю: именно потому, что отец ваш богат, я не считаю себя его родственником, и ни я, ни мать никогда ничего не будем просить и не примем от него.