Strategia
Seguendo un ordine non decrescente per costi, se l’arco corrente
Esempio
Ordinamento
Colorazione
Oppure, per una strategia senza colori: ordina gli edge in ordine non-decrescente, come da pseudocodice (vedi sotto), crea un set per ogni vertice del grafo, e controlla via via in ordine di peso se due vertici sono nello stesso subset.
Se sono in subset diversi, aggiungi l’arco nell’MST, e unisci il subset precedentemente disgiunto.
Seguendo questo ragionamento senza sbagliare, avremo un MST corretto senza cicli.
La riga 6 dello pseudocodice (l’istruzione if ) garantisce che il vertice
Correttezza
- Sia
l’ordinamento per pesi utilizzato; - Siano
le operazione di colorazione effettuate dall’algoritmo di Kruskal. - Procediamo per induzione su
Caso:
- Sia
- Si ha che
e appartengono a due alberi blu distinti - Si consideri il taglio
- Esso è attraversato dall’arco
- Si osservi che tutti gli archi
tali che sono già colorati. - Pertanto
ha peso minimo tra tutti gli archi non colorati che attraversano il taglio - Pertanto
può essere colorato da un passo
Caso:
- Sia
e appartengono ad uno stesso albero blu - Sia
il cammino da a in - Si consideri il ciclo
- Tale ciclo non contiene archi rossi ed inoltre
è l’unico arco non colorato - Pertanto
può essere colorato da un passo
Implementazione
Pseudocodice:
T = EMPTY_SET(); // T is going to be the MST
foreach (v in V)
MAKE_SET(v) // create a subtree for each vertex
E = sort(E,w); // non-decreasing order
foreach ((u,v) in E) // in sorted edges...
if (FIND_SET(u) != FIND_SET(v)) // if u and v are in different subtrees (sets), avoid cycles
T = T U {(u,v)} // insert the edge inside the MST
UNION(u,v) // union between the two different subtrees (sets), we're sure there are no cycles.
return T; // return the MST
Complessità
Infatti si ha:
: ordinamento degli archi - Union-Find:
MAKE_SET FIND_SET UNION operazioni, di cui MAKE_SET