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

Ориентированный ациклический граф, или DAG, помогает описать зависимости, которые нельзя обойти по кругу. Например, перед сборкой программы нужно подготовить компоненты, а перед проверкой сборки - собрать её. Граф показывает эти ограничения стрелками и позволяет понять, какие действия можно выполнять одновременно. Ниже разберём определение, свойства и пример расчёта сроков. В интерактиве можно изменить длительность одной работы и увидеть, когда она начинает влиять на весь проект.
Что означает DAG
Ориентированный ациклический граф - это ориентированный граф без направленных циклов. Сокращение DAG происходит от английского directed acyclic graph. Граф состоит из множества вершин и множества направленных рёбер . Стрелка связывает две вершины в определённом направлении: перейти по ней можно от к , но обратное движение требует отдельной стрелки.
Направленный путь проходит по стрелкам последовательно. Направленный цикл возвращает путь к его исходной вершине, двигаясь только по направлению рёбер. Петля тоже является циклом. В DAG таких замкнутых маршрутов нет. Это определение и связь с топологическим порядком приводятся в материалах MIT по алгоритмам.
Отсутствие направленного цикла не означает, что на рисунке нельзя найти замкнутый контур, если игнорировать стрелки. В примере ниже А, Б, Г, В образуют такой контур, но все стрелки ведут от А к Г, а не обратно. Поэтому граф остаётся ациклическим.
Как читать вершины, рёбра и пути
Возьмём пять работ А, Б, В, Г и Д. Пусть стрелка означает «первая работа должна закончиться до начала второй». Связи заданы так:
У А нет входящих рёбер: это источник. У Д нет исходящих рёбер: это сток. Источников и стоков в графе может быть несколько; изолированная вершина одновременно обладает обоими свойствами. Степень входа вершины - число входящих в неё рёбер, степень выхода - число исходящих. Для Г они равны соответственно двум и одному.
Из А можно добраться до Д, например по пути А→В→Г→Д. Поэтому Д достижима из А, хотя прямой стрелки А→Д нет. Б и В между собой путём не связаны: после завершения А их зависимости разрешают выполнять параллельно. При этом отсутствие пути само по себе не обещает, что ресурсов хватит на одновременную работу.
Рисунок - лишь представление структуры: вершины можно переставить на листе, а стрелки могут пересекаться. Важно не расположение точек, а то, какие пары соединены и куда направлены рёбра. Для хранения используют, например, списки исходящих соседей: у А это Б и В, у Г - только Д. Такое представление занимает памяти.
Почему порядок работ существует
Для конечного DAG существует топологический порядок: такая последовательность всех вершин, в которой начало каждого ребра стоит раньше его конца. В нашем примере подходят и А, Б, В, Г, Д, и А, В, Б, Г, Д. Положение Б и В можно поменять, поскольку ни одна не зависит от другой. Порядок задаёт допустимую последовательность, но сам по себе не указывает время начала или длительность работ.
Почему такой порядок возможен? В непустом конечном DAG найдётся вершина без входящих рёбер. Если бы у каждой был предшественник, можно было бы бесконечно идти назад по стрелкам. В конечном наборе вершин одна повторилась бы, и возник бы направленный цикл. Удалив источник и его рёбра, получаем меньший DAG; повторяя действие, получаем порядок всех вершин.
Обратно, при наличии цикла каждая его вершина должна стоять раньше следующей, а последняя - раньше первой. Это невозможно. Таким образом, конечный орграф имеет топологический порядок тогда и только тогда, когда он ацикличен. Пошаговое построение очередью и вариант через DFS разобраны отдельно в статье о топологической сортировке.
Как проверить граф на цикл
Один способ - последовательно удалять вершины с нулевой степенью входа. Если удалены все вершины, граф ацикличен. Если процесс остановился раньше, в оставшейся части есть цикл. Важно: остаток может включать и вершины, которые сами не лежат на цикле, но зависят от него; считать каждую из них участником цикла нельзя.
Другой способ использует обход в глубину. Вершина бывает ещё не посещённой, находящейся в текущем стеке обхода или полностью обработанной. Ребро к вершине текущего стека обнаруживает направленный цикл: от неё уже идёт путь к текущей вершине, а новое ребро замыкает его. Для полного ответа обход запускают также из ещё не посещённых вершин, чтобы проверить все компоненты графа.
При списках смежности оба подхода работают за времени. Если нужен сам цикл, сохраняют предков обхода и восстанавливают путь по ним. Проверка только одной произвольной цепочки недостаточна: цикл может находиться в другой ветви или компоненте.
Пример: ранние сроки и критический путь
Пусть длительности А, Б, В, Г, Д равны 2, 3, 4, 2 и 1 единице времени. Работы без взаимной зависимости могут идти одновременно, ресурсов достаточно, задержек между работами нет. Старт проекта - момент 0. Раннее начало работы равно максимуму ранних окончаний её непосредственных предшественников; для источника оно равно нулю. Раннее окончание - начало плюс длительность.
| Работа | Предшественники | Раннее начало | Раннее окончание |
|---|---|---|---|
| А | нет | 0 | 2 |
| Б | А | 2 | 5 |
| В | А | 2 | 6 |
| Г | Б, В | 6 | 8 |
| Д | Г | 8 | 9 |

Г не может начаться в момент 5, хотя Б уже закончена: нужно дождаться и В до момента 6. Самая длинная по сумме длительностей цепочка А→В→Г→Д занимает . Это критический путь для данной модели; другая ветвь занимает . Минимальный срок проекта при сделанных предположениях равен 9. Метод длиннейшего пути в DAG лежит и в основе реализации CPM Принстонского университета.
В интерактиве длительность В можно менять от 1 до 6. При значении 3 обе ветви занимают по 8 и становятся критическими; при значении меньше 3 критична ветвь через Б, при большем - через В. Это не прогноз реального проекта: ограничение числа работников, выходные и задержки передачи здесь не учтены. О ранних и поздних сроках с резервами подробнее рассказано в статье о сетевом планировании.
Где ещё применяется DAG
В системе сборки вершинами могут быть файлы или задачи, а стрелками - зависимости между ними. Изменение исходного файла заставляет пересчитать достижимые от него результаты. В конвейере данных узлы представляют преобразования, а стрелки - передачу результата дальше. DAG также моделирует зависимости курсов, формулы таблиц и историю версий с объединением ветвей.
Ещё одно применение - поиск путей во взвешенном графе. Если обработать вершины в топологическом порядке, к моменту обработки все возможные предшественники уже рассмотрены. Это позволяет находить кратчайшие или длиннейшие пути от источника за даже при отрицательных весах рёбер; недостижимые вершины нужно обрабатывать отдельно. Такой подход описан в курсе алгоритмов Принстонского университета. Для невзвешенного графа другую задачу - путь с минимальным числом рёбер - решает обход в ширину.
Модель полезна лишь при корректной семантике стрелки. Если процессы действительно допускают повторную обратную связь, искусственное удаление цикла исказит систему. Иногда достаточно развернуть повторения во времени и представить каждую итерацию отдельными вершинами, но сначала необходимо определить границы модели.
Частые ошибки
- Игнорировать направление рёбер. Замкнутый контур на рисунке не обязательно является направленным циклом.
- Путать ребро с путём. Достижимость может обеспечиваться несколькими стрелками без прямой связи.
- Считать топологический порядок единственным. Независимые вершины нередко можно переставлять.
- Принимать порядок за расписание. Длительности и ограничения ресурсов требуют дополнительного расчёта.
- Проверять только связную часть. Цикл может скрываться в другой компоненте.
FAQ
Может ли DAG содержать несколько источников?
Да. Любые вершины без входящих рёбер являются источниками; конечный непустой DAG имеет хотя бы один источник и хотя бы один сток.
Является ли дерево DAG?
Дерево без направлений ещё не является ориентированным графом. Если назначить направление каждому его ребру, получится DAG: в исходном дереве нет даже неориентированного цикла. Но не каждый DAG является деревом: в нём могут сходиться несколько путей.
Может ли DAG содержать отрицательные веса?
Да. Ацикличность относится к направлению связей, а не к значениям весов. Их смысл зависит от модели: отрицательная стоимость возможна в задаче путей, но отрицательная длительность работы обычно не подходит для расписания.
Коротко
DAG - ориентированный граф без направленных циклов. Его вершины можно упорядочить так, чтобы каждая стрелка вела вперёд. Это позволяет проверять зависимости, находить достижимость и вычислять пути или сроки в порядке предшествования. Для расписания дополнительно нужны длительности и явные предположения о ресурсах.
Читайте также

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

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

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

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

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

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