- Ациклический граф (DAG) – граф, в котором нет циклов (невозможно, выйдя из вершины, вернуться в неё, двигаясь по стрелкам).
Пример. Посчитайте количество путей из вершины start в вершину end в ориентированном ациклическом графе (DAG) с помощью динамического программирования.
- Инициализация. Создать массив dp, где dp [u] – количество путей из вершины u в end.
- Базовый случай. dp [end] = 1.
- Рекуррентность. Для всех вершин u (в обратном топологическом порядке): dp [u] = сумма dp [v] для всех v таких, что есть ребро u → v.
- Ответ. dp [start].
- Ключевые моменты:
- Граф без циклов → порядок обхода важен.
- Эффективно использовать топологическую сортировку.
- Сложность: O (N + M), где N – число вершин, M – рёбер.
Информатика • 11 класс
7
Количество различных путей между вершинами ориентированного ациклического графа (C++)
Было полезно?
Рекомендуем
Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках