Algoritmo Spanning Tree di Kruskal
L'algoritmo di Kruskal per trovare l'albero di copertura del costo minimo utilizza l'approccio avido. Questo algoritmo tratta il grafico come una foresta e ogni nodo che ha come un singolo albero. Un albero si connette a un altro solo e solo se ha il minor costo tra tutte le opzioni disponibili e non viola le proprietà MST.
Per comprendere l'algoritmo di Kruskal consideriamo il seguente esempio:
Passaggio 1: rimuovere tutti i loop e i bordi paralleli
Rimuovi tutti i loop e i bordi paralleli dal grafico dato.
In caso di bordi paralleli, mantenere quello a cui è associato il minor costo e rimuovere tutti gli altri.
Passaggio 2: disporre tutti i bordi nell'ordine di peso crescente
Il passaggio successivo consiste nel creare un insieme di bordi e pesi e disporli in ordine crescente di peso (costo).
Passaggio 3: aggiungere il bordo che ha il minor peso
Ora iniziamo ad aggiungere bordi al grafico partendo da quello che ha il peso minore. Continueremo a controllare che le proprietà di copertura rimangano intatte. Nel caso in cui, aggiungendo uno spigolo, la proprietà spanning tree non vale, considereremo di non includere l'arco nel grafico.
Il costo minimo è 2 e gli archi coinvolti sono B, D e D, T. Li aggiungiamo. L'aggiunta di questi non viola le proprietà dello spanning tree, quindi continuiamo con la nostra successiva selezione del bordo.
Il costo successivo è 3 e gli archi associati sono A, C e C, D. Li aggiungiamo di nuovo -
Il prossimo costo nella tabella è 4 e osserviamo che aggiungendolo creerà un circuito nel grafico. -
Lo ignoriamo. Nel processo ignoreremo / eviteremo tutti i bordi che creano un circuito.
Osserviamo che gli archi con costo 5 e 6 creano anche circuiti. Li ignoriamo e andiamo avanti.
Ora ci resta solo un nodo da aggiungere. Tra i due bordi di costo minimo disponibili 7 e 8, aggiungeremo il bordo con costo 7.
Aggiungendo lo spigolo S, A abbiamo incluso tutti i nodi del grafo e ora abbiamo uno spanning tree a costo minimo.