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