Non tutti gli algoritmi che adottano una strategia greedy possono essere inquadrati nella teoria generale presentata nelle sezioni precedenti. Uno di questi `e l’algoritmo di Prim per il calcolo del minimo albero di copertura di un grafo. Questa procedura si differenzia da quella di Kruskal, descritta nella sezione prece-dente, poich´e l’albero di copertura viene costruito a partire da un nodo sorgente aggiungendo di volta in
volta il lato di peso minimo che permette di estendere l’insieme dei nodi raggiunti dalla soluzione. In questo modo la soluzione parziale mantenuta dall’algoritmo non `e una foresta come nel caso dell’algo-ritmo di Kruskal, ma `e formata da un albero che ha per radice la sorgente e che inizialmente coincide con quest’ultima. A tale albero vengono via via aggiunti nuovi nodi, scegliendoli tra quelli che si trovano a distanza minima da uno dei suoi vertici; il procedimento prosegue fino a quando tutti i nodi sono stati collegati alla soluzione.
Un’istanza del problema `e quindi data da un grafo G = hV, Ei non orientato, connesso, dotato di una funzione peso w : E → Q e da un nodo sorgente s ∈ V . Come al solito rappresentiamo il grafo associando a ogni vertice v ∈ V la lista L(v) dei nodi adiacenti. La soluzione viene calcolata fornendo l’insieme T dei lati dell’albero di copertura ottenuto.
Sostanzialmente l’algoritmo mantiene una partizione dei nodi del grafo in due insiemi che chiame-remo S e R. L’insieme S `e formato dai vertici gi`a raggiunti dalla soluzione, mentre R `e costituito da tutti gli altri. Per ogni nodo v in R la procedura conserva il peso del lato di costo minimo che congiunge v con un nodo in S e sceglie tra tutti questi lati quello di peso minore, aggiungendolo alla soluzione ed estendendo cos`ı l’insieme dei vertici raggiunti. Per descrivere questo procedimento definiamo, per ogni nodo v ∈ R, la distanza di v da S mediante la seguente espressione:
dist(v) = (
min{w({v, z}) | z ∈ S} se {z ∈ S | {v, z} ∈ E} 6= ∅
∞ altrimenti
Inoltre denotiamo con vicino(v) il nodo z ∈ S tale che w({v, z}) = dist(v), con la convenzione di lasciare vicino(v) indefinito se dist(v) = ∞. I valori dist(v) e vicino(v) possono essere rappresentati efficientemente mediante due vettori indiciati dagli elementi di V . Infine, denoteremo con D l’insieme dei nodi in R che hanno una distanza finita da S:
D = {v ∈ R | dist(v) 6= ∞}
Tale insieme viene costantemente aggiornato dall’algoritmo e da esso (insieme ai valori dist e vicino) la procedura estrae di volta in volta il nodo che si trova a distanza minima dalla soluzione.
L’algoritmo pu`o ora essere descritto dalla seguente procedura che utilizza effettivamente solo l’in-sieme D, i valori dist e vicino e l’inl’in-sieme T che mantiene la soluzione costruita.
ProcedurePrim(V, E, w, s) begin T := ∅ for v ∈ Rdo ( dist(v) := ∞ vicino(v) := ⊥ D := {s} dist(s) := 0 whileD 6= ∅do begin
(1) determina l’elemento v ∈ D con dist(v) minima
(2) cancella v da D
aggiungi il lato {v, vicino(v)} a T
foru ∈ L(v) do if dist(u) = ∞ (3) then aggiungi u a D dist(u) := w({v, u}) vicino(u) := v
else ifu ∈ D ∧ w({v, u}) < dist(u)
(4) then ( dist(u) := w(v, u) vicino(u) := v end outputT − {{s, ⊥}} end
Per illustrare il funzionamento dell’algoritmo, consideriamo il grafo rappresentato nella seguente figura: d 2 5 e @ @ @ @ @ 1 3 4 f 8 @ @ @ @ @ 2 a 7 b 5 c
Accanto a ogni lato `e riportato il peso corrispondente e si suppone che il nodo sorgente sia d. Nella tabella successiva mostriamo il funzionamento dell’algoritmo su tale istanza, riportando i valori degli insiemi R, D, T , del vettore dist e del nodo v dopo l’esecuzione di ogni ciclowhile.
v R dist D T − {{s, ⊥}}
d {a, b, c, e, f } (5, ∞, ∞, −, 2, ∞) {a, e} ∅ e {a, b, c, f } (1, 3, ∞, −, −, 4) {a, b, f } {e, d} a {b, c, f } (−, 3, ∞, −, −, 4) {b, f } {e, d}, {e, a} b {c, f } (−, −, 5, −, −, 2) {c, f } {e, d}, {e, a}, {e, b} f {c} (−, −, 5, −, −, −) {c} {e, d}, {e, a}, {e, b}, {b, f }
Scegliamo ora le strutture dati pi`u idonee per implementare l’algoritmo. Innazitutto i valori dist e vicino possono essere rappresentati mediante vettori che hanno per indice i nodi v ∈ V .
La soluzione T pu`o essere semplicemente rappresentata da una lista poich´e l’unica operazione ese-guita su tale insieme consiste nell’aggiungere un nuovo elemento (operazione che possiamo cos`ı eseguire in tempo costante).
Sull’insieme D dobbiamo eseguire 4 operazioni: determinare il nodo v a distanza minima (linea (1) nella procedura), cancellarlo (linea (2)), introdurre un nuovo elemento (linea (3)) e aggiornare la distanza di un nodo gi`a presente in D (linea (4)). Descriviamo due diverse strutture per implementare D. Nel primo caso consideriamo D come una coda di priorit`a e utilizziamo uno heap rovesciato nel quale il valore di ogni nodo v `e dato dalla sua distanza dist(v). In questo modo il nodo a distanza minima si trova nella radice dello heap e l’operazione di cancellazione del minimo e di inserimento di un nuovo elemento possono essere eseguite in tempo logaritmico. Osserva che l’aggiornamento della distanza del nodo u, compiuto nella istruzione (4) della procedura, deve essere accompagnato da una ricollocazione di u all’interno dello heap; poich´e la sua distanza diminuisce questo corrisponde a spostare u verso la radice. Chiaramente, anche quest’ultima operazione richiede un tempo logaritmico rispetto al numero di elementi contenuti nello heap. Utilizzando tali strutture e le relative procedure, l’algoritmo di Prim, eseguito su un grafo di n nodi e m lati, richiede un tempo di calcolo O(m log n) (assumendo il criterio di costo uniforme).
Diversamente, possiamo implementare l’insieme D mediante un vettore ˆD di n elementi che ha per indici i nodi del grafo di ingresso G = (V, E). Per ogni v ∈ V , poniamo
ˆ D[v] = ∞ se v ∈ R − D dist(v) se v ∈ D 0 se v ∈ S
In questo modo il calcolo del nodo a distanza minima in D (linea (1)) richiede un tempo Θ(n), poich´e occorre scorrere l’intero vettore per determinare il minimo; tuttavia le altre operazioni richiedono un tempo costante. `E facile verificare che, usando questa struttura, l’algoritmo richiede un tempo dell’ordine di Θ(n2). Di conseguenza, se il numero dei lati m `e dell’ordine di grandezza di n2 (cio`e il grafo di ingresso contiene “molti” lati) allora quest’ultima implementazione `e preferibile alla precedente. Se invece m << n (cio`e il grafo di ingresso contiene “pochi” lati) l’uso di uno heap per implementare l’insieme D risulta asintoticamente pi`u efficiente.
Concludiamo studiando la correttezza dell’algoritmo appena descritto. Questa `e basata sulla seguente propriet`a .
Proposizione 12.4 Sia G = hV, Ei un grafo non orientato, connesso, dotato di una funzione peso
w : E → Q. Sia inoltre T un albero di copertura minimo per G, sia U un sottoalbero di T e sia S
l’insieme dei nodi in U . Consideriamo un lato di costo minimo {a, b} che “esce” da S, cio`e tale che
a ∈ S e b 6∈ S. Allora esiste un albero di copertura minimo per G che contiene U come sottoalbero e
che contiene anche il lato {a, b}.
Dimostrazione. Se il lato {a, b} appartiene a T allora T `e l’albero di copertura cercato. Altrimenti deve
esistere in T un cammino semplice che congiunge a e b; tale cammino si svolge inizialmente tra nodi dell’insieme S, quindi “esce” da S raggiungendo b. Deve allora esistere in tale cammino un lato {a0, b0} tale che a0 ∈ S e b0 6∈ S (eventualmente si pu`o verificare a = a0 oppure b = b0, ma non entrambi). Allora, sostituendo in T il lato {a0, b0} con il lato {a, b} non formiamo cicli e otteniamo cos`ı un nuovo
albero di copertura T0. Chiaramente T0contiene U come sottoalbero e inoltre il peso dei suoi lati `e dato da:
w(T0) = w(T ) − w({a0, b0}) + w({a, b})
Poich´e {a, b} `e di peso minimo tra tutti i lati che escono da S, abbiamo w({a, b}) ≤ w({a0, b0}) e quindi dall’equazione precedente otteniamo w(T0) ≤ w(T ). Di conseguenza, essendo T un albero di copertura minimo, anche T0risulta un albero di copertura minimo.
Nota che la proposizione precedente `e valida anche quando l’insieme S `e ridotto ad un solo nodo: il nodo sorgente. Cos`ı l’applicazione della propriet`a appena provata consente di dimostrare per induzione che la soluzione fornita dall’algoritmo rappresenta un albero di copertura minimo del grafo di ingresso.
Esercizio
1) Applicando l’osservazione precedente, provare la correttezza dell’algoritmo di Prim.