Минимальный остов: алгоритм Краскала на DSU

Как соединить все точки дорогами минимальной суммарной длины. Алгоритм Краскала = сортировка рёбер + DSU из раздела 3.

Минимальное остовное дерево (MST) — подмножество рёбер связного графа, соединяющее все вершины без циклов и имеющее минимальную суммарную стоимость.

Зачем это нужно

Классическая постановка: есть города и возможные дороги с ценами; нужно проложить дороги так, чтобы все города оказались связаны, а суммарная стоимость была минимальной. Прокладка сетей (электричество, интернет), кластеризация данных, приближённые решения задачи коммивояжёра — всё это MST. Алгоритм Краскала красив тем, что собирается из двух уже знакомых нам кусочков: сортировки (раздел 2) и DSU (раздел 3). Это отличный пример того, как базовые приёмы складываются в мощный алгоритм.

Идея Краскала «на пальцах»

Жадная стратегия: рассматриваем рёбра в порядке возрастания веса и добавляем ребро в остов, если оно соединяет две пока несвязанные части (иначе оно создало бы цикл и было бы лишним). Здесь и нужен DSU: он мгновенно отвечает, лежат ли концы ребра уже в одной компоненте. Берём самые дешёвые рёбра, избегая циклов, — и получаем минимальный остов. Остановиться можно, когда добавили n − 1 ребро (столько рёбер в дереве на n вершинах).

Реализация

class DSU:
    def __init__(self, n):
        self.p = list(range(n)); self.r = [0] * n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]; x = self.p[x]
        return x
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False           # уже связаны — ребро создаст цикл
        if self.r[a] < self.r[b]:
            a, b = b, a
        self.p[b] = a
        if self.r[a] == self.r[b]:
            self.r[a] += 1
        return True

n = 5
# рёбра (вес, u, v)
edges = [(1, 0, 1), (2, 0, 2), (2, 1, 2), (3, 1, 3), (4, 2, 3), (5, 3, 4)]
edges.sort()                       # по возрастанию веса (вес — первый в кортеже)

dsu = DSU(n)
total = 0
used = []
for w, u, v in edges:
    if dsu.union(u, v):            # соединили разные компоненты — берём ребро
        total += w
        used.append((u, v, w))

print("Вес MST:", total)
print("Рёбра MST:", used)

Разберём ход. Рёбра отсортированы по весу. Берём (0-1, вес 1) — соединили; (0-2, вес 2) — соединили; (1-2, вес 2) — пропускаем, 1 и 2 уже в одной компоненте (был бы цикл); (1-3, вес 3) — соединили; (2-3, вес 4) — пропускаем; (3-4, вес 5) — соединили. Итог: 4 ребра, суммарный вес 1+2+3+5 = 11. Метод union сам возвращает False, если ребро лишнее, — отсюда такая лаконичность.

Вывод:

Вес MST: 11
Рёбра MST: [(0, 1, 1), (0, 2, 2), (1, 3, 3), (3, 4, 5)]

Почему Краскал даёт минимум

Корректность опирается на свойство разреза: для любого разбиения вершин на две части минимальное по весу ребро, пересекающее границу, обязательно входит в какой-то MST. Краскал, идя от самых лёгких рёбер, всегда берёт безопасное ребро — наименьшее, соединяющее две ещё не связанные компоненты. Формально это доказывается тем же аргументом обмена, что и для жадных алгоритмов в разделе 2: если в оптимальном остове нет нашего лёгкого ребра, его можно добавить, выкинув более тяжёлое ребро образовавшегося цикла, не увеличив вес. Значит, жадный выбор безопасен.

Сложность

Доминирует сортировка. Это делает Краскал отличным выбором для разреженных графов (мало рёбер). Для плотных графов иногда удобнее алгоритм Прима на куче, но Краскал проще и его легко запомнить: «отсортируй рёбра, бери непротиворечивые через DSU».

Подводные камни

• Граф должен быть связным, иначе остова не существует (получится «остовный лес»); проверяй, что добавлено ровно n − 1 ребро.
• Вес — первым в кортеже. Чтобы sort() сортировал по весу, клади ребро как (вес, u, v).
• DSU обязателен. Без него проверка «образует ли ребро цикл» была бы дорогой; именно DSU даёт почти-константную проверку.
• MST не единственный. При равных весах остовов может быть несколько; их суммарный вес одинаков.

Итог

• MST соединяет все вершины без циклов с минимальной суммарной стоимостью рёбер.
• Краскал: отсортировать рёбра по весу и жадно добавлять те, что соединяют разные компоненты (проверка через DSU).
• Корректность — из свойства разреза и аргумента обмена; сложность O(m log m), доминирует сортировка.
• Это образцовая комбинация базовых приёмов: сортировка + система непересекающихся множеств.