|
|
Il minimo albero di copertura o MST, che è l’acronimo di Minimum Spanning Tree (equivalente in inglese) è un algoritmo che può essere implementato utilizzado la tecnica di progettazione di algoritmi di tipo Greedy. Dato un grafo non orientato e connesso G = (N,A), con pesi non negativi sugli archi [i,j], trovare un albero di copertura T per G, avente tutti gli n nodi di N, ma solo n-1 degli m archi in A, tali che la somma dei pesi degli archi nell’ albero sia la più piccola possibile.
Esistono vari algoritmi che risolvono all’ottimo il problema dell’albero di copertura minimo: Kruskal (1956), Prim (1957), … L’algoritmo di Kruskal che analizzeremo è basato sul principio greedy. L’ idea di base dell’algoritmo di Kruskal è la seguente: viene eseguito un ordinamento degli archi a crescente rispetto al peso pa l’ insieme S viene creato aggiungendo a in S se a non determina alcun circuito in T. Detto in altre parole l’aggiunta di un nuovo arco non deve determinare un circuito (questa fase è detta test).
Vediamo un esempio pratico su un grafo:
L’algoritmo costruisce la soluzione per unione di componenti connesse. La sua correttezza può essere dimostrata come segue. Sia Fk la minima foresta di copertura di G, formata da k componenti connesse (k alberi). Per induzione si dimostra che sono computati gli alberi, in ordine, Fn, Fn-1…,F1 dove l’ insieme An degli archi di Fn è vuoto e l’insieme Ak-1 degli archi di Fk-1è uguale a:
con i e j che appartengono a due diverse componenti connesse di Fk. (in modo da non provocare un circuito). Per implementare il test che determina l’eventuale esistenza di un ciclo, si ricorre agli insiemi Mfset. Se l’insieme dei nodi dei k alberi di Fk sono rappresentati tramite Mfset, allora l’appartenenza dei nodi i e j a due componenti distinte costa O( log n ) utilizzando le operazioni TROVA e FONDI dell’ “Mfset”. Il test viene ripetuto per gli m archi, quindi abbiamo O( m log n ). L’ordinamento degli archi richiede anch’esso O( m log n ) quindi la complessità dell’algoritmo è O( m log n ). Vediamo come poter implementare questo algoritmo in linguaggio C. Il grafo G viene visto come un array di archi, mentre l’ albero T può essere visto come semplice un insieme di archi realizzato, ad esempio, con una lista non ordinata. Viene poi utilizzato un contatore per terminare la computazione dopo aver aggiunto n-1 archi. Definiamo inizialmente la struttura che avrà ogni arco:
i e j sono gli estremi dell’ arco e p il peso dell’ arco. La funzione kruskal è la seguente:
Mfset S è utilizzato per mantenere le componenti connesse di T, tale che S è inizializato con n componenti distinte, ciascuna formata da un singolo nodo del grafo.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.