8/17/2019 Cursul12_ATP2016

1/22

+

Algoritmi și tehnici de

programar

e

Cursul 12

8/17/2019 Cursul12_ATP2016

2/22

+

Structuri arborescente

Parcurgeri

Algoritmul lui Kruskal

Algoritmul lui Prim

8/17/2019 Cursul12_ATP2016

3/22

+Structuri arborescente

Structurile cele mai simple şi care apar cel maifrecvent în aplicaţii sunt cele arborescente (arbori).Grafurile arbori constituie o subclasă a grafurilorconexe.

Definiţi e. Graful G este arbore dacă G este aciclic şiconex.

Definiţi e. Fie G =( V ,E ) graf arbore. Subgraful

H =( V 1 ,E 1 ) al lui G, este subarbore al lui G, dacă H este graf arbore.

8/17/2019 Cursul12_ATP2016

4/22

+Structuri arborescente

Fie G =( V ,E ) un graf. Următoarele afirmaţii sîntechivalente:G este graf arbore (aciclic şi conex);G este graf conex minimal : oricare ar fi e E , prin

eliminarea muchiei e din E , graful rezultat nu esteconex;G este graf aciclic maximal: prin adăugarea uneinoi muchii în graf rezultă cel puţin un ciclu.

8/17/2019 Cursul12_ATP2016

5/22

+Structuri arborescente

Cum verific ăm dacă un graf este arbore?

Verificare conexitate + verificare aciclicitate (alg.Marimont)

Verificare aciclicitate şi n = m + 1 Verificare conexitate şi n = m + 1

8/17/2019 Cursul12_ATP2016

6/22

+Structuri arborescente

Tem ă:Se citește un graf neorientat prin matricea deadiacenţă. Se cere să se verifice daca graful

reprezintă un arbore.

8/17/2019 Cursul12_ATP2016

7/22

+Structuri arborescente

Definiţi e. Se numeşte graf asimetric un digraf D =( V ,E ) cu proprietatea că pentru orice uv E , vu nu apartine E . Digraful D este simetric dacă pentruorice uv E şi vu E .

Definiţie . Fie D =( V ,E ) digraf netrivial. GrafulG =( V ,E’ ), unde E’ ={ uv / uv E sau vu E } senumeşte graf suport al digrafului D .

8/17/2019 Cursul12_ATP2016

8/22

+Structuri arborescente

Definiţie . Un arbore direcţionat este un graf orientat asimetric pentru care graful suport corespunzătoreste graf arbore.

Arborele direcţionat T =( V ,E ) este arbore curădăcinădacă există r V astfel încît, pentru oriceu V , u ≠ r , există r-u drum în T .

Vîrful r se numeşte rădăcina arborelui direcţionat T .(drumurile sînt unice, rădăcina este unică).

8/17/2019 Cursul12_ATP2016

9/22

+Structuri arborescente

Fie = ( , ) arbore direcţionat. Arborele =( , )este subarbore al lui dacă 1 ⊆ , 1 ⊆şi este arbore direcţionat.Un arbore orientat este un arbore direcţionat cu rădăcină .

Fie = ( , ), un arbore orientat cu rădăcină r . Unvîrf v este situat pe nivelul i al arborelui T , dacă

distanţa de la vîrf la rădăcină este egală cu i .Rădăcina arborelui este considerată de nivel 0.

8/17/2019 Cursul12_ATP2016

10/22

+Structuri arborescente

Definiție Daca intr-un arbore eliminam rădăcina,atunci obținem subarbori.

Definiție Intr-un arbore succesorul unui nod senumește fiu.

Definiție Daca un nod are mai mulți fii, atunci el se numește tata .

Definiție Daca un nod are mai mulți fii, aceștia senumesc frați intre ei.

8/17/2019 Cursul12_ATP2016

11/22

+Structuri arborescente

Definiție Se numește înălțimea arborelui nivelulmaxim al nodurilor unui arbore.

Definiție Se numește gradul unui nod numărul fiilornodului respectiv.

Definiție Se numește nod terminal(frunza), un nodde grad zero , iar un nod de grad diferit de zero senumește nod intern .

8/17/2019 Cursul12_ATP2016

12/22

+Reprezentare

Se pot folosi toate tipurile de reprezentare agrafurilor, plus metode specifice arborilor, maieficiente.

Reprezentarea Fiu-Frate N : numărul de noduri R : nodul rădăcină Fiu(i) : eticheta ataşată primului descendent al vîrfuluii

Frate(i) : eticheta ataşată vîrfului descendent al tatălui vîrfuluii

şicare urmează imediat luii Inf(i) : informaţia ataşată vîrfuluii Valoare lipsă: se foloseşte o valoare convenţională (0, - 1…)

8/17/2019 Cursul12_ATP2016

13/22

+Reprezentare

= 16 = 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 = 2 5 0 8 0 9 0 14 0 0 0 0 0 = 0 3 4 0 6 7 0 0 10 11 12 13

8/17/2019 Cursul12_ATP2016

14/22

+Parcurgeri

Variante adaptate ale parcurgerii grafurilor:

În lățime (BF)

Parcurgere pe niveluri

În adîncime (DF)Parcurgerea în A-preordineParcurgerea în A-postordine

8/17/2019 Cursul12_ATP2016

15/22

+Parcurgeri

Pe niveluri (reprezentare Fiu-Frate)

parcurgere_pe_niveluri( R, FIU[], FRATE[], n ){ Coadă C = NULL;

adaugă ( C, R );cît timp ( C ){ extrage( C, v );

Prelucrează( v );v = FIU[v];cît timp ( v ){ adaugă( C, v);

v = FRATE[v];

}}

}1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

8/17/2019 Cursul12_ATP2016

16/22

+Parcurgeri-Preordine

Este vizitat vârful curent şi sunt identificaţidescendenţii lui.Se aplică aceeaşi regulă de vizitare pentru arborii având carădăcini descendenţii vârfului curent .

void A_preordine (nod R){ if (R){

vizit (R); A_preordine(FIU[R]); A_preordine(FRATE[R]);

}}

1, 2, 5, 6, 9, 10, 11, 12, 13, 7, 3, 4, 8, 14, 15, 16

8/17/2019 Cursul12_ATP2016

17/22

+Parcurgeri-Postordine

Se identifică şi se viziteazădescendenţii vârfului curent , apoise viziteazăvârful curent . Se aplică aceeaşi regulă de vizitarepentru arborii având ca rădăcini descendenţii vârfului curent.

void A_postordine (nod R){ if (R){

A_postordine(FIU[R]); A_postordine(FRATE[R]);vizit (R);

}}5, 9, 10, 11, 12, 13, 6, 7, 2, 3, 14, 15, 16, 8, 4, 1

8/17/2019 Cursul12_ATP2016

18/22

+ Arbori par ţiali

Definiţie . Fie G un graf. Subgraful parţial H este un arbore parţial al lui G dacă H este graf arbore.

Definiţie . Fie G =( V ,E ,w ) un graf ponderat conex . DacăT =( V ,E 0 ) este un arbore parţial al grafului G’ =( V ,E ), pondereaarborelui T , notată W (T ), este definită prin

Definiţie . Arborele parţial T 0 T (G ) este arbore parţial minimpentru G dacă

= min∈ unde T (G ) este mulţimea arborilor parţiali corespunzătorigrafului G .

( ) = ∈

8/17/2019 Cursul12_ATP2016

19/22

8/17/2019 Cursul12_ATP2016

20/22

+ Algoritmul lui Kruskal

int radacina(int v,int *tata)

{ int u=v;while(tata[u]>=0) u=tata[u];return u;

}int kruskal(int a[][3],int nv, intnm,int b[][3], int *l){int tata[50],i,j, c=0;*l=0;for(i=0;i

8/17/2019 Cursul12_ATP2016

21/22

+ Algoritmul lui Prim

Problemădeterminarea arborelui parţial de cost minim = ( ,) al grafului =( , )

Algoritm:

E se iniţializează ca mulţime vidă Alege un vîrf inițial oarecare ∈ , = , = −Repetă de −1 ori

Alege muchia = ( , )cu cea mai mică ponderecu ∈ E ←E∪

← ∪ ← −

Temă:Implementați algoritmul Prim

8/17/2019 Cursul12_ATP2016

22/22

+Grafuri

Tem ăStudia ț i toate exemplele din capitolul Grafuri din culegere

Capitolul 3 în edi ț ia 2015

Capitolul 6 în edi ț ia 2012