Алгоритм Прима

Начнём с одной вершины и будем наращивать дерево: на каждом шаге добавляем ближайшую к нему вершину — ту, до которой есть самое лёгкое ребро из уже собранного куска.

По лемме о безопасном ребре это законно: мы всё время берём минимальное ребро, выходящее из одной и той же компоненты.

Версия за $O(n^2)$

Держим массив best[v] — вес самого лёгкого ребра из дерева в $v$.

vector<long long> best(n, INF);
vector<char> used(n, 0);
best[0] = 0;
long long total = 0;

for (int it = 0; it < n; it++) {
    int v = -1;
    for (int u = 0; u < n; u++)
        if (!used[u] && best[u] < INF && (v == -1 || best[u] < best[v])) v = u;
    if (v == -1) { /* граф несвязен */ break; }
    used[v] = 1;
    total += best[v];
    for (auto [to, w] : g[v])
        if (!used[to] && w < best[to]) best[to] = w;
}

Сравните с Дейкстрой за $O(n^2)$: различие ровно в одной строке. Там d[v] + c < d[to] — длина всего пути, здесь w < best[to] — вес одного ребра.

Смысл различия: Дейкстра ищет кратчайшие пути от старта, Прим — самое дешёвое присоединение к дереву. Пути его не интересуют.

Версия за $O(m \log n)$

Так же, как у Дейкстры, поиск минимума заменяется очередью с приоритетом, и так же нужна проверка на устаревшую запись:

priority_queue<pair<long long, int>,
               vector<pair<long long, int>>,
               greater<>> q;
q.push({0, 0});
while (!q.empty()) {
    auto [w, v] = q.top(); q.pop();
    if (used[v]) continue;                 // без этой строки будет квадрат
    used[v] = 1;
    total += w;
    for (auto [to, c] : g[v])
        if (!used[to] && c < best[to]) { best[to] = c; q.push({c, to}); }
}

Какую версию когда

Ровно та же развилка, что у Дейкстры, и по той же причине.

Плотный граф ($m$ близко к $n^2$) — версия за $O(n^2)$: логарифм не нужен, а константа меньше. Разреженный — версия с кучей.

На плотном графе Прим за $O(n^2)$ обгоняет Краскала: тому нужно отсортировать $O(n^2)$ рёбер, а это уже $O(n^2 \log n)$.

Проверено: на 40 000 графов вес совпал с перебором всех остовных подмножеств рёбер.

Восстановление самих рёбер

Как и в Дейкстре, рядом с best[v] держим from[v] — из какой вершины пришло это ребро. Обновляем в той же строке. В конце рёбра дерева — это пары $(v, \text{from}[v])$ для всех $v$, кроме стартовой.