- Attuale
- Nell'albero
- Chiuderebbe un ciclo
Algoritmo di Kruskal
L'algoritmo di Kruskal costruisce un albero ricoprente minimo, l'insieme di archi più economico che collega tutti i nodi, nel modo più semplice che si possa immaginare: prende gli archi dal più corto al più lungo e tiene ognuno, a meno che chiuda un ciclo. Procedi passo per passo per vedere pezzi separati crescere e fondersi in un solo albero, e gli archi saltati. Premi Avvia per guardare l'albero crescere, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Il numero su ogni arco è la sua lunghezza. Sotto il grafo ci sono gli archi ancora da provare, dal più corto al più lungo; un arco i cui estremi sono già collegati chiuderebbe un ciclo ed è tratteggiato in rosso. Nuovo grafo crea un altro grafo; scegli quanti nodi e archi deve avere. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta.
- Trascina il cursore dei passi per saltare in qualsiasi punto. Gli archi ancora da provare sono elencati sotto il grafo, dal più corto.
- Fai attenzione agli archi tratteggiati in rosso: chiuderebbero un ciclo. Nuovo grafo crea un altro grafo da provare.
Come funziona l'algoritmo di Kruskal
Ordina tutti gli archi dal più corto al più lungo. All'inizio ogni nodo è un pezzo a sé. Prova gli archi in ordine: se un arco unisce due pezzi diversi, entra nell'albero e i due pezzi diventano uno; se i suoi due estremi sono già nello stesso pezzo, chiuderebbe un ciclo, quindi si salta. Ci si ferma quando tutto è un solo pezzo, cosa che succede dopo un arco in meno dei nodi, spesso molto prima di provare l'ultimo arco.
Union-find
Per ogni arco, l'algoritmo di Kruskal deve chiedersi se i suoi due estremi sono già collegati. Una struttura union-find risponde in fretta: ogni pezzo ha un nodo rappresentante, find segue i collegamenti fino a lui, e union collega un rappresentante all'altro. Con due semplici trucchi, la compressione dei cammini e l'unione per dimensione, ogni domanda richiede un tempo quasi costante, quindi ordinare gli archi è la parte più lenta, con un lavoro che cresce come E log E.
Domande frequenti
Che cos'è l'algoritmo di Kruskal?
Un algoritmo greedy che costruisce un albero ricoprente minimo ordinando tutti gli archi dal più corto al più lungo e aggiungendo ogni arco che non chiude un ciclo con gli archi già scelti.
Come fa l'algoritmo di Kruskal a riconoscere un ciclo?
Un arco chiude un ciclo esattamente quando i suoi due estremi sono già collegati da archi scelti. Una struttura union-find tiene traccia di quali nodi sono collegati e risponde a questa domanda quasi all'istante.
Perché l'algoritmo di Kruskal funziona?
Per la proprietà del ciclo: l'arco più lungo di un ciclo non serve mai per un albero ricoprente minimo. Ogni arco che Kruskal salta è il più lungo del ciclo che chiuderebbe, perché tutti gli archi prima di lui erano più corti o uguali.
Quando usare Kruskal invece di Prim?
L'algoritmo di Kruskal è semplice e veloce sui grafi sparsi, e lavora direttamente su un semplice elenco di archi. L'algoritmo di Prim è adatto ai grafi densi e ai grafi memorizzati come liste di adiacenza. Entrambi trovano un albero della stessa lunghezza totale.
Il mio grafo viene inviato da qualche parte?
No. Il grafo viene creato e l'albero costruito nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor