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

Сеть связей, а не маршрут

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

Старт определяет порядок роста. При равных весах другой старт может дать другое минимальное дерево с той же суммой. В несвязном графе единого остовного дерева нет; плеер строит минимальный остовный лес — по дереву для каждой компоненты связности, включая отдельные изолированные вершины.

Выбор на всей границе дерева

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

Это не движение только от последней добавленной вершины. Все рёбра границы конкурируют одновременно. Реализация просматривает исходный список рёбер и при равенстве оставляет первое минимальное. Другое столь же лёгкое ребро тоже допустимо; правило разрешения равенства делает демонстрацию воспроизводимой.

Пять вершин и сумма десять

От A сравниваем A—B = 4 и A—C = 2. Добавляем A—C. Теперь на границе A—B = 4, C—B = 1, C—D = 8 и C—E = 5. Выбираем C—B = 1, хотя B присоединяется не напрямую к старту.

Дальше добавляем C—E = 5, хотя последней добавили B: конкурируют все рёбра границы, в том числе из C. Затем берём E—D = 2. В результате четыре ребра и сумма 2 + 1 + 5 + 2 = 10. Ребро D—E = 2 было дешёвым с самого начала, но оба его конца находились снаружи. Веса добавляемых рёбер не обязаны идти по возрастанию.

Почему локальный выбор безопасен

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

Значит, по-прежнему существует минимальное дерево со всеми выбранными рёбрами. На каждом шаге присоединяем новую вершину, поэтому цикл не появляется. Когда рёбер через границу нет, текущая компонента включена целиком; следующая неотмеченная вершина начинает новую компоненту. В итоговом лесе V−C рёбер, где C — число компонент связности.

Равные, нулевые и отрицательные веса

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

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

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

Зелёные рёбра и вершины уже входят в остов. Синий пунктир показывает все рёбра текущей границы; выбранное минимальное выделено жёлтым. Серые рёбра сейчас не подходят для добавления. Набор кандидатов появляется одним этапом; следующим этапом добавляется выбранное ребро. Те же данные доступны текстом под canvas.

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

Реализация и сохранённая история

Для наглядности каждую границу ищем полным просмотром E рёбер. За каждой добавленной вершиной следует одна проверка, включая последнюю пустую границу каждой компоненты: всего V полных проверок, то есть VE просмотров рёбер. Время — O(VE + V), рабочая память — O(V) без входа и возвращаемого леса. У реализации Прима с кучей другие оценки; они не описывают это демо с полными просмотрами.

Плеер дополнительно хранит O(V) неизменяемых снимков: отмеченные вершины, выбранные рёбра и до E рёбер границы. История занимает O(V(V+E)) памяти, граф размером O(V+E) хранится один раз. Длительность воспроизведения объясняет решения и не измеряет быстродействие вычислений.

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

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

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