Уровень 4. Графы и динамическое программирование

Обходы графов, кратчайшие пути, остовные деревья и первые задачи на динамическое программирование.

Два кита среднего уровня: графы (DFS, BFS, Дейкстра, остовы) и динамическое программирование. С этого уровня начинается «настоящая» олимпиадная алгоритмика — и большинство задач городских и республиканских туров. Критерий готовности к уровню 5: вы сводите текстовую задачу к графу самостоятельно и решаете простые ДП (лестница, подотрезки), объясняя, что такое состояние и переход.

В этом разделе

  1. 1
    Графы: представление, BFS и DFS

    Графы: список смежности, обход в глубину и в ширину, компоненты связности и кратчайшие пути.

  2. 2
    Кратчайшие пути: Дейкстра и Флойд

    Кратчайшие пути во взвешенном графе: Дейкстра с кучей за O(m log n) и Флойд за O(n³).

  3. 3
    Минимальное остовное дерево

    Минимальное остовное дерево: алгоритм Краскала = сортировка рёбер + DSU.

  4. 4
    Динамическое программирование: основы

    Динамическое программирование: состояния, переходы, база — лестница и максимальный подотрезок.

Доска