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

Что минимизируют оба алгоритма

Минимальное остовное дерево соединяет все вершины связного неориентированного взвешенного графа без циклов и с минимальной суммой весов рёбер. В нём V−1 рёбер. Это задача о стоимости всей сети: она не минимизирует каждый маршрут от старта. Для несвязного графа наши реализации строят минимальный остовный лес с V−C рёбрами, где C — число компонент связности.

У Прима есть стартовая вершина. При каждом выборе он берёт минимальное ребро на границе между посещёнными и непосещёнными вершинами. У Краскала старта нет: он сортирует все рёбра по весу и принимает ребро, только если его концы лежат в разных компонентах.

Один граф, разный порядок

В исходном примере Прим начинает с A и берёт A—C (2), B—C (1), C—E (5), D—E (2). Краскал берёт B—C (1), A—C (2), D—E (2), пропускает A—B (4) из-за цикла и добавляет C—E (5). Набор выбранных рёбер одинаковый, сумма — 10.

Разница хорошо видна на третьем выборе: Прим соединяет своё растущее дерево с E ребром C—E (5). Более дешёвое D—E (2) пока не лежит на его границе. Краскал уже может взять D—E и построить отдельное дерево. Поменяйте старт Прима на D или E: его порядок изменится, проход Краскала останется прежним.

Почему оба выбора безопасны

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

Неотрицательность весов здесь не требуется. Это другая задача, чем поиск кратчайших путей Дейкстрой. Даже при отрицательных весах лес должен сохранять связность внутри исходных компонент и не содержать циклов.

Равные веса, отрицательные рёбра и несвязность

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

В примере «Отрицательные и нулевые веса» B—C имеет вес −3, D—E — 0; оба результата дают сумму 4. В несвязном примере получаются два дерева, три ребра и сумма 5. Прим после завершения компоненты начинает с первой непосещённой вершины, а Краскал продолжает соединять компоненты там, где это разрешают рёбра. Изолированная вершина тоже считается компонентой. Для одной вершины рёбра не нужны.

Как читать сравнение

Синие линии P принадлежат Приму, зелёные K — Краскалу. Если ребро выбрали оба, остаются две параллельные линии. Длинный пунктир и буква P/K обозначают текущий выбор. Остальные рёбра границы Прима показаны точками; пропущенные циклы Краскала — коротким пунктиром. Можно оставить линии только одного алгоритма, сохранив общий проход.

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

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

Сложность этих реализаций

Прим в этом примере просматривает все E рёбер для выбора минимума на границе, а также в конце каждой компоненты: время O(VE+V), рабочая память O(V+E) с учётом проверки и копирования графа. Реализация с кучей и списками смежности может дать O(E log V) для связного графа; такой вариант в этом плеере не используется.

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

История визуализации требует дополнительной памяти. Прим копирует выбранные рёбра, посещённые вершины и границу для каждого кадра; Краскал — выбранные и пропущенные рёбра, метки компонент. Сравнение повторно использует неизменяемые снимки обеих моделей. При P и K записанных кадрах безопасная оценка истории — O((P+K)(V+E)); это отдельно от рабочей памяти алгоритмов.

Исполняемый код

Ниже те же функции получения результата, что в отдельных статьях о Приме и Краскале. Индексы рёбер соответствуют входному массиву. Плеер дополняет вычисление неизменяемыми снимками и объединяет фазы проверки и решения для наглядности; другая реализация поиска остова для сравнения не создаётся.

function prim(n, edges, start = 0) {
  if (!Number.isInteger(n) || n < 1 || !Number.isInteger(start) ||
      start < 0 || start >= n || !Array.isArray(edges)) throw Error("Invalid graph");
  const valid = v => Number.isInteger(v) && v >= 0 && v < n;
  let bound = 0;
  for (const e of edges) {
    if (!e || !valid(e.from) || !valid(e.to) || e.from === e.to ||
        !Number.isSafeInteger(e.weight)) throw Error("Invalid edge");
    bound += Math.abs(e.weight);
    if (!Number.isSafeInteger(bound)) throw Error("Unsafe weight sum");
  }
  const seen = Array(n).fill(false), selected = [];
  let weight = 0, components = 0;
  const roots = [start, ...Array.from({length: n}, (_, i) => i).filter(i => i !== start)];
  for (const root of roots) {
    if (seen[root]) continue;
    seen[root] = true;
    components++;
    while (true) {
      let best = -1;
      for (let i = 0; i < edges.length; i++) {
        const e = edges[i];
        if (seen[e.from] === seen[e.to]) continue;
        if (best === -1 || e.weight < edges[best].weight) best = i;
      }
      if (best === -1) break;
      const e = edges[best];
      seen[e.from] = seen[e.to] = true;
      selected.push(best);
      weight += e.weight;
    }
  }
  return { edges: selected, weight, components };
}

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 };
}