Графы описывают дороги, сети и связи. Обходы находят пути, Дейкстра — кратчайший путь по весам, жадные алгоритмы и динамическое программирование решают задачи оптимизации — каждый со своими условиями применимости.
Что нужно знать
- Граф: вершины и рёбра; ориентированный, взвешенный.
- Матрица смежности — $V^2$ памяти; списки смежности — $V + E$, лучше для разреженных графов.
- BFS (в ширину, очередь) находит кратчайший путь по числу рёбер; DFS (в глубину, стек или рекурсия) — для обхода и поиска компонент.
- Дейкстра — кратчайшие пути при неотрицательных весах.
- Жадный алгоритм делает локально лучший выбор; верен не всегда (сдача монетами 1, 3, 4 для суммы 6).
- ДП: подзадачи → рекуррентное соотношение → таблица значений.
- Число путей в клетку: $f(i, j) = f(i-1, j) + f(i, j-1)$; «лесенка»: $f(n) = f(n-1) + f(n-2)$.
- НОД — алгоритм Евклида: $\gcd(a, b) = \gcd(b, a \bmod b)$.
Где чаще всего ошибаются
- Применять Дейкстру к графу с отрицательными весами.
- Доверять жадному алгоритму без доказательства.
- Искать кратчайший путь по весам обходом в ширину.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 30 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Программирование (ИТ-класс) · 10–11 классы · Графы, жадные алгоритмы и динамическое программирование