Calcolatore dell'Albero Ricoprente Minimo
Calcola l'Albero Ricoprente Minimo (MST) di un grafo pesato utilizzando l'algoritmo di Kruskal o di Prim. Include visualizzazione interattiva del grafo, tracciamento dell'algoritmo passo dopo passo e animazione della selezione degli archi.
Il tuo ad blocker ci impedisce di mostrare annunci
MiniWebtool è gratuito grazie agli annunci. Se questo strumento ti è stato utile, sostienici con Premium (senza annunci + più veloce) oppure inserisci MiniWebtool.com nella whitelist e ricarica la pagina.
- Oppure passa a Premium (senza annunci)
- Consenti gli annunci per MiniWebtool.com, poi ricarica
Calcolatore dell'Albero Ricoprente Minimo
Benvenuti nel Calcolatore dell'Albero Ricoprente Minimo, uno strumento interattivo per calcolare l'MST di un grafo pesato utilizzando l'algoritmo di Kruskal o quello di Prim. Sia che tu stia studiando la teoria dei grafi, progettando infrastrutture di rete o ottimizzando l'allocazione delle risorse, questo calcolatore offre un'esplorazione visiva e passo-passo di due algoritmi fondamentali nell'ottimizzazione combinatoria.
Cos'è un Albero Ricoprente Minimo (MST)?
Un Albero Ricoprente Minimo di un grafo connesso, non orientato e pesato è un sottoinsieme di archi che:
- Collega tutti i vertici tra loro (ricoprente)
- Non contiene cicli (albero)
- Ha il peso totale minimo possibile degli archi
Per un grafo con V vertici, un MST ha sempre esattamente V - 1 archi. Se il grafo è disconnesso, il risultato è una Foresta Ricoprente Minima — una collezione di MST per ogni componente connessa.
Algoritmo di Kruskal
L'algoritmo di Kruskal è un algoritmo avido basato sugli archi che costruisce l'MST elaborando gli archi in ordine di peso crescente. Utilizza una struttura dati Union-Find (Disjoint Set Union) per rilevare in modo efficiente i cicli.
Pseudocodice di Kruskal
MST ← insieme vuoto
Ordina tutti gli archi per peso (crescente)
Inizializza Union-Find per tutti i vertici
per ogni arco (u, v, w) negli archi ordinati:
se Find(u) ≠ Find(v): // componenti diverse
MST ← MST ∪ {(u, v, w)}
Union(u, v) // unisci componenti
ritorna MST
Algoritmo di Prim
L'algoritmo di Prim è un algoritmo avido basato sui vertici che fa crescere l'MST partendo da un vertice iniziale. Ad ogni passaggio, aggiunge l'arco più economico che collega un vertice nell'albero a un vertice esterno all'albero.
Pseudocodice di Prim
MST ← insieme vuoto
inMST ← {start}
PQ ← coda di priorità con gli archi da start
mentre PQ non è vuota e |inMST| < |V|:
(w, u, v) ← estrai min da PQ
se v ∉ inMST:
MST ← MST ∪ {(u, v, w)}
inMST ← inMST ∪ {v}
Aggiungi tutti gli archi da v a PQ
ritorna MST
Kruskal vs Prim: Quando Usare Quale?
| Caratteristica | Kruskal | Prim |
|---|---|---|
| Approccio | Basato sugli archi (ordinamento globale) | Basato sui vertici (crescita locale) |
| Struttura Dati | Union-Find | Coda di priorità |
| Complessità Temporale | \( O(E \log E) \) | \( O((V + E) \log V) \) |
| Ideale per | Grafi sparsi | Grafi densi |
| Grafi Disconnessi | Produce una foresta ricoprente | Ricopre solo la componente del nodo iniziale |
| Parallelizzabile | Più facilmente parallelizzabile | Sequenziale per natura |
Come Usare Questo Calcolatore
- Definisci gli archi del tuo grafo: Inserisci gli archi nel formato
nodo1, nodo2, peso, uno per riga. L'MST opera su grafi non orientati, quindi ogni arco funziona in entrambe le direzioni. - Scegli un algoritmo: Seleziona Kruskal per grafi sparsi o Prim per grafi densi. Entrambi producono un MST ottimale.
- Imposta il nodo di partenza (solo Prim): Specifica facoltativamente dove inizia l'algoritmo di Prim. Ciò influisce sull'ordine di selezione degli archi ma non sul peso totale dell'MST.
- Calcola l'MST: Fai clic su "Trova MST" per eseguire l'algoritmo. Esplora la visualizzazione interattiva, la tabella degli archi e il tracciamento passo-passo.
- Percorri i passaggi: Usa i pulsanti Successivo/Precedente per osservare l'esecuzione dell'algoritmo passo dopo passo, con evidenziazione in tempo reale sul canvas.
Comprendere i Risultati
Tabella Archi MST
Mostra ogni arco selezionato per l'MST, nell'ordine in cui sono stati aggiunti, insieme ai pesi individuali e al peso totale dell'MST.
Visualizzazione del Grafo
Il canvas interattivo mostra il tuo grafo con elementi codificati a colori:
- Nodi e archi verdi = Parte dell'MST
- Evidenziazioni arancioni = Attualmente in fase di esame
- Elementi grigi = Non ancora parte dell'MST
Tracciamento Passo-Passo
Mostra ogni decisione dell'algoritmo: quale arco viene esaminato, se è stato accettato o rifiutato (e perché), e lo stato attuale della costruzione dell'MST.
Applicazioni Reali dell'MST
Progettazione di Reti
L'applicazione più classica. Quando si collegano nodi (città, server, dispositivi elettrici) con la minima lunghezza totale di cavi, fibre o tubi, l'MST fornisce la soluzione ottimale. Le aziende di telecomunicazioni utilizzano algoritmi basati su MST per ridurre al minimo i costi delle infrastrutture.
Analisi dei Cluster
Nel machine learning e nella scienza dei dati, il clustering basato su MST (come il single-linkage clustering) raggruppa i punti dati rimuovendo gli archi più lunghi dall'MST. Questo produce cluster naturali senza dover specificare preventivamente il numero di gruppi.
Segmentazione delle Immagini
Gli algoritmi di computer vision utilizzano l'MST per segmentare le immagini in regioni significative. I pixel sono nodi, i pesi degli archi rappresentano la differenza di colore/intensità, e il taglio degli archi MST separa gli oggetti distinti.
Algoritmi di Approssimazione
L'MST fornisce una 2-approssimazione per il problema del commesso viaggiatore (TSP) metrico. Il peso dell'MST è un limite inferiore per il tour TSP ottimale, e raddoppiando gli archi dell'MST si ottiene un tour entro il doppio dell'ottimale.
Progettazione di Circuiti
La progettazione di chip VLSI utilizza l'MST (tramite varianti dell'albero di Steiner) per ridurre al minimo la lunghezza totale dei cavi che collegano i componenti su un circuito stampato, riducendo il ritardo del segnale e i costi di produzione.
Proprietà Chiave dell'MST
- Proprietà del Taglio: Per qualsiasi taglio del grafo, l'arco di peso minimo che attraversa il taglio fa parte dell'MST.
- Proprietà del Ciclo: Per qualsiasi ciclo nel grafo, l'arco di peso massimo nel ciclo NON fa parte dell'MST (assumendo pesi unici).
- Unicità: Se tutti i pesi degli archi sono distinti, l'MST è unico. Con pesi duplicati, possono esserci più MST validi con lo stesso peso totale.
- Sottografo: L'MST è un sottografo con V-1 archi e nessun ciclo.
Domande Frequenti
Cos'è un Albero Ricoprente Minimo (MST)?
Un Albero Ricoprente Minimo è un sottoinsieme di archi di un grafo connesso, non orientato e pesato che collega tutti i vertici tra loro con il minor peso totale possibile degli archi, senza formare cicli. Un MST ha esattamente V-1 archi per un grafo con V vertici.
Qual è la differenza tra l'algoritmo di Kruskal e quello di Prim?
L'algoritmo di Kruskal è basato sugli archi: ordina tutti gli archi per peso e aggiunge avidamente quelli che non creano cicli, utilizzando una struttura dati Union-Find. L'algoritmo di Prim è basato sui vertici: fa crescere l'MST da un nodo di partenza aggiungendo sempre l'arco più economico che collega l'albero a un nuovo vertice, utilizzando una coda di priorità. Entrambi producono MST ottimali ma possono differire nell'ordine di selezione degli archi.
Quando dovrei usare Kruskal rispetto a Prim?
Kruskal è generalmente migliore per i grafi sparsi (pochi archi rispetto ai nodi) con una complessità temporale O(E log E). Prim è migliore per i grafi densi con una complessità temporale O(E log V) utilizzando un heap binario. Per grafi molto densi, Prim con un heap di Fibonacci raggiunge O(E + V log V).
Un grafo può avere più MST validi?
Sì, un grafo può avere più MST validi se ci sono archi con pesi uguali. MST diversi avranno lo stesso peso totale ma potrebbero includere archi diversi. Kruskal e Prim possono produrre MST differenti per lo stesso grafo, ma entrambi avranno lo stesso peso totale minimo.
Quali sono le applicazioni reali dell'MST?
Gli MST vengono utilizzati nella progettazione di reti (minimizzazione della lunghezza di cavi/fibre), layout di circuiti stampati, analisi dei cluster, segmentazione delle immagini, costruzione di tassonomie, approssimazione di problemi NP-hard come il problema del commesso viaggiatore (TSP) e costruzione di reti stradali/oleodotti/elettriche al costo minimo.
L'MST funziona su grafi disconnessi?
Un vero MST richiede un grafo connesso. Se il grafo è disconnesso, gli algoritmi produrranno una Foresta Ricoprente Minima — una collezione di MST, uno per ogni componente connessa. Questo calcolatore indicherà quando il grafo non è completamente connesso.
Risorse Aggiuntive
Cita questo contenuto, pagina o strumento come:
"Calcolatore dell'Albero Ricoprente Minimo" su https://MiniWebtool.com/it// di MiniWebtool, https://MiniWebtool.com/
dal team di miniwebtool. Aggiornato: 19 feb 2026
Puoi anche provare il nostro Risolutore di Matematica AI GPT per risolvere i tuoi problemi matematici attraverso domande e risposte in linguaggio naturale.