Минимальное остовное дерево
Минимальное остовное дерево: алгоритм Краскала = сортировка рёбер + DSU.
Задача: соединить все n городов дорогами минимальной суммарной стоимости. Ответ всегда — дерево из n-1 ребра (лишнее ребро в цикле можно выбросить), оно называется минимальным остовным деревом (MST).
Алгоритм Краскала — жадность, которая доказуемо работает:
1. Отсортировать рёбра по весу.
2. Идти от дешёвых к дорогим; ребро брать, если оно соединяет РАЗНЫЕ компоненты.
3. «Разные ли компоненты» проверяет DSU из прошлого уровня — вот где он стреляет!
Сложность: O(m log m) на сортировку, DSU почти бесплатен.
Краскал. Введите: 4 5, затем рёбра: 1 2 1, 2 3 2, 3 4 5, 1 3 2, 2 4 4
На примере: рёбра по возрастанию весов 1, 2, 2, 4, 5. Берём 1-2 (вес 1), берём 2-3 (вес 2), ребро 1-3 пропускаем (уже в одной компоненте), берём 2-4 (вес 4). Итог: 1 + 2 + 4 = 7.
Почему жадность верна: самое дешёвое ребро через любой «разрез» графа обязательно лежит в каком-нибудь MST (если нет — добавьте его, в цикле появится более дорогое ребро через тот же разрез, выбросите его — стало не хуже). Это то же обменное рассуждение из урока про жадные.
Существует и алгоритм Прима (растим дерево от вершины, как Дейкстру) — тот же результат, другой стиль.
Задание: измените программу, чтобы она печатала не только вес, но и сами рёбра остова.
Отметьте урок пройденным и переходите к главной теме уровня — динамическому программированию.