Algoritmo di Prim
Ultimo aggiornamento
L'algoritmo di Prim costruisce un albero ricoprente minimo (MST), cioè l'insieme di archi più economico che collega tutti i nodi senza cicli, facendo crescere un unico albero verso l'esterno a partire da un nodo iniziale. A ogni passo esamina tutti gli archi che vanno dall'albero a un nodo esterno e aggiunge il più economico. Premi play qui sopra per vedere l'albero espandersi, prendendo sempre l'arco di peso minore che raggiunge un nuovo nodo.
Dato che sceglie sempre l'arco di attraversamento minimo, ogni aggiunta è sicura (garantita come parte di qualche MST). Con una coda di priorità basata su heap binario, indicizzata sull'arco più economico verso ogni nodo esterno, Prim richiede O(E log V). Si differenzia da Kruskal, che ordina globalmente tutti gli archi invece di far crescere un unico albero connesso.
Complessità temporale e spaziale
| Implementazione | Complessità | Note |
|---|---|---|
| Heap binario | O(E log V) | Coda di priorità degli archi di attraversamento |
| Matrice di adiacenza | O(V²) | Più semplice; buona per i grafi densi |
| Spazio | O(V + E) | Appartenenza all'albero + coda di priorità |
| Ideale per | Grafi densi | Cresce da un unico nodo di partenza |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Inizia l'albero con un nodo qualsiasi. |
| 2 | Esamina tutti gli archi che vanno dall'albero a un nodo esterno. |
| 3 | Scegli l'arco di attraversamento con il peso più piccolo. |
| 4 | Aggiungi all'albero quell'arco e il suo nuovo nodo. |
| 5 | Ripeti finché tutti i nodi non sono nell'albero. |
Esempio svolto
Costruzione dell'MST di un grafo con 4 nodi e gli archi A-B=1, A-C=3, B-C=2, B-D=4, C-D=5, partendo da A:
| Passo | Albero | Archi di attraversamento | Arco scelto |
|---|---|---|---|
| 1 | {A} | A-B=1, A-C=3 | A-B (peso 1) |
| 2 | {A, B} | A-C=3, B-C=2, B-D=4 | B-C (peso 2) |
| 3 | {A, B, C} | B-D=4, C-D=5 | B-D (peso 4) |
| 4 | {A, B, C, D} | nessuno: tutti i nodi sono nell'albero | fatto: peso dell'MST 1+2+4 = 7 |
Quando usare l'algoritmo di Prim
| Usalo quando | Evitalo quando |
|---|---|
| Ti serve un albero ricoprente minimo di un grafo pesato, connesso e non orientato. | Il grafo è orientato o ti servono i cammini minimi: usa invece Dijkstra o Bellman-Ford. |
Il grafo è denso (E vicino a V²); la forma a matrice O(V²) è semplice e veloce. | Il grafo è sparso e gli archi sono già ordinati o facili da ordinare: Kruskal spesso è più semplice. |
| Vuoi che l'albero cresca da una zona verso l'esterno (ad es. layout incrementale di una rete). | Il grafo non è connesso: Prim copre una sola componente, e ti serve una foresta ricoprente minima. |
| Hai già a disposizione una struttura di adiacenza e una coda di priorità. | Devi rilevare cicli su un insieme globale di archi: l'union-find (Kruskal) è più adatto a questo schema. |
Codice Prim's Algorithm
Un'implementazione di Prim's Algorithm pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Prim's Algorithm in 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)Codice Prim's Algorithm in 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);Codice Prim's Algorithm in 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}Codice Prim's Algorithm in 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}Codice Prim's Algorithm in 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}Domande frequenti sull'algoritmo di Prim
Qual è la complessità temporale dell'algoritmo di Prim?
O(E log V). Una versione più semplice con matrice di adiacenza, che a ogni passo cerca l'arco di attraversamento minimo, è O(V²) e può essere più veloce sui grafi densi. Entrambe usano spazio O(V + E).Qual è la differenza tra l'algoritmo di Prim e quello di Kruskal?
Entrambi trovano un albero ricoprente minimo in modo greedy. Prim fa crescere un unico albero connesso da un nodo di partenza, aggiungendo ripetutamente l'arco più economico che esce dall'albero (con una coda di priorità). Kruskal considera tutti gli archi ordinati per peso e aggiunge il più economico che non forma un ciclo (con l'union-find). Prim è spesso preferito sui grafi densi, Kruskal su quelli sparsi.
L'algoritmo di Prim trova sempre l'MST ottimale?
Sì. A ogni passo l'arco più economico che attraversa l'albero corrente è sicuro da aggiungere: appartiene a qualche albero ricoprente minimo (la proprietà del taglio). Aggiungere ripetutamente archi sicuri produce un vero albero ricoprente minimo, a patto che il grafo sia connesso.
Quando conviene usare l'algoritmo di Prim invece di quello di Kruskal?
O(V²) con matrice di adiacenza evita di ordinare tutti gli E archi e fa crescere un solo albero da un nodo di partenza. Kruskal dà il meglio sui grafi sparsi, dove ordinare la lista degli archi costa poco e l'union-find mantiene veloci i controlli sui cicli. Entrambi producono un MST corretto, quindi la scelta dipende soprattutto dalla densità degli archi e dalle strutture dati che hai già.Il nodo di partenza influisce sull'MST risultante?
No: il peso totale dell'MST è lo stesso qualunque sia il nodo di partenza, perché il peso dell'albero ricoprente minimo di un grafo connesso è unico. Gli archi specifici possono cambiare solo quando più archi hanno lo stesso peso ed esistono più MST. Altrimenti Prim arriva esattamente allo stesso albero indipendentemente dal nodo iniziale.
L'algoritmo di Prim gestisce i grafi non connessi?
Non direttamente. Prim fa crescere un solo albero, quindi copre solo la componente connessa che contiene il nodo di partenza e lascia il resto intatto. Per coprire ogni componente dovresti eseguire Prim più volte da un nodo non visitato, producendo una foresta ricoprente minima invece di un unico albero.
Risorse correlate
Altre visualizzazioni
