Модуль 20 ⏱ ~17 мин чтения 📐 1 Mermaid диаграмм

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

В прошлой статье 8. Минимальное остовное дерево. Алгоритм Крускала мы научились строить Минимальное остовное дерево (MST) с помощью жадной глобальной сортировки всех ребер графа. Алгоритм Крускала гениален в своей простоте и работает с невероятной скоростью на разреженных сетях благодаря легковесной структуре DSU.

Но мы завершили предыдущую главу ключевым архитектурным вопросом: что если наш граф экстремально плотный (Dense Graph)?
Представьте кластер из $10\,000$ серверов, где каждый узел физически соединен со всеми остальными. Это $10^8$ (100 миллионов) ребер! Крускал попытается отсортировать этот колоссальный массив, что потребует $O(E \log E)$ времени, гигабайты оперативной памяти и неизбежно разорвет процессорный кэш при перетасовке элементов.

Для таких сценариев инженеры обращаются к принципиально иной стратегии: вместо того чтобы обозревать весь граф глобально, мы "выращиваем" остовное дерево из одного маленького семени. Этот классический подход называется Алгоритмом Прима (Prim's Algorithm) (открыт Войцехом Ярником в 1930 году и независимо переоткрыт Робертом Примом в 1957 году).

Механика алгоритма: Расширение империи

Если Крускал собирает остов децентрализованно — кусочками из разных изолированных уголков графа (объединяя их через систему непересекающихся множеств DSU), то Прим ведет себя как расширяющееся централизованное государство: он с самого начала поддерживает единое, непрерывно растущее связное дерево, которое шаг за шагом поглощает новые узлы на своей границе.

Пошаговый план:

  1. Выбираем абсолютно любую стартовую вершину (например, 0). Помещаем ее в наше растущее дерево (Остов).
  2. Находим все ребра, которые соединяют узлы внутри Остова с узлами снаружи Остова.
  3. Выбираем из этих ребер самое дешевое (жадный шаг).
  4. Добавляем это ребро и новый узел, к которому оно ведет, в Остов.
  5. Повторяем шаги 2-4, пока все $V$ вершин не окажутся внутри Остова.
flowchart TD
    subgraph Step1["Шаг 1 - Старт с узла A"]
        A["Узел A<br>В остове"] ---|"Вес 1<br>Кандидат"| B["Узел B<br>Снаружи"]
        A ---|"Вес 4<br>Кандидат"| C["Узел C<br>Снаружи"]
    end

    subgraph Step2["Шаг 2 - Поглощение B"]
        A2["Узел A<br>В остове"] ---|"Вес 1<br>Взяли в остов"| B2["Узел B<br>В остове"]
        A2 -.-|"Вес 4<br>Кандидат"| C2["Узел C<br>Снаружи"]
        B2 -.-|"Вес 2<br>★ Новый кандидат"| C2
    end

    classDef default fill:#131d33,stroke:#38bdf8,stroke-width:1.5px,color:#f8fafc;
    classDef inMST fill:#065f46,stroke:#34d399,stroke-width:2px,color:#ffffff;
    class A,A2,B2 inMST;

На втором шаге у нас есть выбор: пойти в C из A за 4, или из B за 2. Алгоритм выберет ребро B-C.

Mechanical Sympathy: Как быстро искать кандидатов?

На каждом шаге алгоритма нам требуется моментально выбирать минимальное по весу ребро среди всех связей фронтира. Эта задача идеально решается с помощью Очереди с приоритетом (Min-Heap), подобно алгоритму Дейкстры (см. 5. Кратчайшие пути. Алгоритм Дейкстры).

В куче хранятся ребра-кандидаты. Когда мы присоединяем к остову очередную вершину, мы просто закидываем в кучу все ее исходящие ребра, ведущие к внешним узлам. На каждой итерации извлекается минимальное ребро (heap.Pop). Если вершина, в которую оно ведет, уже была захвачена остовом ранее — ребро отбрасывается (так как оно создаст цикл), и мы переходим к следующему.

Реализация на Go (Idiomatic Heap Approach)

Используем классический список смежности и стандартный пакет container/heap.

Go 
package main

import (
    "container/heap"
)

// Edge представляет взвешенное ребро
type Edge struct {
    To     int
    Weight int
}

// Graph — список смежности
type Graph struct {
    Adj [][]Edge
}

// PrimItem — элемент для очереди с приоритетом
type PrimItem struct {
    From   int // Откуда исходит ребро (из Остова)
    To     int // Куда ведет ребро (Кандидат)
    Weight int // Вес ребра
}

// MinHeap для ребер (реализация интерфейса heap.Interface)
type MinHeap []PrimItem

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Weight < h[j].Weight }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x any) {
    *h = append(*h, x.(PrimItem))
}

func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[0 : n-1]
    return item
}

// PrimMST возвращает сумму весов минимального остовного дерева
func PrimMST(g *Graph) int {
    V := len(g.Adj)
    if V == 0 {
        return 0
    }

    inMST := make([]bool, V) // Отслеживаем узлы внутри Остова
    pq := &MinHeap{}
    heap.Init(pq)

    totalWeight := 0
    edgesCount := 0

    // Начинаем с узла 0
    startNode := 0
    inMST[startNode] = true

    // Добавляем все ребра от стартового узла в кучу
    for _, edge := range g.Adj[startNode] {
        heap.Push(pq, PrimItem{From: startNode, To: edge.To, Weight: edge.Weight})
    }

    // Пока Остов не охватит все V узлов (потребуется V-1 ребер)
    for pq.Len() > 0 && edgesCount < V-1 {
        // Берем самое дешевое ребро
        minEdge := heap.Pop(pq).(PrimItem)

        // Если узел To уже в Остове, это ребро создаст цикл. Игнорируем.
        if inMST[minEdge.To] {
            continue
        }

        // Поглощаем новый узел
        inMST[minEdge.To] = true
        totalWeight += minEdge.Weight
        edgesCount++

        // Добавляем новые горизонты (исходящие ребра нового узла) в кучу
        for _, nextEdge := range g.Adj[minEdge.To] {
            if !inMST[nextEdge.To] {
                heap.Push(pq, PrimItem{
                    From:   minEdge.To,
                    To:     nextEdge.To,
                    Weight: nextEdge.Weight,
                })
            }
        }
    }

    // Проверка на связность графа
    if edgesCount != V-1 {
        return -1 // Граф разорван, построить полный MST невозможно
    }

    return totalWeight
}

Хардкор для Архитекторов: Оптимизация для Плотных Графов

Вышеописанная реализация на куче работает за $O(E \log V)$. Но в начале статьи мы заявили, что Прим спасает нас на плотных графах, где $E \approx V^2$.

Если $E = V^2$, то сложность решения на куче становится $O(V^2 \log V)$. Крускал работает за $O(V^2 \log V^2) = O(V^2 \log V)$. То есть асимптотически они равны! В чем же тогда выигрыш Прима?

Временная и пространственная сложность (Версия на Куче)

  • Временная сложность: $O(E \log V)$ — каждое ребро может быть добавлено в кучу и извлечено из нее один раз. Извлечение стоит $O(\log V)$ (максимальный размер кучи ограничивается количеством вершин).
  • Память: $O(V + E)$ — для хранения графа и кучи.

Итог

  1. Алгоритм Прима "выращивает" Минимальное остовное дерево из одной стартовой вершины, жадно присоединяя ближайшие узлы.
  2. Под капотом использует Очередь с приоритетом (Min-Heap) для быстрого поиска самых дешевых ребер на границе Остова.
  3. Код Прима алгоритмически похож на Дейкстру, но оптимизирует не общую длину пути, а локальную стоимость подключения.
  4. На экстремально плотных графах Прим с использованием плоского массива (вместо кучи) достигает математического предела скорости $O(V^2)$, оставляя Крускала далеко позади.

Прежде чем двигаться дальше, закрепим работу с компонентами связности и быстрой динамической проверкой циклов: в следующей завершающей лекции этого подраздела мы разберем практические трюки Union Find: 10. Union Find на графах, а затем перейдем к алгоритмам обработки текста и 1. Поиск подстроки.