Алгоритм Прима объяснение

Question

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

Answer 1

Алгоритм Прима (Prim’s algorithm) – это один из классических жадных алгоритмов для нахождения минимального остовного дерева (Minimum Spanning Tree, MST) в взвешенном неориентированном графе. Ниже приводится подробное описание принципа его работы, необходимых структур данных, а также пример реализации.

Суть задачи

Пусть у нас есть связный неориентированный граф $G = (V, E)$ с весами на рёбрах (то есть каждому ребру $(u, v) \in E$ приписан некоторый вес $w(u,v)$ ). Требуется найти подмножество рёбер, соединяющее все вершины графа, причём сумма весов этих рёбер должна быть минимальной из всех возможных вариантов соединения всех вершин. Это и есть минимальное остовное дерево.

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

Алгоритм Прима строится на жадном подходе. Мы начинаем со случайной (или заранее выбранной) вершины и постепенно «наращиваем» дерево, пока оно не будет содержать все вершины графа.

Общее пошаговое описание можно сформулировать так:

Инициализация
- Выбираем любую вершину (часто берут вершину с индексом 0 или 1 — это не принципиально).
- Обозначаем это как текущее дерево, которое пока что состоит из одной вершины.
Выбор ребра минимального веса из «граничных»
- Рассматриваем все рёбра, которые выходят из вершины (или вершин), уже попавшей(их) в текущее дерево, во внешние вершины (те, которые ещё не входят в дерево).
- Из всех таких «граничных» рёбер выбираем ребро с минимальным весом.
Добавление ребра и новой вершины в дерево
- Добавляем выбранное ребро в дерево.
- Добавляем вершину, которая была «снаружи», но связана этим ребром, в состав нашего текущего дерева.
Повтор
- Повторяем шаги 2–3 до тех пор, пока все вершины не окажутся в дереве.

Результатом будет минимальное остовное дерево.

Важные детали реализации

Структура данных для рёбер
- Можно хранить рёбра в списке смежности (для каждой вершины хранить список пар (сосед, вес)), либо в виде матрицы смежности.
- В больших графах обычно используют списки смежности.
Выбор следующего минимального ребра
- Эффективно делается с помощью структуры данных куча (приоритетная очередь), чтобы на каждом шаге быстро находить ребро с минимальным весом.
- Если не пользоваться кучей, а просто сканировать все доступные рёбра, на каждом шаге можно получить сложность $O(V \times E)$ для всего алгоритма, что не всегда оптимально.
- С использованием приоритетной очереди, где мы храним «граничные» рёбра/вершины (точнее расстояние от новой вершины к текущему остову), можно достичь сложности порядка $O(E \log V)$ .
Как хранить «расстояние» до текущего дерева
- В классической оптимизированной версии мы для каждой вершины (ещё не попавшей в дерево) храним минимальный вес ребра, которое её может соединить с уже построенным деревом.
- На каждом шаге выбираем ту вершину, которая имеет наименьший «вес» соединения.

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

Для наглядности возьмём простой граф из 5 вершин $\{A, B, C, D, E\}$ и рёбер с весами:

$A - B = 2$
$A - C = 3$
$B - C = 1$
$B - D = 4$
$C - E = 6$
$D - E = 2$

Шаги:

Выбираем стартовую вершину $A$ .
От $A$ $A$ исходят рёбра к $B$ $B$ и $C$ $C$ . Они «граничные»:
- $A-B = 2$
- $A-C = 3$
  Минимальное – $A-B$ (2). Добавляем в остов ребро $(A,B)$ .
Теперь в остове: вершины $A$ $A$ и $B$ $B$ . Граничные рёбра:
- $A-C = 3$ (всё ещё граничное, ведь $C$ не в остове)
- $B-C = 1$
- $B-D = 4$
  Минимальное – $B-C = 1$ . Добавляем ребро $(B,C)$ .
Теперь в остове: $A, B, C$ $A, B, C$ . Граничные рёбра:
- $B-D = 4$
- $C-E = 6$
- Параллельно, $A-C$ уже не рассматриваем, потому что $C$ уже в остове.
  Минимальное – $B-D = 4$ . Добавляем $(B,D)$ .
Теперь в остове: $A, B, C, D$ $A, B, C, D$ . Граничные рёбра:
- $C-E = 6$
- $D-E = 2$
  Минимальное – $D-E = 2$ . Добавляем $(D,E)$ .

Все вершины оказались в остове. Получившееся дерево:

$(A,B) = 2$
$(B,C) = 1$
$(B,D) = 4$
$(D,E) = 2$

Суммарный вес = $2 + 1 + 4 + 2 = 9$ . Это и есть наш минимальный остов (хотя нужно проверять, нет ли лучшего варианта – в данном случае это действительно минимальный).

Пример кода на Python

Ниже приведён упрощённый вариант алгоритма Прима, где:

граф представлен в виде списка смежности: graph[u] – это список пар (v, вес), обозначающих ребро $u - v$ .
для поиска ребра с минимальным весом используем heapq (приоритетную очередь) из стандартной библиотеки.

python
import heapq

def prim_mst(graph, start=0):
    """
    graph: список смежности, где graph[u] = [(v1, w1), (v2, w2), ...]
    start: индекс стартовой вершины
    Возвращает список рёбер (u, v, w) и суммарный вес MST.
    """

    n = len(graph)          # число вершин
    visited = [False] * n   # отметка, что вершина включена в MST
    mst_edges = []          # список рёбер MST: (u, v, w)
    total_weight = 0        # суммарный вес MST

    # Мини-куча для рёбер: (вес, откуда, куда)
    # Начинаем со стартовой вершины
    pq = []
    visited[start] = True
    for (v, w) in graph[start]:
        heapq.heappush(pq, (w, start, v))

    # Пока очередь не пуста и MST не включает все вершины
    while pq and len(mst_edges) < n - 1:
        # Извлекаем ребро с наименьшим весом
        w, u, v = heapq.heappop(pq)
        if not visited[v]:
            # Если вершина v ещё не была посещена, добавляем ребро в MST
            visited[v] = True
            mst_edges.append((u, v, w))
            total_weight += w

            # Добавляем в кучу все рёбра, исходящие из v
            for (nv, nw) in graph[v]:
                if not visited[nv]:
                    heapq.heappush(pq, (nw, v, nv))

    return mst_edges, total_weight

# Пример использования
if __name__ == "__main__":
    # Допустим, у нас 5 вершин: 0,1,2,3,4
    # graph[u] хранит список (v, вес)
    graph = [
        [(1, 2), (2, 3)],      # вершина 0 связана с 1 (2), 2 (3)
        [(0, 2), (2, 1), (3, 4)], 
        [(0, 3), (1, 1), (4, 6)],
        [(1, 4), (4, 2)],
        [(2, 6), (3, 2)]
    ]
    
    mst, weight = prim_mst(graph, start=0)
    print("Рёбра MST:", mst)
    print("Суммарный вес:", weight)

Пояснения к коду

visited: массив, который отмечает, какие вершины уже включены в остов.
pq (priority queue): приоритетная очередь (куча), где мы складываем кандидаты на добавление в MST. Ребро хранится в формате (вес, откуда, куда); таким образом, в вершине кучи всегда будет ребро с наименьшим весом.
На каждом шаге достаём ребро с минимальным весом, проверяем, не вошла ли вершина v в MST. Если нет – добавляем, иначе пропускаем.
Так как мы постепенно «накрываем» все вершины, в итоге получаем нужное MST.

Сложность

При использовании двоичной кучи (heapq) операции вставки и извлечения занимают $O(\log E)$ , где $E$ – количество рёбер.
Всего мы можем вставить в кучу вплоть до $O(E)$ рёбер. Тогда итоговая асимптотика $\displaystyle O(E \log E)$ .
Но обычно это ещё упрощают до $O(E \log V)$ , учитывая, что $E \approx V^2$ в худшем случае, но во многих задачах $E$ существенно меньше $V^2$ , и эта запись выглядит аккуратнее.

Итог

Алгоритм Прима – это простой жадный метод для построения минимального остова:

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

Этот алгоритм широко используется наравне с алгоритмом Краскала для решения задач поиска минимального остовного дерева. Разница в основном в способе расширения дерева:

Прим «растит» дерево от одной вершины, добавляя по одному ребру;
Краскал идёт по рёбрам в порядке возрастания веса и объединяет компоненты, пока они не сольются в одно дерево.

Таким образом, выбор между алгоритмом Прима и Краскала часто определяется тем, как представлен граф (списком рёбер или списком смежности) и особенностями задачи, но оба дают одинаковый корректный результат – MST.