Алгоритм Прима - как построить остовное дерево по шагам

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

Что такое минимальное остовное дерево

Пусть дан связный неориентированный граф $G = (V, E)$ с весовой функцией $w: E \to \mathbb{R}$. Остовное дерево - это подграф, который содержит все вершины $V$, является деревом (связен и без циклов) и потому имеет ровно $|V| - 1$ ребро. Минимальное остовное дерево - остовное дерево с минимальной суммой весов $\sum_{e \in T} w(e)$.

Если веса всех рёбер различны, МОД единственно. Если есть равные веса, минимальных деревьев может быть несколько, но их суммарная стоимость одинакова. Именно на этом свойстве и держатся жадные алгоритмы построения МОД: алгоритм Прима и алгоритм Краскала.

Идея алгоритма Прима

Алгоритм Прима поддерживает множество $S$ уже включённых в дерево вершин. На старте $S = \{r\}$ для произвольной стартовой вершины $r$. Затем многократно повторяется один шаг: среди всех рёбер, у которых один конец лежит в $S$, а другой вне $S$, выбирается ребро минимального веса, и его внешний конец добавляется в $S$. Процесс заканчивается, когда $S = V$.

Такие «пограничные» рёбра между $S$ и $V \setminus S$ образуют разрез. Ключевое утверждение - лемма о разрезе: для любого разреза самое лёгкое пересекающее его ребро принадлежит некоторому минимальному остовному дереву. Алгоритм Прима на каждом шаге как раз и берёт минимальное ребро текущего разреза, поэтому он корректен.

Хотите прогнать алгоритм Прима на собственном графе и увидеть, какое ребро выбирается на каждом шаге? Опишите рёбра ниже - инструмент соберёт пошаговую трассировку с растущим множеством $S$ и итоговой стоимостью дерева.

Псевдокод

В наивной реализации на каждой вершине поддерживается величина $key[v]$ - минимальный вес ребра, соединяющего $v$ с уже построенным деревом, и $\pi[v]$ - родитель $v$ в дереве.

для всех v из V:
    key[v] = +inf
    pi[v]  = nil
key[r] = 0
Q = V                       // приоритетная очередь по key
пока Q не пуста:
    u = extract-min(Q)      // вершина с минимальным key
    для каждого ребра (u, v) с весом w:
        если v в Q и w < key[v]:
            key[v] = w
            pi[v]  = u
            decrease-key(v)

После завершения рёбра $(\pi[v], v)$ для всех $v \neq r$ образуют минимальное остовное дерево. Обратите внимание: $key[v]$ хранит вес единственного ребра, а не накопленное расстояние, - это и отличает алгоритм Прима от алгоритма Дейкстры, где обновляется длина всего пути.

Пошаговый разбор на примере

Рассмотрим граф из 5 вершин $\{A, B, C, D, E\}$ со следующими рёбрами и весами: $A\!-\!B = 2$, $A\!-\!C = 3$, $B\!-\!C = 1$, $B\!-\!D = 4$, $C\!-\!E = 5$, $D\!-\!E = 6$. Стартуем с вершины $A$.

1. $S = \{A\}$. Пограничные рёбра: $A\!-\!B = 2$, $A\!-\!C = 3$. Минимум - $A\!-\!B$, добавляем $B$.
2. $S = \{A, B\}$. Рёбра разреза: $A\!-\!C = 3$, $B\!-\!C = 1$, $B\!-\!D = 4$. Минимум - $B\!-\!C = 1$, добавляем $C$.
3. $S = \{A, B, C\}$. Рёбра: $B\!-\!D = 4$, $C\!-\!E = 5$. Минимум - $B\!-\!D = 4$, добавляем $D$.
4. $S = \{A, B, C, D\}$. Рёбра: $C\!-\!E = 5$, $D\!-\!E = 6$. Минимум - $C\!-\!E = 5$, добавляем $E$.

Все вершины включены. Дерево состоит из рёбер $\{A\!-\!B, B\!-\!C, B\!-\!D, C\!-\!E\}$ суммарным весом $2 + 1 + 4 + 5 = 12$. Заметьте, что более дешёвое на вид ребро $A\!-\!C = 3$ в дерево не вошло: к моменту рассмотрения $C$ уже была достижима через $B\!-\!C = 1$.

Сложность и выбор структуры данных

Время работы целиком определяется тем, как реализована операция extract-min и decrease-key.

• Без приоритетной очереди (поиск минимума простым перебором массива): $O(V^2)$. Хорош для плотных графов, где $|E|$ близко к $|V|^2$.
• Двоичная куча: $O(E \log V)$. $V$ извлечений минимума и до $E$ операций decrease-key, каждая за $O(\log V)$.
• Фибоначчиева куча: амортизированное $O(E + V \log V)$ - теоретический оптимум, но на практике константа велика и куча почти не используется.

Для разреженных графов выгодна двоичная куча, для плотных - простой массив на $O(V^2)$. Это зеркально отражает выбор структуры в алгоритме Дейкстры - см. разбор алгоритма Дейкстры на взвешенном графе, где приоритетная очередь устроена аналогично.

Прим против Краскала

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

Практическое правило: на плотных графах быстрее Прим с массивом ($O(V^2)$), на разреженных - Краскал ($O(E \log E)$ на сортировку) или Прим с кучей. Если граф уже задан списком отсортированных рёбер, естественнее Краскал. Если граф плотный и хранится матрицей смежности - Прим. По смежной логике разрезов и циклов полезно сравнить с задачами на радиус и диаметр графа.

Частые ошибки

• Путают $key[v]$ с расстоянием. В алгоритме Прима $key[v]$ - вес одного ребра до дерева, а не длина пути от старта. Если случайно накапливать сумму, получится не МОД.
• Применяют к ориентированному графу. МОД определено для неориентированных графов. Для ориентированных аналог - оптимальное входящее дерево (алгоритм Эдмондса), это другая задача.
• Забывают про связность. Если граф несвязен, остовного дерева не существует - алгоритм Прима построит дерево только для компоненты стартовой вершины. Нужен остовный лес.
• Считают, что отрицательные веса ломают алгоритм. В отличие от Дейкстры, алгоритм Прима корректно работает с отрицательными весами рёбер: лемма о разрезе от знака весов не зависит.
• Останавливаются по числу рёбер неверно. Дерево готово, когда добавлено ровно $|V| - 1$ ребро или $S = V$, а не когда «кончились дешёвые рёбра».

FAQ

Чем алгоритм Прима отличается от алгоритма Дейкстры? Структурно они почти идентичны (приоритетная очередь, релаксация соседей), но минимизируют разное: Прим минимизирует вес присоединяемого ребра ($key[v] = w$), Дейкстра - длину всего пути от источника ($d[v] = d[u] + w$).

Зависит ли результат от выбора стартовой вершины? Сумма весов МОД - нет, она всегда минимальна и одинакова. Конкретный набор рёбер может отличаться, только если в графе есть рёбра равного веса.

Работает ли алгоритм Прима с отрицательными весами? Да. Лемма о разрезе не использует положительности весов, поэтому отрицательные рёбра обрабатываются корректно. Это отличает его от алгоритма Дейкстры.

Коротко

Алгоритм Прима строит минимальное остовное дерево, выращивая одно дерево из стартовой вершины и на каждом шаге присоединяя ближайшую внешнюю вершину по самому лёгкому ребру разреза. Корректность следует из леммы о разрезе. Сложность - $O(V^2)$ с массивом или $O(E \log V)$ с двоичной кучей; выбор структуры зависит от плотности графа. От Краскала отличается стратегией (единое дерево против слияния компонент), от Дейкстры - тем, что минимизирует вес ребра, а не длину пути.