Algoritmi/Gli alberi ricoprenti minimi: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
using an external editor |
m Bot: sostituzione tag obsoleti |
||
Riga 4:
Si può rappresentare come lista di archi, come lista di adiacenza o come vettore dei padri.
<span style="text-decoration:underline;">Vettore dei padri:</span> Anziché per ogni radice puntare ai due figli come nel BST, per ogni figlio si punta al padre (<
Gli algoritmi di Kruskal e Prim, partendo da un sottoinsieme di albero ricoprente minimo avente nessun arco, costruiscono arco per arco l'albero ricoprente minimo seguendo la proprietà di '''invarianza''', cioè garantendo che l'arco via via inserito sia sicuro e mantenga la condizione di albero ricoprente minimo. Nonostante questi algoritmi siano di tipo greedy, la soluzione trovata è comunque quella ottima globalmente perché l'arco è garantito essere sicuro.
| |||