Дейкстра, A*, MST, SCC — для 11 класса и олимпиад.
Глава 17 — базовые графы (степени, матрицы смежности, топсорт). Эта глава — продвинутый уровень: взвешенные графы, алгоритмы кратчайшего пути, MST, SCC, CPM. Эксклюзивные интерактивы: MST Game, Беллман-Форд визуализатор, планировщик проекта, раскраска графа.
| Глава 17 | Глава 24 |
|---|---|
| Неориентированные графы, степени | Взвешенные ориентированные графы |
| Матрица смежности (0/1) | Весовая матрица + матрица достижимости |
| DFS/BFS, связность | SCC (Тарьян), конденсация → DAG |
| Топсорт, DP на DAG | CPM, критический путь, резервы |
| Подсчёт путей (формула) | Алгоритмы кратчайшего пути |
| — | MST (Прим/Краскал), A*, Беллман-Форд |
| — | MST Game, раскраска графа |
Деревянные доски → верстак → инструменты → алмазные инструменты. Нельзя красить стены до возведения фундамента. Каждый предмет зависит от предыдущих — типичный DAG.
Коммиты образуют DAG (directed acyclic graph). Merge commits создают параллельные ветки. Топологический порядок = порядок сборки/деплоя.
Арифметика → алгебра → функции → производная. Нельзя изучать интегралы до понимания производных. Зависимости между темами — DAG.
object.o зависит от source.cpp, final.exe зависит от всех object.o. Топологический порядок определяет правильный порядок компиляции.
Задача A → задача B означает: A должна выполниться до B. Планировщик использует Kahn's algorithm для определения допустимого расписания.
Заявка → согласование → оплата. Нельзя оплатить без согласования. Каждый этап зависит от предыдущего — DAG.
6 страниц с теорией, уникальными интерактивами и банком заданий.
Построй MST по Краскалу: выбирай рёбра от лёгкого к тяжёлому. DSU показывает компоненты и циклы.
Пошаговая релаксация рёбер с поддержкой отрицательных весов и детекцией отрицательных циклов.
Интерактивный Gantt-график: меняй длительности задач, смотри как меняется критический путь и резервы.
Составь расписание экзаменов: вершины = экзамены, рёбра = конфликты студентов. Найди минимальное число слотов.
Моделирование — предыдущая глава. Графы используются для моделирования сетей и систем.
Базовые графы: степени, DFS/BFS, связность, топсорт. Основа для этой главы.
Деревья — частный случай графов (V-1 рёбер, связность, отсутствие циклов).
Деревья игры: тоже графы (minimax как DP на DAG).