Minimo albero ricoprente

Il compito consiste nell'implementazione di tre algoritmi per il calcolo della copertura minima (MST) di un grafo non diretto connesso.

Sia dato un grafo non diretto (i.e. non orientato) G = <V,A> con archi pesati: Peso:A -> integer; inoltre G sia connesso (dati comunque due vertici esiste un cammino che li congiunge). Introduciamo i seguenti concetti, dove T è un sottoinsieme di A:

  1. T è una copertura se ogni vertice in V possiede in T un arco in esso incidente;
  2. T è un albero ricoprente se è una copertura ed è un grafo connesso aciclico;
  3. T è un minimo albero ricoprente (inglese: Minimum Spanning Tree) se la somma dei pesi degli archi in T è minima tra quelle di tutte le possibili coperture.
I seguenti due algoritmi calcolano un minimo albero ricoprente per un grafo connesso pesato non diretto G. In particolare il secondo algoritmo consiste in una visita del grafo a partire da un assegnato vertice r, che risultarà la radice dell'albero ricoprente calcolato.

Algoritmo di Kruskal

Si implementi in C il seguente algoritmo: 
MST-Kruskal (Graph G)
// pre:  G e' connesso
// post: ritorna un MST T di G

var C: famiglia di insiemi disgiunti di vertici;
    E: lista di archi pesati [(u,v),p];
    T: insieme di archi formanti un albero;

begin
    T:= albero vuoto;
    C:= {{v} | v in Vertici(G)};
    E:= lista degli archi [(u,v),peso(u,v)] in Archi(G) 
        ordinata in senso non decrescente rispetto al peso;    
    while E <> lista vuota do begin
          [(u,v),p]:= Testa(E);
          A:= l'unico ins. in C t.c. u in A;
          B:= l'unico ins. in C t.c. v in B;
          if A <> B then begin
              C:= C - {A,B} + {A + B};
              T:= T + {(u,v)}
          end;
          E:= Coda(E);
    end;
    return T
end;
Si rammenti che una foresta è un insieme di alberi; equivalentemente una foresta è un grafo le cui parti connesse sono acicliche. Il seguente asserto, allora, risulta un'invariante del while di MST-Kruskal: 
T è un sottoinsieme di Archi(G) formante una foresta;
C è una partizione di Vertici(V) ciascun elemento
    della quale o è un singoletto oppure l'insieme
    dei vertici di un albero in T.
Se G è connesso, poiché gli archi sono considerati esaustivamente, al termine dell'iterazione risulterà C = {Vertici(G)}; d'altra parte, visto che un arco è aggiunto in T solo se connette due sottografi aciclici disgiunti di G, T risulta un albero di copertura del grafo. Che sia minimo è conseguenza dell'ordine in cui gli archi vengono scelti.

Si realizzi l'algoritmo di Kruskal utilizzando strutture dati appropriate tra quelle viste nel corso: in particolare per l'implementazione della partizione C si usi un opportuno adattamento della struttura dati Insiemi disgiunti, mentre per l'albero T si impieghi una coppia <grafo,radice>, come in GrafiMain.c

Algoritmo di Prim

Si implementi in C il seguente algoritmo: 
MST-Prim (Graph G, Vertex r)
// pre:  G e' connesso, r in Vertici(G)}
// post: ritorna un MST T di G con radice in r

var Q: coda di [(u,v),pr] dove (u,v) è un arco e pr una priorità
    R: insieme di vertici;
    T: insieme di archi formanti un albero;

begin
    T:= albero vuoto;
    _:= vertice fittizio non in Vertici(V);
    Q:= {[(_,v),pr] | v in Vertici(G)-{r}, pr = +infinito} + {[(_,r),0]};
    while Q <> coda vuota do begin
        v:= un el. di Vertici(G) t.c. [(u,v),pr] in Q
            per qualche u in Vertici(G) + {_},
            e, per ogni [(u',v'),pr'] in Q, pr <= pr';
        Q:= Q - {[(u,v),pr]};
        T:= T + {(u,v)};
        foreach w in Adiacenti(v) do
             if esiste [(z,w),pr] in Q t.c. pr > Peso(v,w) 
                             // se [(z,w),pr] esiste in Q allora e' unico
                then Q:= Q - {[(z,w),pr]} + {[(v,w),Peso(v,w)]}
    end;
    return T
end;
L'invariante del ciclo while definisce il concetto di priorità usato dall'algoritmo, ed è il seguente: 
per ogni [(u,v),pr] in Q, o u = _ e pr = +infinito, oppure
(u,v) è un arco di G t.c. u sia un vertice appartenente alla
copertura T e v un vertice che non appartiene a tale copertura.
In questo ultimo caso pr = Peso(u,v).
Si osservi che in T il solo arco incidente nel nodo fittizio _ sarà (_,r), vale a dire la radice di T (tale arco, così come il nodo _ servono nella pseudocodifica, ma è opportuno evitarli nell'implementazione).

L'implementazione deve utilizzare una coda di priorità, adattata da Heap.cpp. Si osservi come la ridefinizione della priorità mediante il peso di un arco comporti una ristrutturazione dello heap, per cui si deve definire una funzione 

void DecrPrior (Vertex v, Priority p, PriorityQueue q)
// assegna a v in q una nuova priorità, minore di quella
// che v aveva in precedenza, e riorganizza la coda di
// conseguenza.

Algoritmo MST con code unificabili

Si consideri la seguente variante degli algoritmi MST: 
MST-MergeableHeap (Graph G)
var  T: insieme di archi formanti un albero;
     PV: partizione dei vertici di G;
     PA: vettore di insiemi di archi di G indicizzato su PV;

begin
     T := albero vuoto;
     PV := {{v_i}| v_i in Vertici(G)};
     foreach V' in PV
         PA[V'] := {(v,u)| v in V', (u,v) in Archi(G)};
     while PV ha più di un elemento do begin
         scegli V' in PV;
         sia (v,u) in PA[V'] con peso minimo;
		 sia U in PV t.c. u in U;
         PA[V'] := PA[V'] - {(v,u)};
         if V' <> U then begin
            T := T + {(v,u)}; 
                 // + rappresenta l'unione insiemistica
            PV := PV - {V',U} + {V' + U};
            PA[V'+ U] := PA[V'] + PA[U];
         end;
     end;
     return T
end;
Si realizzi questo algoritmo utilizzando le opportune strutture dati, vale a dire:
  1. PV con una tecnica simile a quella impiegata per MST-Kruskal, salvo che gli elementi della partizione saranno coppie <V,puntatore a PA[V]>
  2. ogni elemento PA[V] di PA deve essere implementato con una coda unificabile realizzata con heap binomiale; non occorre realizzare una struttura dati per PA, potendosi sfruttare PV.