Archi dell'albero
Lunghezza totale
Archi esaminati

  • Attuale
  • Nell'albero
  • Chiuderebbe un ciclo

Scopri di più sull'algoritmo di Kruskal

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

  1. Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta.
  2. Trascina il cursore dei passi per saltare in qualsiasi punto. Gli archi ancora da provare sono elencati sotto il grafo, dal più corto.
  3. 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