Algoritmo di Kruskal
Ordina gli archi, prendi il più corto, non chiudere mai un giro. L'algoritmo di Kruskal è forse il più semplice algoritmo greedy che esista, eppure trova sempre il modo più economico di collegare tutti i nodi di un grafo.
L'idea
Un albero ricoprente minimo collega tutti i nodi di un grafo pesato con la minima lunghezza totale degli archi. L'algoritmo di Kruskal non fa crescere un solo albero da una partenza. Guarda tutto il grafo insieme, parte con ogni nodo come pezzo a sé e continua a unire pezzi con l'arco più corto disponibile finché ne resta uno solo.
Passo per passo
Ordina gli archi dal più corto al più lungo. Provali in quell'ordine. Se i due estremi di un arco sono in pezzi diversi, aggiungilo all'albero: i due pezzi diventano uno. Se entrambi gli estremi sono già nello stesso pezzo, l'arco chiuderebbe un ciclo, quindi si salta. Con n nodi l'albero è completo dopo n − 1 archi, e gli archi rimanenti non serve nemmeno guardarli.
Un esempio
Prendi gli archi A–B di lunghezza 1, B–C 2, A–C 3, C–D 4 e B–D 5. Kruskal aggiunge A–B, poi B–C, che unisce C al pezzo A–B. Poi viene A–C, ma A e C sono già nello stesso pezzo, quindi chiuderebbe il ciclo A–B–C e si salta. C–D unisce D, e ora tutti e quattro i nodi formano un albero con tre archi, di lunghezza totale 7. B–D, l'arco più lungo, non viene nemmeno provato.
Union-find
L'unica domanda difficile che l'algoritmo di Kruskal si pone è: questi due nodi sono già nello stesso pezzo? Una struttura union-find risponde. Ogni pezzo è un piccolo albero di collegamenti che puntano a un rappresentante. Find segue i collegamenti fino al rappresentante; union mette un rappresentante sotto l'altro. La compressione dei cammini, che fa puntare ogni nodo visitato direttamente al rappresentante, e l'unione per dimensione tengono i collegamenti così corti che ogni domanda richiede un tempo quasi costante.
Storia e velocità
Joseph Kruskal pubblicò l'algoritmo nel 1956, in un breve articolo nei Proceedings of the American Mathematical Society. Ordinare gli archi è la parte più lenta, quindi il lavoro cresce come E log E per E archi. Se gli archi sono già ordinati, o le loro lunghezze sono piccoli numeri interi, è quasi lineare.
Provalo
Apri l'app e premi Passo. Gli archi ancora da provare sono elencati sotto il grafo, dal più corto. Ogni arco che unisce due pezzi diventa verde; ogni arco che chiuderebbe un ciclo è tratteggiato in rosso. Guarda vari piccoli pezzi crescere in parti diverse del grafo e fondersi, e nota che gli ultimi archi spesso non vengono mai provati.
Domande frequenti
Perché l'algoritmo di Kruskal ordina gli archi?
Perché ogni arco che aggiunge sia il più corto che unisce ancora due pezzi. Questa scelta greedy è sempre sicura grazie alla proprietà del taglio, e ogni arco saltato è il più lungo del ciclo che chiuderebbe, quindi non serve mai.
Che cos'è una struttura per insiemi disgiunti?
Un altro nome di union-find: una struttura che gestisce una raccolta di insiemi separati, qui i pezzi della foresta che cresce, e sa dire in fretta a quale insieme appartiene un elemento e unire due insiemi.
L'algoritmo di Kruskal funziona su un grafo non connesso?
Sì. Finisce semplicemente con un albero per ogni pezzo connesso del grafo, una foresta ricoprente minima, perché nessun arco può unire pezzi che non sono collegati.
L'algoritmo di Kruskal si usa anche per altro?
Fermarlo presto, prima che gli ultimi pezzi si fondano, raggruppa i nodi in cluster: è il clustering single-linkage. Eseguirlo su una griglia con lunghezze casuali degli archi genera un labirinto.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova l'algoritmo di Kruskal