- Attuale
- Nell'albero
- Vicino all'albero
- Miglior arco finora
- Chiuderebbe un ciclo
Albero ricoprente minimo
Vuoi collegare ogni città con un cavo, ogni casa con le tubature dell'acqua o ogni computer di una rete, usando meno materiale possibile. La risposta è un albero ricoprente minimo: l'insieme di archi che collega tutti i nodi con la minima lunghezza totale. Scegli l'algoritmo di Kruskal o di Prim e procedi passo per passo per veder crescere l'albero, aggiungendo ogni volta l'arco ammesso più corto. 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. Scegli l'algoritmo: Kruskal prova gli archi dal più corto al più lungo, Prim fa crescere un solo albero dalla partenza; fai clic su un nodo per farne la partenza di Prim. Il numero su ogni arco è la sua lunghezza. Sotto il grafo c'è l'elenco degli archi ancora da provare, oppure i nodi in attesa con la lunghezza del loro arco migliore verso l'albero. 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
- Scegli l'algoritmo di Kruskal o di Prim. Per Prim, fai clic su un nodo per farne la partenza.
- Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto.
- Osserva gli archi entrare nell'albero e la lunghezza totale crescere. Nuovo grafo crea un altro grafo da provare.
Algoritmo di Kruskal
Ordina tutti gli archi dal più corto al più lungo e provali in quell'ordine. Se un arco unisce due pezzi non ancora collegati, entra nell'albero. Se i suoi due estremi sono già collegati attraverso l'albero, chiuderebbe un ciclo, quindi si salta. Ci si ferma quando l'albero ha un arco in meno dei nodi. Per capire in fretta se due nodi sono già collegati, l'algoritmo di Kruskal tiene i pezzi in una struttura union-find.
Algoritmo di Prim
Parti da un albero di un solo nodo. Ogni nodo fuori dall'albero ricorda il suo arco più corto verso l'albero. Aggiungi ogni volta il nodo con l'arco più corto, insieme a quell'arco, ed esamina i suoi archi: uno di essi può dare a un vicino una via più breve verso l'albero. L'algoritmo di Prim somiglia all'algoritmo di Dijkstra, ma confronta singoli archi, non intere distanze dalla partenza. Entrambi gli algoritmi finiscono sempre con la stessa lunghezza totale.
Domande frequenti
Che cos'è un albero ricoprente minimo?
In un grafo connesso i cui archi hanno una lunghezza, un albero ricoprente è un insieme di archi che collega tutti i nodi senza alcun ciclo; con n nodi ha sempre n − 1 archi. Un albero ricoprente minimo è un albero ricoprente con la lunghezza totale più piccola possibile.
Qual è la differenza tra l'algoritmo di Kruskal e quello di Prim?
L'algoritmo di Kruskal guarda gli archi di tutto il grafo dal più corto al più lungo e unisce pezzi separati in un solo albero. L'algoritmo di Prim fa crescere un solo albero da una partenza, aggiungendo sempre l'arco più corto che ne esce. Entrambi sono greedy e trovano un albero con la stessa lunghezza totale; Kruskal è adatto ai grafi sparsi, Prim a quelli densi.
L'albero ricoprente minimo è unico?
Se tutte le lunghezze degli archi sono diverse, sì. Se alcune sono uguali, possono esserci più alberi con lo stesso totale minimo, e gli algoritmi possono sceglierne di diversi a seconda di come risolvono i pareggi.
Un albero ricoprente minimo dà i percorsi più brevi?
No. L'albero ricoprente minimo tiene bassa la lunghezza totale di tutti gli archi, ma il percorso tra due nodi nell'albero può essere molto più lungo del loro percorso più breve. Per i percorsi più brevi, usa l'algoritmo di Dijkstra.
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