Граф описывает связи, дерево — частный случай графа без циклов. Динамическое программирование решает задачу, сохраняя ответы подзадач, — и тем превращает перебор в линейный проход.
Что нужно знать
- Граф задаётся вершинами и рёбрами; рёбра бывают направленными и взвешенными.
- Способы хранения: матрица смежности (быстрая проверка связи) и список смежности (экономнее для разреженных графов).
- Дерево — связный граф без циклов; у корневого дерева есть корень, узлы и листья.
- Обход в глубину использует стек или рекурсию, обход в ширину — очередь.
- Обход в ширину находит кратчайший путь в невзвешенном графе; для взвешенного нужен алгоритм Дейкстры.
- Динамическое программирование применимо, когда задача разбивается на перекрывающиеся подзадачи.
- Ответы подзадач сохраняют в таблице и переиспользуют, вместо того чтобы считать заново.
Где чаще всего ошибаются
- Ищут кратчайший путь обходом в глубину — он найдёт какой-нибудь путь, но не обязательно короткий.
- Применяют обход в ширину к взвешенному графу и получают неверный ответ.
- Не помечают посещённые вершины и зацикливаются.
- Пишут рекурсию без сохранения результатов и получают экспоненциальное время вместо линейного.
Проверить себя
По этой же главе есть проверочная работа из 11 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Информатика · 11 класс · Поляков, 2023 · Глава 7 · Деревья, графы и динамическое программирование