Что такое DAG (Directed Acyclic Graph) в контексте алгоритмов и структур данных?

DAG (Directed Acyclic Graph) — это направленный ациклический граф, фундаментальная структура данных, где:

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

Ключевые свойства и применения:

• Моделирование зависимостей: идеально подходит для представления задач с предшественниками и последователями (например, планирование проектов, компиляция с зависимостями файлов).
• Топологическая сортировка: для любого DAG существует линейное упорядочивание вершин (топологический порядок), при котором для любого ребра (u → v) вершина u идет перед v. Это основа для многих алгоритмов.
• Динамическое программирование: DAG часто представляет пространство состояний в задачах ДП, где ребро — это переход между состояниями.

Пример на Python (представление списком смежности и топологическая сортировка):

from collections import deque

class DAG:
    def __init__(self, vertices):
        self.graph = {v: [] for v in range(vertices)}
        self.in_degree = [0] * vertices

    def add_edge(self, u, v):
        """Добавляет направленное ребро от u к v."""
        self.graph[u].append(v)
        self.in_degree[v] += 1

    def topological_sort_kahn(self):
        """Алгоритм Кана для топологической сортировки."""
        result = []
        q = deque([v for v in range(len(self.in_degree)) if self.in_degree[v] == 0])

        while q:
            u = q.popleft()
            result.append(u)
            for v in self.graph[u]:
                self.in_degree[v] -= 1
                if self.in_degree[v] == 0:
                    q.append(v)

        if len(result) != len(self.graph):
            return None  # В графе есть цикл
        return result

# Пример использования
dag = DAG(6)
dag.add_edge(5, 2)
dag.add_edge(5, 0)
dag.add_edge(4, 0)
dag.add_edge(4, 1)
dag.add_edge(2, 3)
dag.add_edge(3, 1)

print("Топологический порядок:", dag.topological_sort_kahn())
# Вывод: [4, 5, 0, 2, 3, 1] или другой валидный порядок