Algoritmi/Gli alberi ricoprenti minimi

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|$.