Алгоритм Краскала: минимальное остовное дерево

Сеть с минимальной суммой весов

Остовное дерево включает все вершины связного неориентированного графа и не содержит циклов. Для V вершин в нём V−1 рёбер. Минимальное остовное дерево минимизирует сумму их весов; пути от какой-либо вершины при этом не обязаны быть кратчайшими.

У Краскала нет стартовой вершины. Сначала каждая вершина — отдельная компонента, включая изолированные вершины. Добавленное ребро соединяет две компоненты. Если исходный граф несвязный, получаем минимальный остовный лес — по дереву на каждую компоненту связности.

Сортируем все рёбра и пропускаем циклы

Сортируем все рёбра по весу и рассматриваем их в этом порядке. Если концы ребра находятся в разных компонентах, берём ребро и объединяем компоненты. Если в одной — пропускаем: в выбранном лесе между ними уже есть путь, поэтому новое ребро замкнуло бы цикл.

При равных весах плеер использует исходный индекс ребра. Так запуск воспроизводится; другой порядок равных рёбер может дать другое минимальное дерево с той же суммой. Как только остаётся одна компонента, дерево готово: остальные рёбра помечаются ненужными, а не отклонёнными. Если компонент несколько, идём до конца списка рёбер.

Тот же граф, что у Прима, другой порядок

В исходном примере порядок такой: B—C = 1, A—C = 2, D—E = 2, A—B = 4, C—E = 5, B—D = 7, C—D = 8. Берём B—C, затем A—C. Следом берём D—E и получаем отдельное маленькое дерево. Краскал может одновременно строить несколько деревьев.

Пропускаем A—B = 4: A и B уже связаны через C. Ребро C—E = 5 объединяет два дерева. Итог — четыре ребра с суммой 1 + 2 + 2 + 5 = 10. Оставшиеся рёбра проверять не нужно. Прим на этом графе начинает с A и выбирает A—C, C—B, C—E, E—D; минимальная сумма у обоих алгоритмов одинакова.

Как узнать, связаны ли две вершины

Система непересекающихся множеств, или DSU, хранит каждую компоненту как дерево родительских ссылок. Операция find(v) идёт по этим ссылкам к представителю. Одинаковые представители означают, что вершины уже связаны. Если представители разные, union подвешивает меньшее дерево к большему.

В реализации есть и сжатие путей: во время поиска вершина перенаправляется к родителю своего родителя. Родительские ссылки DSU — вспомогательные данные, а не рёбра исходного графа или остова. Группы под графом перечисляют действительно связанные вершины; подпись группы определяется минимальным индексом вершины, а не корнем DSU.

Почему это ребро можно брать

Выбранные рёбра образуют лес, который можно дополнить до минимального остовного леса. Для ребра между двумя текущими компонентами рассмотрим разрез: одна компонента с одной стороны, все остальные вершины — с другой. Более лёгкого необработанного ребра через этот разрез нет; уже обработанное ребро через него объединило бы компоненты раньше. Значит, выбранное ребро имеет минимальный вес на этом разрезе.

Возьмём минимальный лес со всеми уже выбранными рёбрами. Если нового ребра в нём нет, его добавление создаст цикл с другим ребром через тот же разрез. Другое ребро не легче: заменяем его новым и сохраняем минимальный лес. Каждое объединение уменьшает число компонент на единицу, поэтому на любом этапе выбрано рёбер = V − текущее число компонент.

Отрицательные веса и несвязный граф

Нулевые и отрицательные веса допустимы: сравниваем веса самих рёбер, а не предварительные стоимости маршрутов. Циклов в лесе всё равно быть не должно, даже если все рёбра цикла отрицательные. При равных весах минимальный лес может быть не единственным.

В отрицательном примере вес B—C меняется на −3, а D—E — на ноль; итоговая сумма равна четырём. В несвязном примере есть группы A,B,C и D,E: две компоненты, три ребра, сумма пять. Единственная изолированная вершина уже является деревом с весом ноль.

Как читать плеер и управлять примером

Зелёные рёбра образуют выбранный лес. Жёлтым выделены проверяемое ребро и его концы. Пропущенное ребро цикла показано пунктиром. Карточки отсортированы по весу и содержат статус каждого ребра; группы под графом показывают уже связанные вершины. Проверка ребра и решение взять или пропустить его — отдельные этапы. Счётчик учитывает проверенные рёбра, без сравнений при сортировке и внутренних операций DSU.

Меняйте пример или вес ребра. Ошибочный ввод сохраняет текущий корректный запуск. Плеер принимает 1–8 вершин с уникальными подписями, до 28 рёбер без петель и повторных неупорядоченных пар, целые веса от −99 до 99. Ноль — вес ребра, а не его отсутствие. Общие кнопки позволяют шагать, перематывать, менять скорость, развернуть плеер, поделиться чистой страницей на паузе и сохранить немое видео.

Стоимость алгоритма и сохранённая история

При сортировке сравнениями за O(E log(E+1)) упорядочивание рёбер занимает O(E log(E+1)), создание DSU — O(V), а все поиски и объединения вместе — O(E α(V)) амортизированно, благодаря объединению по размеру и сжатию путей. Здесь α — очень медленно растущая обратная функция Аккермана. Рабочая память — O(V+E) для DSU и копии порядка рёбер без учёта входа. Ранняя остановка не отменяет начальную сортировку.

Визуализация дополнительно хранит O(E+1) неизменяемых снимков групп, принятых и отклонённых рёбер: O((E+1)(V+E)) памяти истории. Группы для показа вычисляются по родительским деревьям без изменения DSU: это добавляет до O((E+1)V log(V+1)) работы, а также копирование снимков. Эти расходы интерфейса отделены от оценки алгоритма. Длительность анимации объясняет выбор и не измеряет быстродействие вычислений.

Реализация на JavaScript

Функция возвращает исходные индексы рёбер, сумму весов и итоговое число компонент без истории анимации. Порядок равных рёбер, DSU и ранняя остановка совпадают с плеером. Вершины нумеруются от нуля до n−1. Безопасные целые веса и сумма их модулей проверяются для защиты от переполнения; исходный список рёбер не изменяется.

function kruskal(n, edges) {
    if (!Number.isInteger(n) || n < 1 || !Array.isArray(edges))
        throw new RangeError("Invalid graph");
    let budget = 0;
    const pairs = new Set();
    for (const e of edges) {
        if (!e || !Number.isInteger(e.from) || !Number.isInteger(e.to) ||
            e.from < 0 || e.from >= n || e.to < 0 || e.to >= n ||
            e.from === e.to || !Number.isSafeInteger(e.weight))
            throw new RangeError("Invalid edge");
        const key = [e.from, e.to].sort((a, b) => a - b).join(":");
        if (pairs.has(key)) throw new RangeError("Duplicate edge");
        pairs.add(key);
        budget += Math.abs(e.weight);
        if (!Number.isSafeInteger(budget)) throw new RangeError("Unsafe sum");
    }
    const order = edges.map((_, id) => id)
        .sort((a, b) => edges[a].weight - edges[b].weight || a - b);
    const parent = Array.from({ length: n }, (_, i) => i);
    const size = Array(n).fill(1);
    function find(v) {
        while (v !== parent[v]) {
            parent[v] = parent[parent[v]];
            v = parent[v];
        }
        return v;
    }
    const selected = [];
    let weight = 0, components = n;
    for (const id of order) {
        if (components === 1) break;
        const e = edges[id];
        let a = find(e.from), b = find(e.to);
        if (a === b) continue;
        if (size[a] < size[b]) [a, b] = [b, a];
        parent[b] = a;
        size[a] += size[b];
        selected.push(id);
        weight += e.weight;
        components--;
    }
    return { edges: selected, weight, components };
}