EssayAI
Блог
Блог
Естественные науки

Ориентированный ациклический граф: что такое DAG

8 ноября 2026Время чтения: 8 минут
#ориентированный ациклический граф#DAG#теория графов#зависимости#критический путь
Ориентированный ациклический граф: что такое DAG

Ориентированный ациклический граф, или DAG, помогает описать зависимости, которые нельзя обойти по кругу. Например, перед сборкой программы нужно подготовить компоненты, а перед проверкой сборки - собрать её. Граф показывает эти ограничения стрелками и позволяет понять, какие действия можно выполнять одновременно. Ниже разберём определение, свойства и пример расчёта сроков. В интерактиве можно изменить длительность одной работы и увидеть, когда она начинает влиять на весь проект.

Что означает DAG

Ориентированный ациклический граф - это ориентированный граф без направленных циклов. Сокращение DAG происходит от английского directed acyclic graph. Граф G=(V,E)G=(V,E) состоит из множества вершин VV и множества направленных рёбер EE. Стрелка u→vu\to v связывает две вершины в определённом направлении: перейти по ней можно от uu к vv, но обратное движение требует отдельной стрелки.

Направленный путь проходит по стрелкам последовательно. Направленный цикл возвращает путь к его исходной вершине, двигаясь только по направлению рёбер. Петля u→uu\to u тоже является циклом. В DAG таких замкнутых маршрутов нет. Это определение и связь с топологическим порядком приводятся в материалах MIT по алгоритмам.

Подсветка проходит по работам графа: разветвление после А показывает две независимые ветви, а стрелки к Г показывают необходимость дождаться обеих.

Отсутствие направленного цикла не означает, что на рисунке нельзя найти замкнутый контур, если игнорировать стрелки. В примере ниже А, Б, Г, В образуют такой контур, но все стрелки ведут от А к Г, а не обратно. Поэтому граф остаётся ациклическим.

Как читать вершины, рёбра и пути

Возьмём пять работ А, Б, В, Г и Д. Пусть стрелка означает «первая работа должна закончиться до начала второй». Связи заданы так:

А→Б,А→В,Б→Г,В→Г,Г→Д.А\to Б,\quad А\to В,\quad Б\to Г,\quad В\to Г,\quad Г\to Д.

У А нет входящих рёбер: это источник. У Д нет исходящих рёбер: это сток. Источников и стоков в графе может быть несколько; изолированная вершина одновременно обладает обоими свойствами. Степень входа вершины - число входящих в неё рёбер, степень выхода - число исходящих. Для Г они равны соответственно двум и одному.

Из А можно добраться до Д, например по пути А→В→Г→Д. Поэтому Д достижима из А, хотя прямой стрелки А→Д нет. Б и В между собой путём не связаны: после завершения А их зависимости разрешают выполнять параллельно. При этом отсутствие пути само по себе не обещает, что ресурсов хватит на одновременную работу.

Рисунок - лишь представление структуры: вершины можно переставить на листе, а стрелки могут пересекаться. Важно не расположение точек, а то, какие пары соединены и куда направлены рёбра. Для хранения используют, например, списки исходящих соседей: у А это Б и В, у Г - только Д. Такое представление занимает O(∣V∣+∣E∣)O(|V|+|E|) памяти.

Почему порядок работ существует

Для конечного DAG существует топологический порядок: такая последовательность всех вершин, в которой начало каждого ребра стоит раньше его конца. В нашем примере подходят и А, Б, В, Г, Д, и А, В, Б, Г, Д. Положение Б и В можно поменять, поскольку ни одна не зависит от другой. Порядок задаёт допустимую последовательность, но сам по себе не указывает время начала или длительность работ.

Почему такой порядок возможен? В непустом конечном DAG найдётся вершина без входящих рёбер. Если бы у каждой был предшественник, можно было бы бесконечно идти назад по стрелкам. В конечном наборе вершин одна повторилась бы, и возник бы направленный цикл. Удалив источник и его рёбра, получаем меньший DAG; повторяя действие, получаем порядок всех вершин.

Обратно, при наличии цикла каждая его вершина должна стоять раньше следующей, а последняя - раньше первой. Это невозможно. Таким образом, конечный орграф имеет топологический порядок тогда и только тогда, когда он ацикличен. Пошаговое построение очередью и вариант через DFS разобраны отдельно в статье о топологической сортировке.

Как проверить граф на цикл

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

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

При списках смежности оба подхода работают за O(∣V∣+∣E∣)O(|V|+|E|) времени. Если нужен сам цикл, сохраняют предков обхода и восстанавливают путь по ним. Проверка только одной произвольной цепочки недостаточна: цикл может находиться в другой ветви или компоненте.

Пример: ранние сроки и критический путь

Пусть длительности А, Б, В, Г, Д равны 2, 3, 4, 2 и 1 единице времени. Работы без взаимной зависимости могут идти одновременно, ресурсов достаточно, задержек между работами нет. Старт проекта - момент 0. Раннее начало работы равно максимуму ранних окончаний её непосредственных предшественников; для источника оно равно нулю. Раннее окончание - начало плюс длительность.

РаботаПредшественникиРаннее началоРаннее окончание
Анет02
БА25
ВА26
ГБ, В68
ДГ89
Ранние окончания пяти работ: 2, 5, 6, 8, 9 и критический путь через А, В, Г, Д
Ранние окончания пяти работ: 2, 5, 6, 8, 9 и критический путь через А, В, Г, Д

Г не может начаться в момент 5, хотя Б уже закончена: нужно дождаться и В до момента 6. Самая длинная по сумме длительностей цепочка А→В→Г→Д занимает 2+4+2+1=92+4+2+1=9. Это критический путь для данной модели; другая ветвь занимает 2+3+2+1=82+3+2+1=8. Минимальный срок проекта при сделанных предположениях равен 9. Метод длиннейшего пути в DAG лежит и в основе реализации CPM Принстонского университета.

В интерактиве длительность В можно менять от 1 до 6. При значении 3 обе ветви занимают по 8 и становятся критическими; при значении меньше 3 критична ветвь через Б, при большем - через В. Это не прогноз реального проекта: ограничение числа работников, выходные и задержки передачи здесь не учтены. О ранних и поздних сроках с резервами подробнее рассказано в статье о сетевом планировании.

Где ещё применяется DAG

В системе сборки вершинами могут быть файлы или задачи, а стрелками - зависимости между ними. Изменение исходного файла заставляет пересчитать достижимые от него результаты. В конвейере данных узлы представляют преобразования, а стрелки - передачу результата дальше. DAG также моделирует зависимости курсов, формулы таблиц и историю версий с объединением ветвей.

Ещё одно применение - поиск путей во взвешенном графе. Если обработать вершины в топологическом порядке, к моменту обработки все возможные предшественники уже рассмотрены. Это позволяет находить кратчайшие или длиннейшие пути от источника за O(∣V∣+∣E∣)O(|V|+|E|) даже при отрицательных весах рёбер; недостижимые вершины нужно обрабатывать отдельно. Такой подход описан в курсе алгоритмов Принстонского университета. Для невзвешенного графа другую задачу - путь с минимальным числом рёбер - решает обход в ширину.

Модель полезна лишь при корректной семантике стрелки. Если процессы действительно допускают повторную обратную связь, искусственное удаление цикла исказит систему. Иногда достаточно развернуть повторения во времени и представить каждую итерацию отдельными вершинами, но сначала необходимо определить границы модели.

Частые ошибки

  • Игнорировать направление рёбер. Замкнутый контур на рисунке не обязательно является направленным циклом.
  • Путать ребро с путём. Достижимость может обеспечиваться несколькими стрелками без прямой связи.
  • Считать топологический порядок единственным. Независимые вершины нередко можно переставлять.
  • Принимать порядок за расписание. Длительности и ограничения ресурсов требуют дополнительного расчёта.
  • Проверять только связную часть. Цикл может скрываться в другой компоненте.

FAQ

Может ли DAG содержать несколько источников?

Да. Любые вершины без входящих рёбер являются источниками; конечный непустой DAG имеет хотя бы один источник и хотя бы один сток.

Является ли дерево DAG?

Дерево без направлений ещё не является ориентированным графом. Если назначить направление каждому его ребру, получится DAG: в исходном дереве нет даже неориентированного цикла. Но не каждый DAG является деревом: в нём могут сходиться несколько путей.

Может ли DAG содержать отрицательные веса?

Да. Ацикличность относится к направлению связей, а не к значениям весов. Их смысл зависит от модели: отрицательная стоимость возможна в задаче путей, но отрицательная длительность работы обычно не подходит для расписания.

Коротко

DAG - ориентированный граф без направленных циклов. Его вершины можно упорядочить так, чтобы каждая стрелка вела вперёд. Это позволяет проверять зависимости, находить достижимость и вычислять пути или сроки в порядке предшествования. Для расписания дополнительно нужны длительности и явные предположения о ресурсах.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Доминирующее множество в графе: определение и примеры

Доминирующее множество в графе: определение и примеры

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

8 ноября 20268 минут
Дополнение графа: определение и построение

Дополнение графа: определение и построение

Как построить дополнение простого графа по рёбрам и матрице смежности, проверить число рёбер и степени вершин и использовать связь клик с независимыми множествами.

8 ноября 20269 минут
Гиперграф: что это такое и как его построить

Гиперграф: что это такое и как его построить

Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

8 ноября 20268 минут
Граф Кэли: как построить граф группы

Граф Кэли: как построить граф группы

Граф Кэли связывает операции группы с вершинами и рёбрами. Разбираем построение на вычетах по модулю 8, связность, кратчайшие пути и выбор образующих.

8 ноября 20268 минут
Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях связывает сумму степеней вершин и число рёбер графа. Разбираем доказательство, нечётные степени, петли и типовые задачи на примерах.

8 ноября 20267 минут
Рёберный граф: построение, свойства и примеры

Рёберный граф: построение, свойства и примеры

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

8 ноября 20268 минут