Как ответить
DAG — это ориентированный граф без циклов. На практике это значит, что у нас есть вершины (узлы) и направленные рёбра, идя по которым, ты никогда не вернёшься в исходную точку. Это ключевое свойство, которое делает DAG удобным для моделирования зависимостей.
Основное применение в разработке — это планирование и выполнение задач с зависимостями. Самый частый пример — системы сборки и CI/CD пайплайны. В GitLab CI или GitHub Actions каждый job — это вершина, а needs или depends_on — это рёбра. Пайплайн не запустит тесты, пока не соберётся бинарник, и не выкатит в прод, пока тесты не пройдут. DAG гарантирует, что порядок выполнения корректен и нет взаимных блокировок.
Второй большой класс — это обработка данных. Apache Airflow, Spark, dbt — все они строят DAG из тасков. Например, в Airflow DAG описывает последовательность: выгрузить данные из API → почистить → агрегировать → записать в ClickHouse. Если один таск упадёт, DAG перезапустит только его и зависимые, не трогая уже выполненное.
Третий пример — системы контроля версий. Git history — это DAG из коммитов. Каждый коммит ссылается на родительский (или несколько при merge), и это направленный граф без циклов. Именно поэтому Git может эффективно вычислять diff и merge.
Из алгоритмов: топологическая сортировка — это способ получить линейный порядок вершин DAG, где все рёбра идут слева направо. Она используется в планировщиках задач, чтобы понять, что запускать первым. Сложность — O(V+E).
Важный нюанс: если в графе появляется цикл, планировщик не сможет определить порядок выполнения. В Airflow, например, при старте DAG проверяется на ацикличность, и если цикл найден — DAG не запускается с ошибкой.
Ещё одно применение — блокчейны. Bitcoin и Ethereum используют DAG для хранения транзакций (хотя там есть и fork'и, которые временно создают циклы, но протокол их разрешает). Некоторые проекты вроде IOTA полностью построены на DAG вместо классической цепочки блоков.
Из структур данных: DAG можно реализовать через список смежности или матрицу смежности. Для больших графов (миллионы вершин) используют adjacency list с хеш-таблицами для быстрого поиска рёбер.