FMI Algoritmica grafurilor, anul 1, Laborator 4

Arbori pariali de cost minim

Probleme maxim dou probleme la alegere

1. Implementai eficient algoritmul lui Prim pentru determinarea unui arbore parial

de cost minim (economic) al unui graf simplu, conex, ponderat cu n vrfuri i m

muchii (O(m log n)). Se vor da la intrare numrul de vrfuri ale grafului, numrul

de muchii i fiecare muchie a grafului cu costul su. (4p)

http://www.infoarena.ro/problema/apm

2. Implementai eficient algoritmul lui Kruskal pentru determinarea unui arbore

parial de cost minim (economic) al unui graf simplu, conex, ponderat cu n

vrfuri i m muchii (O(m log n)). Se vor da la intrare numrul de vrfuri ale

grafului, numrul de muchii i fiecare muchie a grafului cu costul su. (4p)

http://www.infoarena.ro/problema/apm

3. Second best minimum spanning tree Implementai un algoritm eficient pentru

determinarea primilor doi arbori parial cu cele mai mici costuri, pentru un graf

simplu, conex, ponderat cu n vrfuri i m muchii, n ipoteza c muchiile au

costuri distincte (O(n2)). Se vor da la intrare numrul de vrfuri ale grafului,

numrul de muchii i fiecare muchie a grafului cu costul su. Pentru determinarea

arborelui parial de cost minim (primul) se va folosi un algoritm de complexitate

O(m log n) (9p)

4. http://www.infoarena.ro/problema/retea2 (5p)

5. http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=960

(5p)

6. http://www.infoarena.ro/problema/online (9p implementarea optim a

algoritmului pentru arbori pariali de cost minim ales)

7. Orice alt problem care se reduce la determinarea de arbori pariali de cost

minim

Bibliografie

T.H. Cormen, C.E. Leiserson, R.L. Rivest Introduction to algorithms, MIT Press, Cambridge, 1990/2001

FMI Algoritmica grafurilor, anul 1, Laborator 4

Algoritmul lui Kruskal

Pe parcursul algoritmului lui Kruskal muchiile selectate formeaz o pdure. Iniial mulimea muchiilor selectate este vid, fiecare vrf al grafului constituind un

arbore.

La fiecare pas este selectat o muchie de cost minim cu extremitile n arbori diferii din pdurea deja construit (altfel spus, o muchie de cost minim care nu formeaz cicluri cu muchiile deja existente).

Pentru a simplifica alegerea unei muchii de cost minim muchiile sunt sortate iniial n ordinea cresctoare a costurilor i vor fi prelucrate de algoritm n aceast ordine.

Mai trebuie gsit o metod eficient de a testa dac o muchie unete doi arbori din pdurea deja construit sau are extremitile n acelai arbore (deci formeaz ciclu cu muchiile deja selectate). Este suficient s gsim o modalitate de a memora vrfurile arborilor. Pentru aceasta se folosesc structuri de date pentru mulimi disjuncte (mulimile vrfurilor arborilor sunt mulimi disjuncte). Fiecrei mulimi i se asociaz un reprezentatnt. Operaiile principale cu mulimi disjuncte sunt:

MakeSet(u) formeaz o mulime cu un singur element u

FindSet(u) returneaz reprezentantul mulimii care conine pe u

Unoin(u,v) reunete mulimea care conine elementul u cu cea care conine elementul v.

Cu aceste operaii algoritmul lui Kruskal este urmtorul:

A=

for (v V(G)) MakeSet(v) //iniial fiecare vrf este un arbore

Sort(E(G),w) //sorteaz muchiile grafului cresctor dup cost

for(uv E(G) n ordinea costurilor) if(FindSet(u)!=FindSet(v){

A=A{uv} Union(u,v)

if(|A|==n-1)

break

}

return A

Un mod simplu de a reprezenta mulimile disjuncte este folosirea unui vector de reprezentani r cu n elemente cu semnificaia r[u] = reprezentantul mulimii creia aparine u.

Astfel, MakeSet(u) se reduce la atribuirea r[u]=u, iar FindSet(u) la a returna r[u].

Operaia Unoin(u,v) presupune ns schimbarea peste tot n vectorul r a valorii r[u] cu valoarea r[v] (reprezentantul mulimii care l conine pe u devine reprezentantul mulimii care l conine pe v), deci are complexitatea O(n).

Pentru o implementare mai rapid a mulimilor disjuncte, reprezentm o mulime printr-un arbore avnd ca rdcin reprezentantul mulimii, pentru fiecare element al mulimii fiind memorat tatl acestuia n arbore.

FMI Algoritmica grafurilor, anul 1, Laborator 4

Operaia FindSet(u) presupune urmrirea legturii de tip tata din vrful u pn n rdcin. Nodurile de pe acest lan de la vrful u la rdcin constituie drumul de

cutare. Operaia Unoin(u,v) va avea ca efect faptul c rdcina unui arbore va avea ca tat rdcina celuilalt arbore. Pentru ca operaiile s fie ct mai eficiente trebuie ca nlimea arborilor reprezentnd mulimile disjuncte s fie ct mai mic. Pentru aceasta la reuniune rdcina arborelui cu nlime mai mic va arta (va avea ca tat) rdcina arborelui cu nlime mai mare reuniune ponderat. n plus, n timpul operaiei

FindSet(u) putem modifica legtura de tip tata a vrfurilor de pe drumul de cutare de la u la rdcin, astfel nct aceasta s arate direct ctre rdcin (astfel, la o viitoare cutare, reprezentantul acestor vrfuri va fi chiar tatl lor, nu va mai fi necesar o urcare n arbore) compresie de cale.

1

4

32

7

5FindSet(7)

8 9

1

4

32 75

8 96

6

1

4

32

5

6

Union(1,5)

1

4

32 5

6

Dac pentru fiecare vrf u reinem n h[u] o margine superioar a nlimii lui u (numrul de muchii ale celui mai lung lan de la u la o frunz descendent) i n p[u] tatl vrfului u, pseudocodul pentru cele trei operaii este urmtorul:

MakeSet(u)

p[u]=0

h[u]=0

FindSet(u)

if (p[u]==0)

return u

p[u]=FindSet(p[u]) //tatal lui u devine radacina

return p[u]

Union(u,v)

u=FindSet(u)

v=FindSet(v)

if (h[u]>h[v])

p[v]=u

else

p[u]=v

if(h[u]==h[v])

h[v]=h[v]+1

FMI Algoritmica grafurilor, anul 1, Laborator 4

n practic se poate considera c un ansamblu de q operaii cu mulimi disjuncte implementate astfel are complexitatea O(q).

Complexitatea algoritmului Kruskal

T(n, m) ncomplexitate(MakeSet)+complexitate(sort)+

+2mcomplexitate(FindSet) + (n-1)complexitate(Union)

Pentru reprezentarea mulimilor disjuncte folosind vectori de reprezentani obinem complexitatea O(n

2+m log n). Dac folosim ns arbori (cu reuniune ponderat i

compresie de cale) obinem O(m log n).

Algoritmul lui Prim

Pe parcursul algoritmului lui Prim muchiile selectate formeaz ntotdeauna un singur arbore.

Arborele pornete de la un vrf arbitrar r si crete pn acoper toate vrfurile din V. La fiecare pas se adaug arborelui o muchie de lungime minim care unete un vrf al arborelui A cu un vrf neselectat pn la acel pas.

Cheia implementrii eficiente a algoritmului lui Prim este s procedm astfel nct sa fie uor s selectm o nou muchie de cost minim ntre un vrf selectat i un vrf neselectat pentru a fi adugat la arbore. Pentru aceasta, asociem fiecrui vrf neselectat o cheie reprezentnd costul minim al unei muchii care l unete de un vrf deja selectat. La fiecare selectare a unui nou vrf pentru a fi adugat n arbore, se actualizeaz cheile vrfurilor adiacente cu el rmase neselectate.

n pseudocodul de mai jos graful conex G si rdcina r sunt date de intrare.

Pentru fiecare vrf v, cheie[v] este minimul costurilor muchiilor care unesc pe v cu vrfurile selectate (din arborele A). Vrful din arbore pentru care se realizeaz acest

minim se reine n p[v]. Astfel, la fiecare pas, muchia (v, p[v]) va fi muchia de cost

minim care unete pe v de un vrf selectat, iar lungimea acestei muchii este cheie[v] i reprezint distana minim de la v la arborele A.

Cnd un vrf u aflat la distana minim de A este adugat la arbore, p[u] va reprezenta printele lui n arbore.

Prin convenie cheie[v]= dac nu exist nici o muchie care s uneasc pe v de un vrf selectat.

n timpul execuiei algoritmului toate vrfurile care nu sunt n arbore se afl ntr-o structur Q (care poate fi de exemplu un ansamblu bazat pe cmpul cheie).

Funcia extrageMinim (Q) extrage din Q vrful cu cheie minim i l returneaz.

n timpul algoritmului mulimea A din algoritmul generic este pstrat implicit ca

A={(v, p[v]), vV-{r}-Q}

Algoritmul se termin cnd Q este vid. Arborele parial de cost minim A al lui G

este astfel A={(v, p[v]), vV-{r}}

FMI Algoritmica grafurilor, anul 1, Laborator 4

procedure APCM_PRIM(G, w, r) creare(Q, V[G])

pentru fiecare uQ executa

cheie[u] = cheie[r] = 0

p[r] = null

cat timp Q executa u = extrageMinim(Q)

pentru fiecare vAdj[u] executa

daca vQ si w(u, v)

FMI Algoritmica grafurilor, anul 1, Laborator 4

Exemplu

Kruskal :

20

15

811

102

3 5

9.

1

3

2

4

5 6

Muchiile vor fi prelucrate n ordinea (5, 6) cost 2 (2, 5) cost 3 (2, 6) cost 5 (3, 4) cost 8 (3, 6) cost 9 (1, 3) cost 10 (2, 4) cost 11 (1, 2) cost 15 (4, 6) cost 20

Algoritmul va selecta muchia (5, 6), apoi (2, 5), nu va selecta muchia (2, 6)

deoarece formeaz cicluri cu cele deja selectate (are extremitile n acelai arbore), va selecta apoi (3, 4), (3, 6), (1, 3) i se va opri deoarece muchiile selectate formeaz un arbore. Obinem urmtorul arbore de cost minim

8

10

2

3

9.

1

3

2

4

5 6

FMI Algoritmica grafurilor, anul 1, Laborator 4

Prim:

20

15

811

10

23 5

9.

1

3

2

4

5 6

Vrf de pornire 1 Marcm cu * vrful selectat la pasul curent

vrf 1 2 3 4 5 6

Cheie/p 0/null * /null /null /null /null /null

- 15/1 10/1 * /null /null /null

- 15/1 - 8/3 * /null 9/3

- 11/4 - - /null 9/3 *

- 5/6 - - 2/6 * -

3/5 *

Dup ce au fost selectate toate vrfurile, muchiile se pot reconstitui innd cont de printele p la momentul selectrii. Astfel, muchiile vor fi

(5, 2) - deoarece p[2] = 5

(1, 3) - deoarece p[3] = 1

(3, 4) - deoarece p[4] = 3

(6, 5) - deoarece p[5] = 6

(3, 6) - deoarece p[6] = 3

Obinem arborele urmtor.

8

10

2

3

9.

1

3

2

4

5 6