Подсчёт путей в ДАГ

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 16 · страница 16.3
Подсчёт путей в ДАГ
Топологическая сортировка + динамическое программирование.
ДАГ (DAG)
— ориентированный граф без циклов. Главное свойство: можно топологически отсортировать вершины. На этом основан алгоритм подсчёта путей за O(V+E).
ФГОС
ФОП
ОГЭ №9
ЕГЭ №1
01
ДАГ и его свойства
Определение
ДАГ (Directed Acyclic Graph)
— ориентированный граф, в котором нет циклов.
Топологическая сортировка
— линейное упорядочивание вершин, в котором каждое ребро u→v идёт «вперёд» (u раньше v).
Существует тогда и только тогда, когда граф — ДАГ.
Где встречается
Сборка проекта:
make-файлы, package.json — порядок сборки.
Планировщик задач:
какие задачи зависят от других.
Git:
история коммитов (DAG, не цепочка).
Нейросети:
вычислительный граф операций.
Криптовалюты:
блокчейн (DAG, не цепочка — IOTA, Nano).
Пример ДАГ (6 вершин)
Рёбра: 1→2, 1→3, 2→4, 2→5, 3→5, 4→6, 5→6.
Топсорт: 1, 2, 3, 4, 5, 6 (один из вариантов).
02
Алгоритм подсчёта путей
Метод динамического программирования
Пусть
dp[v]
— число путей от стартовой вершины s до v.
База:
dp[s] = 1 (путь из одной вершины в саму себя).
Переход:
dp[v] = Σ dp[u] для всех рёбер (u → v).
Порядок обхода:
топологическая сортировка (сначала предки, потом потомки).
Сложность:
O(V + E).
📊
Симулятор: подсчёт путей в ДАГ
Старт
Финиш
03
Мини-тест
📝
6 вопросов по ДАГ