Algoritmo di Kruskal
Ultimo aggiornamento
L'algoritmo di Kruskal costruisce un albero ricoprente minimo (MST), cioè l'insieme di archi più economico che collega tutti i nodi senza cicli. Ordina tutti gli archi per peso, poi aggiunge in modo greedy l'arco successivo più economico, a patto che unisca due nodi non ancora collegati. Premi play qui sopra per vedere l'albero crescere, un arco sicuro più economico alla volta.
Il controllo "già collegati?" si fa con una struttura dati union-find (insiemi disgiunti): ogni arco viene saltato se i suoi due estremi sono già nella stessa componente, perché aggiungerlo formerebbe un ciclo. L'ordinamento domina il costo, per un totale di O(E log E). Kruskal dà il meglio sui grafi sparsi.
Complessità temporale e spaziale
| Misura | Complessità | Note |
|---|---|---|
| Tempo | O(E log E) | Dominato dall'ordinamento degli archi |
| Operazioni union-find | ≈ O(E α(V)) | Quasi costanti per controllo con la compressione dei cammini |
| Spazio | O(V + E) | Lista degli archi + struttura a insiemi disgiunti |
| Ideale per | Grafi sparsi | Lavora su una lista globale degli archi |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Ordina tutti gli archi per peso, in ordine crescente. |
| 2 | Metti ogni nodo in una componente a sé (union-find). |
| 3 | Prendi l'arco successivo più economico. |
| 4 | Se i suoi estremi sono in componenti diverse, aggiungilo all'albero e uniscile. |
| 5 | Altrimenti saltalo (creerebbe un ciclo). |
| 6 | Fermati quando l'albero ha V − 1 archi. |
Esempio svolto
Grafo con i nodi A, B, C, D e gli archi A-B(1), B-C(2), A-C(3), C-D(4), B-D(5). Archi ordinati: A-B(1), B-C(2), A-C(3), C-D(4), B-D(5):
| Arco (peso) | Componenti prima | Azione |
|---|---|---|
A-B(1) | {A} {B} {C} {D} | Componenti diverse: aggiungi all'MST, unisci in {A,B}. |
B-C(2) | {A,B} {C} {D} | Componenti diverse: aggiungi all'MST, unisci in {A,B,C}. |
A-C(3) | {A,B,C} {D} | A e C sono già insieme: salta (formerebbe un ciclo). |
C-D(4) | {A,B,C} {D} | Componenti diverse: aggiungi all'MST, unisci in {A,B,C,D}. |
| Stop | {A,B,C,D} | L'albero ha V - 1 = 3 archi. MST = A-B, B-C, C-D, peso totale 7. |
Quando usare l'algoritmo di Kruskal
| Usalo quando | Evitalo quando |
|---|---|
| Il grafo è sparso (pochi archi rispetto ai nodi). | Il grafo è denso: Prim con un heap di solito è più veloce. |
| Gli archi sono già disponibili come lista globale da ordinare. | Gli archi arrivano solo tramite liste di adiacenza da scorrere nodo per nodo. |
| Vuoi un'implementazione semplice basata su union-find. | Ti serve che l'albero cresca da uno specifico nodo di partenza. |
| Vuoi costruire una foresta ricoprente di un grafo non connesso. | Devi gestire archi che arrivano in streaming senza un ordinamento completo. |
Codice Kruskal's Algorithm
Un'implementazione di Kruskal'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 Kruskal's Algorithm in Python
Python
1def find(parent, x):2 while parent[x] != x:3 parent[x] = parent[parent[x]] # path compression4 x = parent[x]5 return x6
7
8def kruskal(vertices, edges):9 # Take the cheapest edge that does not close a cycle10 parent = {v: v for v in vertices}11 mst, total = [], 012 for w, u, v in sorted(edges):13 root_u, root_v = find(parent, u), find(parent, v)14 if root_u != root_v:15 parent[root_u] = root_v16 mst.append((u, v, w))17 total += w18 return mst, total19
20
21vertices = ["A", "B", "C", "D", "E"]22edges = [23 (4, "A", "B"), (1, "A", "C"), (3, "B", "C"), (2, "B", "D"),24 (5, "C", "D"), (6, "C", "E"), (7, "D", "E"),25]26
27mst, total = kruskal(vertices, edges)28for u, v, w in mst:29 print(f"{u} - {v} (weight {w})")30print("Total MST weight:", total)Codice Kruskal's Algorithm in JavaScript
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 4], ["A", "C", 2], ["B", "C", 1], ["B", "D", 5],4 ["C", "D", 8], ["C", "E", 10], ["D", "E", 2],5];6
7function kruskal() {8 // Union-find with path compression detects cycles cheaply9 const parent = Object.fromEntries(nodes.map((n) => [n, n]));10 const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));11 const mst = [];12 let total = 0;13 const sorted = [...edges].sort((a, b) => a[2] - b[2]);14 for (const [u, v, w] of sorted) {15 const rootU = find(u);16 const rootV = find(v);17 if (rootU !== rootV) {18 parent[rootU] = rootV;19 mst.push(`${u}-${v} (${w})`);20 total += w;21 }22 }23 return { mst, total };24}25
26const { mst, total } = kruskal();27console.log("MST edges:", mst.join(", "));28console.log("Total weight:", total);Codice Kruskal's Algorithm in Java
Java
1import java.util.Arrays;2
3public class Main {4 static int[] parent;5
6 static int find(int x) {7 if (parent[x] != x) parent[x] = find(parent[x]); // path compression8 return parent[x];9 }10
11 static boolean union(int a, int b) {12 int rootA = find(a), rootB = find(b);13 if (rootA == rootB) return false; // would create a cycle14 parent[rootA] = rootB;15 return true;16 }17
18 public static void main(String[] args) {19 int n = 6;20 int[][] edges = {21 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},22 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}23 };24 Arrays.sort(edges, (a, b) -> a[2] - b[2]);25 parent = new int[n];26 for (int i = 0; i < n; i++) parent[i] = i;27
28 int total = 0, used = 0;29 for (int[] e : edges) {30 if (union(e[0], e[1])) {31 System.out.println("Take edge " + e[0] + "-" + e[1] + " (weight " + e[2] + ")");32 total += e[2];33 if (++used == n - 1) break;34 }35 }36 System.out.println("MST total weight: " + total);37 }38}Codice Kruskal's Algorithm in C++
C++
1#include <algorithm>2#include <iostream>3#include <numeric>4#include <vector>5
6struct Edge {7 int u, v, weight;8};9
10struct DSU {11 std::vector<int> parent;12 explicit DSU(int n) : parent(n) {13 std::iota(parent.begin(), parent.end(), 0);14 }15 int find(int x) {16 if (parent[x] != x) parent[x] = find(parent[x]); // path compression17 return parent[x];18 }19 bool unite(int a, int b) {20 int ra = find(a), rb = find(b);21 if (ra == rb) return false; // would create a cycle22 parent[ra] = rb;23 return true;24 }25};26
27int main() {28 const int n = 5;29 std::vector<Edge> edges = {30 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},31 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},32 };33 // Greedily take the cheapest edge that connects two components34 std::sort(edges.begin(), edges.end(),35 [](const Edge& a, const Edge& b) { return a.weight < b.weight; });36 DSU dsu(n);37 int total = 0;38 std::cout << "MST edges:\n";39 for (const Edge& e : edges) {40 if (dsu.unite(e.u, e.v)) {41 std::cout << " " << e.u << " - " << e.v42 << " (weight " << e.weight << ")\n";43 total += e.weight;44 }45 }46 std::cout << "Total weight: " << total << "\n";47 return 0;48}Codice Kruskal's Algorithm in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5#define N 56
7typedef struct {8 int u, v, weight;9} Edge;10
11int parent[N];12
13int find(int x) {14 if (parent[x] != x) parent[x] = find(parent[x]); // path compression15 return parent[x];16}17
18bool unite(int a, int b) {19 int ra = find(a), rb = find(b);20 if (ra == rb) return false; // would create a cycle21 parent[ra] = rb;22 return true;23}24
25int cmpEdge(const void* a, const void* b) {26 return ((const Edge*)a)->weight - ((const Edge*)b)->weight;27}28
29int main(void) {30 Edge edges[] = {31 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},32 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},33 };34 int m = sizeof(edges) / sizeof(edges[0]);35 for (int i = 0; i < N; i++) parent[i] = i;36 // Greedily take the cheapest edge that connects two components37 qsort(edges, m, sizeof(Edge), cmpEdge);38 int total = 0;39 printf("MST edges:\n");40 for (int i = 0; i < m; i++) {41 if (unite(edges[i].u, edges[i].v)) {42 printf(" %d - %d (weight %d)\n",43 edges[i].u, edges[i].v, edges[i].weight);44 total += edges[i].weight;45 }46 }47 printf("Total weight: %d\n", total);48 return 0;49}Domande frequenti sull'algoritmo di Kruskal
Cos'è un albero ricoprente minimo?
Un albero ricoprente minimo (MST) di un grafo pesato connesso è un sottoinsieme di archi che collega tutti i nodi senza cicli e con il peso totale più piccolo possibile. Ha esattamente
V - 1 archi per V nodi.Qual è la differenza tra l'algoritmo di Kruskal e quello di Prim?
Entrambi costruiscono un albero ricoprente minimo in modo greedy. Kruskal ordina globalmente tutti gli archi e aggiunge il più economico che non forma un ciclo, usando l'union-find. Prim fa crescere un unico albero verso l'esterno a partire da un nodo iniziale, aggiungendo sempre l'arco più economico che esce dall'albero. Kruskal è adatto ai grafi sparsi; Prim (con un heap) a quelli densi.
Perché l'algoritmo di Kruskal usa l'union-find?
Prima di aggiungere un arco, Kruskal deve controllare se i suoi due estremi sono già collegati: aggiungere un arco del genere creerebbe un ciclo. L'union-find (insiemi disgiunti) risponde a "sono nella stessa componente?" e unisce le componenti in un tempo ammortizzato quasi costante, mantenendo l'algoritmo efficiente.
Quando conviene usare l'algoritmo di Kruskal invece di quello di Prim?
Preferisci Kruskal quando il grafo è sparso e hai già tutti gli archi in una lista da ordinare: l'ordinamento
O(E log E) costa poco quando E è piccolo. L'algoritmo di Prim con un heap binario o di Fibonacci tende a vincere sui grafi densi dove E si avvicina a V², perché evita di ordinare tutti gli archi in anticipo.L'algoritmo di Kruskal funziona sui grafi non connessi?
Sì. Se il grafo non è connesso, Kruskal semplicemente non riesce ad arrivare a
V - 1 archi e produce invece una foresta ricoprente minima, un MST per ogni componente connessa. Succede in modo naturale, perché l'union-find non unisce mai nodi tra cui non esiste un percorso.Qual è l'errore più comune quando si implementa l'algoritmo di Kruskal?
Tralasciare la compressione dei cammini e l'unione per rango dell'union-find, cosa che porta ogni controllo di connessione da quasi costante a quasi lineare e può dominare il tempo di esecuzione. Un altro bug frequente è dimenticare di unire davvero le due componenti dopo aver aggiunto un arco, lasciando che gli archi successivi creino cicli.
Risorse correlate
Altre visualizzazioni
