Алгоритм Прима
Последнее обновление
Алгоритм Прима строит минимальное остовное дерево (MST) - самый дешёвый набор рёбер, соединяющий все узлы без циклов - выращивая одно дерево наружу от стартового узла. На каждом шаге он рассматривает все рёбра, пересекающие границу между деревом и узлом вне его, и добавляет самое дешёвое. Нажмите воспроизведение выше, чтобы увидеть, как дерево расширяется, всегда беря ребро наименьшего веса, ведущее к новому узлу.
Поскольку он всегда выбирает минимальное пересекающее ребро, каждое добавление безопасно (гарантированно является частью некоторого MST). С очередью с приоритетом на основе двоичной кучи, ключом которой является самое дешёвое ребро к каждому внешнему узлу, Прим работает за O(E log V). Он контрастирует с Крускалом, который сортирует все рёбра глобально, вместо того чтобы выращивать одно связное дерево.
Временная и пространственная сложность
| Реализация | Сложность | Примечания |
|---|---|---|
| Двоичная куча | O(E log V) | Очередь с приоритетом пересекающих рёбер |
| Матрица смежности | O(V²) | Проще; подходит для плотных графов |
| Память | O(V + E) | Принадлежность дереву + очередь с приоритетом |
| Лучше всего для | Плотных графов | Растёт от одного стартового узла |
Пошагово
| Шаг | Что происходит |
|---|---|
| 1 | Начните дерево с любого одного узла. |
| 2 | Рассмотрите все рёбра, пересекающие границу между деревом и узлом вне его. |
| 3 | Выберите пересекающее ребро с наименьшим весом. |
| 4 | Добавьте это ребро и его новый узел в дерево. |
| 5 | Повторяйте, пока все узлы не окажутся в дереве. |
Разобранный пример
Построение MST графа из 4 узлов с рёбрами A-B=1, A-C=3, B-C=2, B-D=4, C-D=5, начиная с A:
| Шаг | Дерево | Пересекающие рёбра | Выбранное ребро |
|---|---|---|---|
| 1 | {A} | A-B=1, A-C=3 | A-B (вес 1) |
| 2 | {A, B} | A-C=3, B-C=2, B-D=4 | B-C (вес 2) |
| 3 | {A, B, C} | B-D=4, C-D=5 | B-D (вес 4) |
| 4 | {A, B, C, D} | нет - все узлы в дереве | готово: вес MST 1+2+4 = 7 |
Когда использовать алгоритм Прима
| Используйте, когда | Избегайте, когда |
|---|---|
| Вам нужно минимальное остовное дерево связного неориентированного взвешенного графа. | Граф ориентированный или вам нужны кратчайшие пути - используйте вместо этого Дейкстру или Беллмана-Форда. |
Граф плотный (E близко к V²); матричная форма O(V²) проста и быстра. | Граф разреженный, а рёбра уже отсортированы или их легко отсортировать - Крускал часто проще. |
| Вы хотите, чтобы дерево росло из одной области наружу (например, инкрементальная разметка сети). | Граф несвязный - Прим охватывает только одну компоненту; вам нужен минимальный остовный лес. |
| У вас уже есть доступная структура смежности и очередь с приоритетом. | Вам нужно обнаруживать циклы по глобальному набору рёбер - union-find (Крускал) лучше подходит для этой задачи. |
Код Prim's Algorithm
Чистая, готовая к запуску реализация Prim's Algorithm на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Prim's Algorithm на Python
1import heapq2
3
4def prim(graph, start):5 visited = {start}6 heap = [(w, start, v) for v, w in graph[start]]7 heapq.heapify(heap)8 mst, total = [], 09 while heap and len(visited) < len(graph):10 w, u, v = heapq.heappop(heap)11 if v in visited:12 continue13 visited.add(v)14 mst.append((u, v, w))15 total += w16 # Offer the new node's edges to the frontier17 for neighbor, weight in graph[v]:18 if neighbor not in visited:19 heapq.heappush(heap, (weight, v, neighbor))20 return mst, total21
22
23graph = {24 "A": [("B", 4), ("C", 1)],25 "B": [("A", 4), ("C", 3), ("D", 2)],26 "C": [("A", 1), ("B", 3), ("D", 5)],27 "D": [("B", 2), ("C", 5), ("E", 7)],28 "E": [("D", 7)],29}30
31mst, total = prim(graph, "A")32for u, v, w in mst:33 print(f"{u} - {v} (weight {w})")34print("Total MST weight:", total)Код Prim's Algorithm на JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { A: 4, C: 1, D: 5 },4 C: { A: 2, B: 1, D: 8, E: 10 },5 D: { B: 5, C: 8, E: 2 },6 E: { C: 10, D: 2 },7};8
9function prim(start) {10 const inTree = new Set([start]);11 const mst = [];12 let total = 0;13 while (inTree.size < Object.keys(graph).length) {14 // JS has no built-in heap: scan all crossing edges for the cheapest15 let best = null;16 for (const u of inTree) {17 for (const [v, w] of Object.entries(graph[u])) {18 if (!inTree.has(v) && (best === null || w < best[2])) {19 best = [u, v, w];20 }21 }22 }23 const [u, v, w] = best;24 inTree.add(v);25 mst.push(`${u}-${v} (${w})`);26 total += w;27 }28 return { mst, total };29}30
31const { mst, total } = prim("A");32console.log("MST edges:", mst.join(", "));33console.log("Total weight:", total);Код Prim's Algorithm на Java
1import java.util.ArrayList;2import java.util.List;3import java.util.PriorityQueue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 List<List<int[]>> adj = new ArrayList<>();9 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());10 int[][] edges = {11 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},12 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}13 };14 for (int[] e : edges) {15 adj.get(e[0]).add(new int[]{e[1], e[2]});16 adj.get(e[1]).add(new int[]{e[0], e[2]});17 }18
19 boolean[] inMst = new boolean[n];20 // Always grow the tree along the cheapest crossing edge21 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);22 pq.add(new int[]{0, 0}); // {node, edge weight}23 int total = 0, taken = 0;24 while (!pq.isEmpty() && taken < n) {25 int[] cur = pq.poll();26 if (inMst[cur[0]]) continue;27 inMst[cur[0]] = true;28 total += cur[1];29 taken++;30 for (int[] edge : adj.get(cur[0])) {31 if (!inMst[edge[0]]) pq.add(edge);32 }33 }34 System.out.println("MST nodes reached: " + taken);35 System.out.println("MST total weight: " + total);36 }37}Код Prim's Algorithm на C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Undirected weighted graph: adj[u] = {(neighbor, weight), ...}7 std::vector<std::vector<std::pair<int, int>>> adj = {8 {{1, 2}, {3, 6}}, // 09 {{0, 2}, {2, 3}, {3, 8}, {4, 5}}, // 110 {{1, 3}, {4, 7}}, // 211 {{0, 6}, {1, 8}}, // 312 {{1, 5}, {2, 7}}, // 413 };14 int n = static_cast<int>(adj.size());15 std::vector<bool> inMST(n, false);16 using State = std::pair<int, int>; // (edge weight, node)17 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;18 pq.push({0, 0});19 int total = 0, picked = 0;20 // Always grow the tree along the cheapest crossing edge21 while (!pq.empty() && picked < n) {22 auto [w, u] = pq.top();23 pq.pop();24 if (inMST[u]) continue;25 inMST[u] = true;26 total += w;27 ++picked;28 std::cout << "Add node " << u << " (edge weight " << w << ")\n";29 for (auto [v, weight] : adj[u]) {30 if (!inMST[v]) pq.push({weight, v});31 }32 }33 std::cout << "MST total weight: " << total << "\n";34 return 0;35}Код Prim's Algorithm на C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Undirected weighted graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 2, 0, 6, 0},11 {2, 0, 3, 8, 5},12 {0, 3, 0, 0, 7},13 {6, 8, 0, 0, 0},14 {0, 5, 7, 0, 0},15 };16 int key[N], parent[N];17 bool inMST[N] = {false};18 for (int v = 0; v < N; v++) {19 key[v] = INF;20 parent[v] = -1;21 }22 key[0] = 0;23 int total = 0;24 // O(V^2) scan for the cheapest crossing edge (no heap needed here)25 for (int iter = 0; iter < N; iter++) {26 int u = -1;27 for (int v = 0; v < N; v++) {28 if (!inMST[v] && (u == -1 || key[v] < key[u])) u = v;29 }30 inMST[u] = true;31 total += key[u];32 if (parent[u] != -1) {33 printf("Add edge %d - %d (weight %d)\n", parent[u], u, key[u]);34 }35 for (int v = 0; v < N; v++) {36 if (w[u][v] > 0 && !inMST[v] && w[u][v] < key[v]) {37 key[v] = w[u][v];38 parent[v] = u;39 }40 }41 }42 printf("MST total weight: %d\n", total);43 return 0;44}Часто задаваемые вопросы об алгоритме Прима
Какова временная сложность алгоритма Прима?
O(E log V). Более простая версия с матрицей смежности, которая на каждом шаге ищет минимальное пересекающее ребро, имеет сложность O(V²), что может быть быстрее на плотных графах. Обе используют память O(V + E).В чём разница между алгоритмами Прима и Крускала?
Оба находят минимальное остовное дерево жадным образом. Прим выращивает одно связное дерево от стартового узла, многократно добавляя самое дешёвое ребро, выходящее из дерева (используя очередь с приоритетом). Крускал рассматривает все рёбра, отсортированные по весу, и добавляет самое дешёвое, не образующее цикл (используя union-find). Прим часто предпочтителен на плотных графах, Крускал - на разреженных.
Всегда ли алгоритм Прима находит оптимальное MST?
Да. На каждом шаге самое дешёвое ребро, пересекающее текущее дерево, безопасно добавлять - оно принадлежит некоторому минимальному остовному дереву (свойство разреза). Многократное добавление безопасных рёбер даёт настоящее минимальное остовное дерево при условии, что граф связный.
Когда следует использовать алгоритм Прима вместо Крускала?
O(V²) избегает сортировки всех E рёбер и выращивает одно дерево от стартового узла. Крускал блистает на разреженных графах, где сортировка списка рёбер дёшева, а union-find обеспечивает быстрые проверки циклов. Оба дают корректное MST, поэтому выбор зависит главным образом от плотности рёбер и от того, какие структуры данных у вас уже есть.Влияет ли стартовый узел на итоговое MST?
Нет - суммарный вес MST одинаков независимо от того, с какого узла вы начинаете, потому что вес минимального остовного дерева связного графа уникален. Конкретные рёбра могут различаться только тогда, когда несколько рёбер имеют одинаковый вес и существует несколько MST. В остальных случаях Прим приходит к точно такому же дереву независимо от стартового узла.
Может ли алгоритм Прима работать с несвязными графами?
Не напрямую. Прим выращивает одно дерево, поэтому охватывает только связную компоненту, содержащую стартовый узел, оставляя остальное нетронутым. Чтобы покрыть каждую компоненту, вы бы многократно запускали Прим от непосещённого узла, получая минимальный остовный лес вместо одного дерева.
Связанные ресурсы
Больше визуализаций
