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

Алгоритм Прима — это ещё один классический способ построить минимальное остовное дерево во взвешенном неориентированном графе.

Напомню идею задачи: у нас есть связный граф, у каждого ребра есть вес, и нужно выбрать набор из n-1 ребра так, чтобы:

все вершины оказались связаны;
циклов не было;
суммарный вес выбранных рёбер был минимален.

Алгоритм Прима решает эту задачу постепенно: он наращивает одно связное дерево, каждый раз добавляя в него новую вершину по самому выгодному ребру.

Основная идея¶

Если алгоритм Краскала мыслит категориями «давайте отсортируем все рёбра и будем брать безопасные», то алгоритм Прима мыслит иначе:

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

То есть мы всё время поддерживаем одну растущую компоненту.

Это очень похоже на алгоритм Дейкстры:

в Дейкстре мы выбираем вершину с минимальным расстоянием от старта;
в Приме мы выбираем вершину, которую дешевле всего присоединить к уже построенному дереву.

Но цели у них разные:

Дейкстра строит кратчайшие пути от одной вершины;
Прим строит минимальное остовное дерево для всего графа.

Интуиция¶

Представим, что мы хотим соединить несколько городов дорогами минимальной стоимости.

Мы начинаем с одного города. Затем каждый раз смотрим:

какой новый город можно присоединить к уже построенной сети дешевле всего?

Если всегда делать такой шаг, в итоге получится оптимальная сеть дорог.

Почему идея разумная? Потому что на каждом шаге мы выбираем самое дешёвое ребро, пересекающее границу между уже взятыми вершинами и ещё не взятыми. Такое ребро безопасно для минимального остовного дерева.

Это один из ключевых фактов про MST.

Пошаговый пример¶

Рассмотрим граф:

graph LR
    A[1] ---|3| B[2]
    A ---|5| C[3]
    B ---|2| D[4]
    B ---|5| E[5]
    C ---|9| D
    C ---|3| F[6]
    D ---|7| E
    E ---|6| F

Hold "Ctrl" to enable pan & zoom

Начнём с вершины 1.

Шаг 1¶

В дереве пока только вершина 1.

Кандидатные рёбра:

1-2 с весом 3
1-3 с весом 5

Берём самое дешёвое ребро 1-2.

Шаг 2¶

Теперь в дереве вершины {1, 2}.

Кандидатные рёбра, которые ведут наружу:

1-3 вес 5
2-4 вес 2
2-5 вес 5

Берём 2-4.

Шаг 3¶

Теперь в дереве {1, 2, 4}.

Кандидаты:

1-3 вес 5
2-5 вес 5
4-3 вес 9
4-5 вес 7

Можно взять любое ребро веса 5. Например, 1-3.

Шаг 4¶

Теперь в дереве {1, 2, 3, 4}.

Кандидаты:

2-5 вес 5
4-5 вес 7
3-6 вес 3

Берём 3-6.

Шаг 5¶

Теперь в дереве {1, 2, 3, 4, 6}.

Кандидаты:

2-5 вес 5
4-5 вес 7
6-5 вес 6

Берём 2-5.

Все вершины подключены.

Итоговое остовное дерево содержит рёбра:

1-2 вес 3
2-4 вес 2
1-3 вес 5
3-6 вес 3
2-5 вес 5

Суммарный вес:

3 + 2 + 5 + 3 + 5 = 18

Почему алгоритм корректен¶

Ключевая идея доказательства такая.

Пусть мы уже выбрали некоторое множество вершин S, которые входят в текущее дерево. Рассмотрим все рёбра, которые соединяют вершины из S с вершинами вне S. Алгоритм Прима выбирает среди них ребро минимального веса.

Такое ребро можно безопасно включить в некоторое минимальное остовное дерево.

Почему это правда¶

Граница между множеством S и остальными вершинами называется разрезом. Для MST верно свойство:

минимальное по весу ребро, пересекающее любой разрез, обязательно входит хотя бы в одно минимальное остовное дерево.

Алгоритм Прима на каждом шаге как раз использует это свойство. Поэтому каждый его выбор безопасен, а после n-1 шагов мы получаем минимальное остовное дерево.

Чем Прим отличается от Краскала¶

Алгоритм Краскала¶

сортирует все рёбра;
постепенно добавляет рёбра в порядке возрастания веса;
следит, чтобы не образовался цикл;
обычно использует DSU / union-find.

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

растит одно дерево из стартовой вершины;
на каждом шаге выбирает лучшее ребро, ведущее наружу;
обычно использует очередь с приоритетом.

Когда что удобнее¶

Краскал особенно удобен, когда граф задан просто списком рёбер.
Прим особенно удобен, когда граф хранится списками смежности и нужно постепенно расширять компоненту.

На практике в спортивном программировании чаще используют Краскала, потому что он очень коротко пишется вместе с DSU. Но Прим тоже крайне важен и часто оказывается более естественным.

Реализация через priority queue¶

Для каждой вершины будем хранить минимальный вес ребра, которым её можно присоединить к уже построенному дереву.

Дальше используем очередь с приоритетом:

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

Это почти тот же шаблон, что и у Дейкстры.

Код на C++¶

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int,int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

    const long long INF = (long long)4e18;
    vector<long long> best(n + 1, INF);
    vector<int> parent(n + 1, -1);
    vector<bool> used(n + 1, false);

    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;

    best[1] = 0;
    pq.push({0, 1});

    long long mst_weight = 0;
    vector<pair<int,int>> mst_edges;

    while (!pq.empty()) {
        auto [cur_w, v] = pq.top();
        pq.pop();

        if (used[v]) continue;
        used[v] = true;
        mst_weight += cur_w;

        if (parent[v] != -1) {
            mst_edges.push_back({parent[v], v});
        }

        for (auto [to, w] : g[v]) {
            if (!used[to] && w < best[to]) {
                best[to] = w;
                parent[to] = v;
                pq.push({best[to], to});
            }
        }
    }

    if ((int)mst_edges.size() != n - 1) {
        cout << "Граф несвязный, MST не существует\n";
        return 0;
    }

    cout << "Вес MST: " << mst_weight << "\n";
    cout << "Ребра MST:\n";
    for (auto [a, b] : mst_edges) {
        cout << a << " " << b << "\n";
    }

    return 0;
}

Как работает код¶

1. Список смежности¶

Граф хранится в виде:

g[v] — список соседей вершины v;
каждый элемент — пара (to, w).

2. Массив `best`¶

best[to] — минимальный вес ребра, которым вершину to можно сейчас подключить к дереву.

3. Массив `parent`¶

parent[to] — из какой вершины мы пришли оптимальным ребром.

Это позволяет не только найти вес MST, но и восстановить сами рёбра дерева.

4. Очередь с приоритетом¶

В очереди лежат пары:

вес подключения;
вершина.

Каждый раз выбирается вершина, которую дешевле всего добавить следующей.

Оценка сложности¶

Если граф задан списками смежности и используется priority_queue, то сложность составляет:

по времени: O((n + m) log m)
часто также пишут: O(m log n)

Обе оценки по сути отражают одно и то же поведение для разреженных графов.

Память:

O(n + m)

Важные замечания¶

1. Граф должен быть связным¶

Если граф несвязный, то минимального остовного дерева для всего графа не существует. В таком случае можно построить только минимальный остовный лес.

2. Стартовая вершина может быть любой¶

Алгоритм можно запускать из любой вершины. Итоговый вес MST будет одинаковым, хотя конкретный набор рёбер иногда может отличаться, если существуют несколько разных MST с одинаковым весом.

3. Отрицательные веса не мешают¶

В отличие от Дейкстры, алгоритму Прима не страшны отрицательные веса. Для MST это не проблема.

Небольшой пример ввода¶

Один из возможных ответов:

Вес MST: 18
Ребра MST:
1 2
2 4
1 3
3 6
2 5

Когда полезно помнить про Прима¶

Алгоритм Прима особенно хорош, когда:

нужно построить MST напрямую по спискам смежности;
граф достаточно разреженный;
хочется использовать подход, похожий на Дейкстру;
нужно мыслить не рёбрами глобально, а «растущей компонентой».

Краткое резюме¶

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

начинает с одной вершины;
постепенно достраивает одно дерево;
на каждом шаге выбирает минимальное ребро, ведущее к новой вершине;
корректен благодаря свойству минимального ребра на разрезе;
эффективно реализуется через priority_queue.

Если Краскал — это стратегия «выбираем хорошие рёбра по всему графу», то Прим — это стратегия «растим дерево шаг за шагом».

Обе идеи очень важны, и хорошо уметь применять обе.

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

Основная идея¶

Интуиция¶

Пошаговый пример¶

Шаг 1¶

Шаг 2¶

Шаг 3¶

Шаг 4¶

Шаг 5¶

Почему алгоритм корректен¶

Почему это правда¶

Чем Прим отличается от Краскала¶

Алгоритм Краскала¶

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

Когда что удобнее¶

Реализация через priority queue¶

Код на C++¶

Как работает код¶

1. Список смежности¶

2. Массив best¶

3. Массив parent¶

4. Очередь с приоритетом¶

Оценка сложности¶

Важные замечания¶

1. Граф должен быть связным¶

2. Стартовая вершина может быть любой¶

3. Отрицательные веса не мешают¶

Небольшой пример ввода¶

Когда полезно помнить про Прима¶

Краткое резюме¶

2. Массив `best`¶

3. Массив `parent`¶