# Algoritmi/Gli alberi ricoprenti minimi

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario
Il grafo ricoprente minimo è un sottoinsieme non unico di un generico grafo avente stessi vertici e un sottoinsieme di archi, in cui tutti i vertici vengono coperti in modo che la somma dei costi degli archi utilizzati sia la minore possibile. Un grafo ricoprente minimo è sempre aciclico (viene scelto solo uno dei cammini che compongono il ciclo) → è un albero ricoprente minimo.
Si può rappresentare come lista di archi, come lista di adiacenza o come vettore dei padri.
Vettore dei padri: Anziché per ogni radice puntare ai due figli come nel BST, per ogni figlio si punta al padre (st è il vettore dei padri) perché il padre è uno, i figli sono in varie quantità.
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.
Il taglio è la partizione del grafo V in due insiemi S e V − S. La differenza tra gli algoritmi di Kruskal e di Prim è la scelta del taglio.
Dato un taglio che rispetti l'insieme degli archi corrente (cioè nessun arco attraversa il taglio), ogni arco sicuro deve essere l'arco leggero (cioè quello di peso minimo) che attraversa il taglio (cioè collega un nodo di S con un nodo di V − S).
Un arco sicuro collega due alberi non ancora connessi.

## Algoritmo di Kruskal

A ogni passo si prendono gli archi sicuri tra quelli rimasti nell'intero grafo.
All'inizio, ciascun nodo è un albero composto da un nodo.
Quando gli archi presi sono multipli, nell'algoritmo corrispondono a iterazioni multiple (non vengono presi insieme).
La complessità $T\left(n\right)=\left|E\right|\log {\left|E\right|}$ è data sia se ordino prima tutti gli archi per peso decrescente, sia se ogni volta cerco l'arco di peso minimo.

## Algoritmo di Prim

Partendo da un nodo, a ogni passo si prende il solo arco sicuro tra quelli che partono dal nodo corrente (in caso di due archi sicuri di egual peso, è arbitraria la scelta di uno di essi).
Man mano che si aggiunge un arco sicuro, nel vettore dei padri si memorizza come padre il nodo da cui l'arco sicuro parte.
La complessità è: $T\left(n\right)=O\left(\left|E\right|\log {\left|V\right|}\right)$
Il caso peggiore si verifica se il numero di archi $\left|E\right|$ è molto maggiore del numero di vertici $\left|V\right|$.