Подсчёт путей в ациклическом графе
В ориентированном ациклическом графе нет направленных циклов.
В этом занятии
- Самостоятельно решить задачу по теме «Подсчёт путей в ациклическом графе» и объяснить проверку результата.
- Построй карту из пяти этапов проекта без возвратов. Сравни число маршрутов до финиша до и после добавления одной разрешённой стрелки.
Пригодится: informatics11-weighted-graphs
Разберёмся перед практикой+
Подсчёт путей в ациклическом графе
В ориентированном ациклическом графе нет направленных циклов. Число путей от стартовой вершины можно накапливать: для каждой вершины складывают числа путей ко всем её непосредственным предшественникам. В стартовой вершине принимают одно пустое начало пути.
Вершины обрабатывают в порядке, где предшественники уже посчитаны. Для графа с циклами такая процедура без дополнительных ограничений не подходит: повторные обходы могут дать бесконечно много маршрутов. Условия «через вершину» и «без вершины» меняют набор разрешённых путей.
Рёбра A→B, A→C, B→D, C→D. В B и C приходит по одному пути, в D — 1+1=2. Других рёбер и циклов нет.
- Проверь отсутствие циклов и задай старт.
- Суммируй значения предшественников в допустимом порядке.
Открываем цифровую мастерскую…
Попробуйте самостоятельно
Запишите рассуждения в черновик или сделайте построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Построй карту из пяти этапов проекта без возвратов. Сравни число маршрутов до финиша до и после добавления одной разрешённой стрелки.
- Сначала предположите результат, затем проверьте и объясните, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.