Прим и Крускал: два способа выбрать разрез

Если ты помнишь оба алгоритма, их цену и то, какой разрез каждый из них использует, листай до «Теперь сам».

Как думаешь, чем они отличаются по сути

Оба алгоритма жадные, оба правильные, оба строят одно и то же дерево. Прежде чем читать дальше, сформулируй отличие не в коде, а в стратегии: что у каждого из них всегда связно по ходу работы - и что это даёт?

На что это похоже

Два способа проложить сеть дорог. Первый: начать с одного города и каждый раз пристраивать самый дешёвый отрезок до ещё не подключённого - сеть всё время остаётся единой. Второй: составить список всех возможных дорог от дешёвых к дорогим и строить подряд те, что соединяют ещё не связанные куски, - до самого конца у тебя несколько отдельных сетей, которые сливаются в одну лишь в финале.

Механизм: два алгоритма рядом

Данные и обозначения в обоих листингах одни: V - число вершин, adj[v] - список пар «сосед, вес», edges - список тройек (u, v, w), INF - заведомо большое число, DSU - класс union-find из раздела про непересекающиеся множества (find и union), heapq - куча из стандартной библиотеки. Возвращают функции ВЕС дерева; как получить сами рёбра, сказано сразу после.

# ПРИМ: растим одно дерево, приоритет - вес РЕБРА
def prim(start):
    best = [INF] * V; best[start] = 0     # самое лёгкое ребро до дерева
    used = [False] * V
    q = [(0, start)]
    total = 0
    while q:
        w, v = heapq.heappop(q)
        if used[v]:
            continue
        used[v] = True; total += w        # ребро принято в дерево
        for u, wt in adj[v]:
            if not used[u] and wt < best[u]:
                best[u] = wt
                heapq.heappush(q, (wt, u))
    return total

# КРУСКАЛ: сортируем рёбра, соединяем непересекающиеся множества
def kruskal():
    edges.sort(key=lambda e: e[2])        # по весу
    dsu = DSU(V)                          # union-find из раздела про кучи
    total = 0
    for (u, v, w) in edges:
        if dsu.find(u) != dsu.find(v):    # концы в разных компонентах
            dsu.union(u, v)
            total += w
    return total

edges.sort(key=lambda e: e[2]) - это «отсортировать по третьему элементу тройки»: e здесь одно ребро (u, v, w), значит e[2] - его вес, а lambda e: e[2] - короткая запись функции «дай мне вес этого ребра», по которой сортировка и сравнивает элементы.

Сами рёбра дерева, а не только вес, получаются одной строкой: там, где стоит total += w, добавь tree.append((u, v, w)) (у Прима придётся положить в кучу тройку (wt, u, v) - вес, куда идём и откуда, - и дописывать ребро при его приёме). Это та же разница, что между dist и prev в кратчайших путях: длину дают числа, маршрут - запоминание выбора.

Разница в одной строчке приоритета, но следствия разные:

Правило

Прим: растить дерево, каждым шагом добавляя самое лёгкое ребро наружу; O((V + E)·log V) на куче, O(V²) перебором на плотном графе. Крускал: отсортировать рёбра по весу и брать каждое, если его концы в разных компонентах (проверка - union-find); O(E·log E), почти вся цена - сортировка. Оба корректны по свойству разреза: у Прима разрез «дерево против остального», у Крускала - «компонента конца ребра против остального». При различных весах оба строят ОДНО И ТО ЖЕ дерево.

Разбор: строим МОД обоими способами

Граф: a-b = 4, a-c = 1, b-c = 2, b-d = 5, c-d = 3.

Прим из a. В дереве {a}. Рёбра наружу: a-b (4), a-c (1). Берём a-c (1), дерево {a, c}. Рёбра наружу: a-b (4), b-c (2), c-d (3). Берём b-c (2), дерево {a, b, c}. Рёбра наружу: b-d (5), c-d (3). Берём c-d (3). Все вершины в дереве, итог: рёбра a-c, b-c, c-d, вес 1 + 2 + 3 = 6.

Крускал. Сортировка: a-c (1), b-c (2), c-d (3), a-b (4), b-d (5). a-c: a и c в разных множествах - берём, объединяем. b-c: b и {a,c} - разные - берём. c-d: d и {a,b,c} - разные - берём. Уже три ребра при четырёх вершинах, дерево готово. a-b: концы в одном множестве - пропускаем. b-d: тоже - пропускаем. Итог тот же: вес 6, те же рёбра.

Обрати внимание на порядок ДОБАВЛЕНИЯ: у Прима он был a-c, b-c, c-d - и дерево всё время оставалось связным. У Крускала порядок совпал случайно; на другом графе он брал бы рёбра из разных концов графа, и до конца работы куски были бы разрозненными.

Разбор: почему Крускалу нужен именно union-find

Крускал обязан быстро отвечать на вопрос «эти две вершины уже связаны?» - по одному разу на каждое ребро, то есть E раз. Наивная проверка (запустить обход и посмотреть, достижим ли второй конец) стоила бы O(V + E) за раз, и весь алгоритм превратился бы в O(E·(V + E)).

Структура непересекающихся множеств из раздела про кучи отвечает за почти константу: find с ранговым объединением и сжатием пути - O(α(V)), практически 4 операции. Поэтому вся цена Крускала сводится к сортировке: O(E·log E), а проверки связности добавляют лишь O(E·α(V)).

Отсюда и практические следствия. Если рёбра уже отсортированы (например, приходят из базы в нужном порядке) или их веса - маленькие целые (тогда сортировка линейная, подсчётом), Крускал становится почти линейным. А на плотном графе, где E ≈ V², сортировка V²·log V проигрывает приму с перебором массива за V² - там берут Прима.

Что ломается без этого

Первое, у Прима: сравнивать dist вместо веса ребра - получится Дейкстра, а она строит дерево кратчайших путей, а НЕ минимальное остовное. Это разные деревья, и их путают постоянно. Второе, у Прима: забыть проверку if used[v]: continue при извлечении - вершина обработается повторно, и в сумму попадут лишние рёбра. Третье, у Крускала: проверять связность обходом вместо union-find - алгоритм станет квадратичным. Четвёртое, у обоих: не заметить, что граф несвязен - Прим построит дерево только своей компоненты, Крускал честно выдаст лес; если ожидалось дерево, проверь число взятых рёбер: их должно быть ровно V − 1. Пятое: сортировать рёбра, но сравнивать их по номеру вершины вместо веса - ошибка глупая, но молчащая: дерево получится, просто не минимальное.

Зачем это в работе

Прим удобен, когда граф плотный или задан матрицей (расстояния между всеми точками) - например, при прокладке связей между всеми офисами. Крускал - когда рёбра уже есть списком и их сравнительно немного: сети, дороги, связи в данных; он же естественно ложится на потоковую обработку и на внешнюю сортировку, если рёбер слишком много для памяти. Отдельно стоит запомнить трюк кластеризации: построй МОД и выбрось k − 1 самых тяжёлых рёбер - получишь k кластеров, а это ровно то, что делает Крускал, если остановить его пораньше. И самое частое практическое недоразумение: МОД - это не дерево кратчайших путей. Если нужна «дешёвая сеть» - МОД; если нужно «быстро добираться из центра» - Дейкстра.

Теперь сам

Граф: 1-2 = 3, 1-3 = 1, 2-3 = 3, 2-4 = 6, 3-4 = 5, 3-5 = 4, 4-5 = 2. Построй МОД Крускалом, выпиши порядок взятых рёбер и суммарный вес. Сколько рёбер будет пропущено?