Atp Id - Grafuri.pdf
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Atp Id - Grafuri.pdf as PDF for free.
More details
- Words: 14,384
- Pages: 60
Algoritmi și tehnici de programare
1
Algoritmi si tehnici de programare (partea a II-a)
Material suport elaborat de Prof.dr. Ion Gh. Roşca Prof.dr. Bogdan Ghilic-Micu Conf.dr. Cătălina Cocianu Conf.dr. Marian Stoica Lect.dr. Cristian Uscatu Asist. Marinela Mircea
Editura ASE, Bucureşti 2007
2
Metode de programare
1. Introducere_______________________________________________3 2. Grafuri 3 2.1. Definiţii şi reprezentări ale grafurilor 2.1.1 Moduri de reprezentare a grafurilor 2.1.2. Reprezentarea matriceală 2.1.3. Reprezentarea tabelară 2.1.4. Reprezentarea prin intermediul listelor 2.2. Modalităţi de parcurgere a grafurilor 1.2.1. Metoda de parcurgere BF (Breadth First) 1.2.2. Metoda de parcurgere DF (Depth First) 1.2.3. Parcurgerea în adîncime în varianta generalizată – DFG 2.3. Drumuri în grafuri. Conexitate 2.3.1 Drumuri; definiţii 2.3.2. Matricea existenţei drumurilor; algoritmul Roy-Warshall 2.3.3. Componente conexe ale unui graf 2.3.4. Drumuri de cost minim 2.4. Circuite şi cicluri în grafuri şi în digrafuri
3
3. Structuri arborescente
37
3.1. Grafuri de tip arbore 3.1.1. Definiţii şi caracterizări ale grafurilor arbori 3.1.2. Reprezentări şi parcurgeri ale arborilor orientaţi 3.1.3. Arbori parţiali. Algoritmul Kruskal 3.2. Arbori binari 3.2.1. Reprezentarea arborilor binari. Modalităţi de parcurgere 3.2.2. Arbori de sortare 3.2.3. Arbori de structură
37
Bibliografie
_62
7
21
31
49
2
Algoritmi și tehnici de programare
3
1. Introducere
Grafurile sînt structuri de date cu aplicaţii în multe domenii ale informaticii, algoritmii pentru reprezentarea şi prelucrarea grafurilor fiind consideraţi fundamentali în acest domeniu. În subcapitolul 2.1 sînt prezentate principalele noţiuni ale domeniului, precum şi modalităţile uzuale de reprezentare a structurii de graf. În continuare sînt descrise tehnicile de parcurgere a grafurilor în lăţime şi în adîncime. Traversarea în adîncime a grafurilor determină obţinerea unei clasificări a muchiilor, în funcţie de care pot fi derivate diferite proprietăţi ale grafurilor. Verificarea conexităţii şi calculul drumurilor în grafuri sînt tratate în subcapitolul 2.3. În finalul capitolului este studiată problema determinării circuitelor şi ciclurilor în grafuri şi digrafuri.
2. Grafuri 2.1. Definiţii şi reprezentări ale grafurilor Definiţia 2.1.1. Se numeşte graf sau graf neorientat o structură G=(V,E), unde V este o mulţime nevidă iar E este o submulţime posibil vidă a mulţimii perechilor neordonate cu componente distincte din V. Elementele mulţimii V se numesc vîrfuri, iar obiectele mulţimii E se numesc muchii. Dacă e E, e (u,v) not. uv , vîrfurile u şi v se numesc extremităţi ale lui e, muchia e fiind determinată de vîrfurile u şi v. Dacă e=uv E se spune că vîrfurile u, v sînt incidente cu muchia e. Definiţia 2.1.2. Fie G=(V,E) graf. Vîrfurile u, v sînt adiacente în G dacă uv E. Definiţia 2.1.3. Graful G=(V,E) este graf finit, dacă V este o mulţime finită. În cadrul acestui capitol vor fi considerate în exclusivitate grafurile finite, chiar dacă acest lucru nu va fi precizat în mod explicit. Definiţia 2.1.4. Fie Gi =(V i,Ei), i=1,2 grafuri. G2 este un subgraf al grafului G1 dacă V2 V1 şi E2 E1 . G2 este este un graf parţial al lui G1 dacă V2=V1 şi G2 este subgraf al lui G1. Definiţia 2.1.5. Un digraf este o structură D=(V,E), unde V este o mulţime nevidă de vîrfuri, iar E este o mulţime posibil vidă de perechi ordonate cu componente elemente distincte din V. Elementele mulţimii E sînt numite arce sau muchii ordonate. Un graf direcţionat este o structură D=(V,E), unde V este o mulţime nevidă de vîrfuri, iar E este o mulţime posibil vidă de perechi ordonate cu componente elemente din V, nu neapărat distincte. Evident, orice digraf este un graf direcţionat. Terminologia utilizată relativ la digrafuri este similară celei corespunzătoare grafurilor. În continuare vom referi prin muchie şi elementele mulţimii E a unui graf direcţionat, în situaţia în care este tratat cazul unui graf oarecare (neorientat sau direcţionat). Definiţia 2.1.6. Se numeşte graf ponderat o structură (V,E,W), unde G=(V,E) este graf şi W este o funcţie definită prin W : E 0 , . Funcţia W este numită pondere şi ea asociază
4
Metode de programare
fiecărei muchii a grafului un cost/cîştig al parcurgerii ei. Definiţia 2.1.7. Fie G=(V,E) un graf, u,vV. Secvenţa de vîrfuri :u0,u1,..,un este un u-v drum dacă u0=u, un=v, uiui+1E pentru toţi i, 0 i n . Definiţia 2.1.8. Fie G=(V,E) un graf. Elementul vV se numeşte vîrf izolat dacă, pentru orice e E, u nu este incident cu e.
2.1.1 Moduri de reprezentare a grafurilor Cea mai simplă reprezentare a unui graf este cea intuitivă, grafică; fiecare vîrf este figurat printr-un punct, respectiv muchiile sînt reprezentate prin segmentele de dreaptă, orientate (în cazul digrafurilor) sau nu şi etichetate (în cazul grafurilor ponderate) sau nu, avînd ca extremităţi punctele corespunzătoare vîrfurilor care o determină Exemple 2.1.1. Fie G=(V,E) graf, cu V={1,2,3,4,5,6}, E={(1,2),(1,3),(2,5),(3,5),(5,6)}. O posibilă reprezentare grafică este,
1 2 4
6
5
3
2.1.2. Fie D=(V,E) digraf, V={1,…,5}, E={(1,2), (1,3), (1,5), (2,5), (3,5), (4,1), (5,4)}. Digraful poate fi reprezentat grafic astfel,
1
2
4
3 5 2.1.3. Fie D=(V,E) graf direcţionat, V={1,2,3,4,5}, E={(1,2), (1,3), (1,5) (2,5), (3,5), (4,4)}. Reprezentarea grafică este,
4
Algoritmi și tehnici de programare
5
1 4
2 3
5
2.1.4. Fie G=(V,E,W) graf ponderat, V={1,2,3,4}, E={(1,2), (1,3), (1,4), (2,3), (2,4)}, W((1,2))=5, W((1,3))=1, W((1,4))=7, W((2,3))=4, W((2,4))=2. O posibilă reprezentare grafică este:
1
5
1
2
4
3
2 7
4 În scopul reprezentării grafurilor în memoria calculatorului sînt utilizate în general următoarele structuri de date. 2.1.2. Reprezentarea matriceală Grafurile, digrafurile şi grafurile direcţionate pot fi reprezentate prin matricea de adiacenţă. Dacă G=(V,E ) este graf, digraf sau graf direcţionat cu V n , atunci matricea de adiacenţă A Mnxn({0,1}) are componentele,
1, dacă vi ,v j E aij , 0 , altfel
unde vi, vj reprezintă cel de-al i-lea, respectiv cel de-al j-lea nod din V. În cazul unui graf neorientat, matricea de adiacenţă este simetrică. Exemplu 2.1.5. Graful din exemplul 2.1.1, digraful din exemplul 2.1.2 şi graful direcţionat din exemplul 2.1.3 sînt reprezentate prin matricele de adiacenţă, 0 1 1 A 0 0 0
1 0 0 0 1 0
1 0 0 0 1 0
0 0 0 0 0 0
0 1 1 0 0 1
0 0 0 0 0 (2.1.1), A 0 0 1 1 0 0
1 0 0 0 0
1 0 0 0 0
0 0 0 0 1
1 0 1 0 1 (2.1.2), A 0 0 0 0 0
1 0 0 0 0
1 0 0 0 0
0 0 0 1 0
1 1 1 (2.1.3) 0 0
În cazul grafurilor ponderate, reprezentarea poate fi realizată prin matricea ponderilor. Dacă G=(V,E,W) este graf ponderat, V n , W Mnxn((0, )) are componentele,
6
Metode de programare
W ( vi ,v j ), dacă vi ,v j E wi , j , altfel
unde vi, vj reprezintă cel de-al i-lea, respectiv cel de-al j-lea nod din V, 0 , dacă ponderea are semnificaţia de cîştig, respectiv în cazul în care se doreşte reprezentarea costurilor ca ponderi ale grafului. Exemplu 2.1.6. Presupunînd că ponderile reprezintă costuri, matricea de reprezentare a grafului
5 din exemplul 2.1.4. este W 1 7
5 1 7 4 2 . 4 2
2.1.3. Reprezentarea tabelară Reţinînd muchiile prin intermediul extremităţilor şi eventual valoarea ponderii ei, se obţine reprezentarea tabelară, mai economică din punctul de vedere al spaţiului de memorie necesar. Dacă graful conţine vîrfuri izolate atunci este necesară păstrarea acestora într-un vector suplimentar VS. Mulţimea muchiilor este reţinută într-o matrice A cu E linii şi c coloane, unde c=2 dacă graful nu este ponderat, altfel c=3. În primele două coloane se scriu perechile de vîrfuri ce determină muchiile, în cazul grafurilor ponderate cea de-a treia coloană conţine valoarea ponderii muchiei respective. Exemple 2.1.7. Graful din exemplul 2.1.1 poate fi reprezentat astfel, VS=(4),
1 1 A 2 3 5
2 3 5 5 6
1 1 1 2.1.8. Digraful din exemplul 2.1.2 este reprezentat prin A 2 3 4 5
2 3 5 5 . 5 1 4
6
Algoritmi și tehnici de programare
7
1 1 1 2.1.9. Graful direcţionat din 2.1.3. este reprezentat prin A 2 3 4
2 3 5 . 5 5 4
2.1.10. Graful ponderat din exemplul 2.1.4. nu are vîrfuri izolate, deci este reprezentat 1 1 prin intermediul matricei A 2 1 2
2 3 3 4 4
5 1 4 . 7 2
2.1.4. Reprezentarea prin intermediul listelor Această reprezentare permite utilizarea economică a spaţiului de memorare şi, în anumite cazuri, implementări mai eficiente pentru anumite clase de algoritmi. Vîrfurile grafului sînt memorate într-o listă, fiecare nod al listei N conţinînd o referinţă spre lista vecinilor vîrfului memorat ca informaţie în N. Dacă graful nu este ponderat, el poate fi reprezentat prin structura listă de liste, şi anume: nodurile grafului se trec într-o listă L_nod, fiecare celulă avînd structura, informaţie legătură vecini legătură nod următor unde, cîmpul informaţie conţine identificatorul nodului; legătură vecini reprezintă referinţa spre începutul listei vecinilor; legătură nod următor conţine adresa următoarei celule din lista L_nod. Un graf ponderat poate fi reprezentat în mod similar, cu diferenţa că, fiecare celulă din lista vecinilor conţine şi ponderea muchiei respective (muchia care are ca extremităţi vîrful referit prin identificatorul de nod din lista vecinilor şi respectiv vîrful indicat de informaţia acelei celule din L_nod ce conţine adresa primului element al listei vecinilor).
2.2. Modalităţi de parcurgere a grafurilor Modalitatea de vizitare a tuturor vîrfurilor grafului în care fiecare vîrf al grafului este vizitat o singură dată se numeşte parcurgere sau traversare. În acest paragraf sînt prezentate metodele de parcurgere BF (în lăţime), DF (în adîncime) şi metoda DF generalizată, notată DFG. Primele două metode de parcurgere sînt aplicate grafurilor neorientate respectiv grafurilor direcţionate şi presupun selectarea unui vîrf iniţial v0 şi identificarea acelor vîrfuri ale grafului v cu proprietatea că există cel puţin un drum de la vîrful iniţial către v. Grafurile cu proprietatea că oricare două vîrfuri sînt conectate printr-un drum se numesc grafuri conexe şi sînt prezentate în § 2.3. Dacă graful este conex, atunci prin aplicarea metodelor de parcurgere vor fi identificate toate vîrfurile grafului. Cele două modalităţi de parcurgere sînt prezentate în continuare în cazul grafurilor neorientate, extinderea la digrafuri şi grafuri direcţionate fiind imediată. Studiul proprietăţii metodei BF de a calcula distanţele minim între
8
Metode de programare
orice vîrf al grafului conectat de vîrful iniţial şi vîrful iniţial este prezentat în cazul grafurilor oarecare. Parcurgerea DFG presupune vizitarea tuturor vîrfurilor unui graf sau graf direcţionat prin aplicarea metodei DF tuturor vîrfurilor care, după ultima traversare DF, nu au fost încă vizitate.
2.2.1. Metoda de parcurgere BF (Breadth First) Traversarea BF presupune parcurgerea în lăţime a grafului, în sensul că, vîrfurile grafului sînt prelucrate în ordinea crescătoare a distanţelor la vîrful iniţial (teorema 2.2.1). Distanţa de la u la v, notată u ,v , este numărul de muchii ale unui cel mai scurt u-v drum. La momentul iniţial vîrf curent este v0. Deoarece vîrful curent la fiecare moment trebuie să fie unul dintre vîrfurile aflate la distanţă minimă de v0 se poate proceda în modul următor: iniţial lui v0 i se asociază valoarea 0, d v0 0 şi fiecărui vîrf v v0 i se asociază
valoarea , d v . Dacă valoarea asociată vîrfului curent este m, atunci fiecăruia dintre vecinii acestuia de valoare li se asociază valoarea m+1. Se observă că, dacă după ce toate vîrfurile de valoare m au fost considerate şi nici unui vîrf nu i-a fost recalculată valoarea, atunci toate vîrfurile conectate cu v0 au fost vizitate, deci calculul se încheie. Exemple 2.2.1. Fie graful,
1 2
3 6 4 7
5
şi v0=1.Valorile calculate prin aplicarea metodei prezentate sînt, vîrf
1
2
3
4
5
6
7
0
0
1
0
1
1
1
1
2
0
1
1
1
2
2
1
0
1
1
1
2
2
1
d
8
Algoritmi și tehnici de programare
9
2.2.2. Fie graful,
1
8 3
2
6
4 5
9
10 11
7
şi v0=1. Se observă că vîrfurile 8, 9, 10 şi 11 nu sînt conectate cu vîrful iniţial. Valorile rezultate prin aplicarea metodei sînt:
1
2
3
4
5
6
7
8
9
10
11
0
0
1
0
1
1
1
1
2
0
1
1
2
1
2
1
0
1
1
2
1
2
1
vîrf d
Se observă că valorile lui d calculate în final reprezintă numărul de muchii corespunzător unui cel mai scurt drum care conectează vîrful iniţial cu vîrful respectiv, pentru vîrfurile neconectate cu v0 valoarea d[v0] rezultată la terminarea calculului este . Fie G=(V,E) un graf, V n . O alternativă de implementare a metodei BF este construită prin utilizarea următoarelor structuri de date, A matricea de adiacenţă a grafului; o structură de tip coadă, C, în care sînt introduse vîrfurile ce urmează a fi vizitate şi procesate (în sensul cercetării vecinilor lor); un vector c cu n componente, unde, dacă i 1a, fost adăugat în coadă ci altfel 0, Componentele vectorului c sînt iniţializate cu valoarea 0.
10
Metode de programare
Parcurgerea BF poate fi descrisă astfel, coada C este iniţializată cu vîrful v0; cît timp C Ø, este extras şi vizitat un vîrf i din coadă, apoi sînt introduşi în coadă vecinii lui i care nu au fost deja introduşi (acele vîrfuri k cu proprietatea că c[k]=0 şi a[i][k]=1). Vîrfurile i ce au fost introduse în coadă sînt marcate prin c[i]=1. Exemplu 2.2.3. Pentru graful din exemplul 2.2.1., aplicarea metodei de traversare BF determină următoarea evoluţie, c t t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8
1
2
3
4
5
6
7
1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1
0 1 1 1 1 1 1 1
1 2 3 4 7 5 6
3 4 7 5 6
4 7 5 6
7 5 6
C t t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8
Observaţie Deoarece graful din exemplul 2.2.1. este conex, traversarea BF realizează vizitarea tuturor vîrfurilor grafului. Aplicarea metodei BF grafului din exemplul 2.2.2. nu determină vizitarea vîrfurilor 8,9, 10 şi 11, deoarece acestea sînt vîrfuri neconectate cu vîrful iniţial . Cu alte cuvinte, metoda BF aplicată unui graf determină vizitarea tuturor vîrfurilor care sînt conectate cu vîrful iniţial selectat. Sursa C pentru implementarea metodei BF este, #include <stdio.h> #include #include typedef struct nn { int inf; struct nn *leg; } nod,* pnod; int insereaza_coada(pnod *head,pnod *tail,int info) { pnod nou; if(nou=(pnod)malloc(sizeof(nod))){
10
Algoritmi și tehnici de programare nou->inf=info; nou->leg=NULL; if(*head==NULL) *head=nou; else (*tail)->leg=nou; *tail=nou; return 1; } else return 0; } int extrage_coada(pnod *head,pnod *tail, int *info) { if(*head){ pnod aux=*head; *info=(*head)->inf; (*head)=(*head)->leg; free(aux); if(*head==NULL)*head=*tail=NULL; return 1; } else return 0;} void breadth_first(int v0,int a[10][10],int n) { pnod head=NULL; pnod tail=NULL; int c[10]; for(int i=0;i
11
12
Metode de programare
În continuare sînt prezentate o serie de rezultate prin care este demonstrată proprietatea parcurgerii BF de a calcula distanţa minimă de la orice vîrf v conectat de vîrful iniţial v0 la v0. Lema 2.2.1. Fie G=(V,E) un graf oarecare şi v0 V arbitrar. Atunci, pentru orice
muchie u ,v E , v0 ,v v0 ,u 1 . Demonstraţie Dacă u este conectat de v0 în G, atunci, evident, şi v este conectat de v0 în G. În acest caz, cel mai scurt drum de la v0 la v nu poate fi mai lung decît cel mai scurt drum de la v0 la u prelungit cu muchia (u,v), deci afirmaţia este demonstrată. În situaţia în care u nu este conectat de v0 în G, atunci, evident, rezultă inegalitatea v0 ,v v0 ,u 1 . Lema 2.2.2 Fie G=(V,E) un graf neorientat sau graf direcţionat şi v0 V vîrf iniţial al
procedurii de traversare BF. Atunci orice v V vizitat, are loc inegalitatea d v v0 ,v . Demonstraţie Afirmaţia este demonstrată prin inducţie după ordinea vizitării BF a elementelor v V conectate cu v0 în G.
Dacă v v0 , rezultă d v 0 şi, pentru orice u V \ v, d u u ,v , deci afirmaţia este adevărată. Fie v vîrful vizitat ca rezultat al procesării vîrfului u. Prin aplicarea ipotezei inductive, d u v0 ,u , a rezultatului lemei 2.2.1 şi a procedurii de parcurgere BF obţinem,
d v d u 1 v0 ,u 1 v0 ,v .
Deoarece vîrful v nu a fost anterior găsit în lista vecinilor nici unui nod studiat înaintea vîrfului u, v este inserat în C.
Lema 2.2.3 Fie G=(V,E) un graf neorientat sau graf direcţionat şi C v1 ,v2 ,...,v p
coada calculată la un moment al aplicării procedurii de parcurgere BF. Atunci următoarele inegalităţile sînt verificate, [Cor,Lei şa]
d v p d v1 1
d vi d vi 1 , i 1,..., p 1 .
Teorema 2.2.1. Corectitudinea procedurii BF Fie G=(V,E) graf neorientat sau graf direcţionat şi v0 V vîrf iniţial al procedurii de traversare BF. Atunci metoda BF calculează toate vîrfurile v conectate cu v0 în G şi, pentru orice v v0 , v V vizitat, un cel mai scurt v0-v drum este format dintr-un v0-u drum şi muchia (u,v), unde u este acel vîrf prin procesarea căruia este determinată vizitarea lui v. Demonstraţie Fie Vk v V / v0 ,v k mulţimea vîrfurilor situate la distanţă k de v0. Rezultatul teoremei este demonstrat prin inducţie după k, cu ipoteza inductivă, Ik: v Vk , există un singur moment al execuţiei procedurii BF în care este determinată următoarea evoluţie, d v k şi v C ; dacă v v0 , vîrful u care determină inserarea lui v în C este element al mulţimii Vk 1 .
Pentru k 0 , V0 v0 . La momentul iniţial, C v0 şi d v0 0 , deci I este verificată. Verificarea ipotezei Ik în condiţiile în care I0 ,…,Ik-1 sînt adevărate este bazată pe următoarea observaţie. Pe tot parcursul execuţiei procedurii BF, C Ø şi, dacă u C , atunci 12
Algoritmi și tehnici de programare
13
d u şi vîrful care a determinat procesarea lui u rămîn constante. Din
lema
rezultă
2.2.3.
că,
dacă
C v1 ,v2 ,...,v p ,
atunci
d vi d vi 1 , i 1,..., p 1 . Fie v Vk , k 1 . Din proprietatea de monotonie şi ipoteza Ik-1, rezultă că v a fost inserat în C după ce toate vîrfurile u Vk 1 au fost deja inserate în coadă. Deoarece v0 ,v k , obţinem că există un v0-v drum de lungime k şi u Vk 1 astfel încît
u ,v E . Fără a pierde din generalitate, vom presupune că u este primul vîrf din Vk 1 inserat în
C. La momentul în care vîrful u devine prim element al cozii C, toate vîrfurile vecine cu u în G sînt inserate în C, deci şi vîrful v. Rezultă că d v d u 1 k , unde u este acel vîrf care precede v pe un cel mai scurt v0-v drum. Observaţii 1. Demonstrarea teoremei de corectitudine a parcurgerii BF stabileşte şi o modalitate de calcul al unui cel mai scurt v0-v drum astfel. Pentru orice v V conectat cu v0 în G, fie pv V vîrful a cărui procesare a determinat inserarea lui v în C. Un v0-v drum de lungime minimă este v0- pv drumul cel mai scurt “prelungit” cu muchia pv,v . 2. Aplicarea metodei BF unui graf oarecare G determină obţinerea unui arbore (vezi
capitolul 9) Gp, numit subgraful predecesorilor definit de BF pe G, unde G p V p , E p şi
V p v V / pv V v0 , E p pv,v E / v V \ v0 .
Exemplu 2.2.4 Prin aplicarea procedurii BF grafului din 2.2.1, obţinem,
1 2 5
3 6
4
7
14
Metode de programare
2.2.2. Metoda de parcurgere DF (Depth First) Ideea metodei DF revine la parcurgerea în adîncime a grafurilor. Considerînd v0 vîrf iniţial şi M mulţimea vîrfurilor vizitate de procedură, pentru vizitarea vecinilor este considerat unul din vîrfurile din M cu proprietatea că lungimea drumului calculat de metodă pînă la vîrful iniţial v0 este maximă. Implementarea acestei metode poate fi realizată în mai multe moduri, pentru menţinerea mulţimii vîrfurilor grafului disponibilizate pînă la momentul curent fiind utilizată o structură de de date de tip stivă S. La momentul iniţial se introduce în stivă v0. La fiecare pas, se preia cu ştergere ca vîrf curent vîrful stivei S şi se introduc în stivă vecinii încă nevizitaţi ai vîrfului curent. Un vîrf se marchează ca vizitat în momentul introducerii lui în S. Calculul continuă pînă cînd este efectuat un acces de preluare din stivă şi se constată că S este vidă. Pentru gestiunea vîrfurilor vizitate, se utilizează un vector c cu n componente, unde n reprezintă numărul vîrfurilor grafului şi, la fiecare moment, componentele sînt:
1, dacă i a fost vizitat ci 0, altfel Componentele vectorului c vor fi iniţializate cu valoarea 0. Exemple 2.2.5. Pentru graful, 1 2
3 6 4 7
5
şi v0=1, prin aplicarea metodei descrise, rezultă următoarea evoluţie. c 1
2
3
4
5
6
7
t=1
1
0
0
0
0
0
0
t=2
1
1
1
1
0
0
1
t=3
1
1
1
1
0
1
1
t=4
1
1
1
1
0
1
1
t
14
Algoritmi și tehnici de programare
15
t=5
1
1
1
1
1
1
1
t=6
1
1
1
1
1
1
1
t=7
1
1
1
1
1
1
1
t=8
1
1
1
1
1
1
1
S t t=1
1
t=2
7
4
3
2
t=3
6
4
3
2
t=4
4
3
2
t=5
5
3
2
t=6
3
2
t=7
2
t=8
Ordinea în care sînt vizitate vîrfurilor corespunzător acestei variante de parcurgere DF este: 1, 2, 3, 4, 7, 6, 5. 2.2.6. Pentru graful din exemplul 2.2.2 vîrfurile 8,9,10 care nu sînt conectate cu vîrful iniţial nu vor fi vizitate nici prin aplicarea metodei DF. Ordinea în care sînt vizitate vîrfurilor corespunzător acestei variante este: 1, 2, 3, 4, 6, 7, 5. O variantă de implementare a metodei DF rezultă prin gestionarea stivei S în modul următor. Iniţial vîrful v0 este unicul component al lui S. La fiecare etapă se preia, fără ştergere, ca vîrf curent vîrful stivei. Se introduce în stivă unul dintre vecinii vîrfului curent încă nevizitat. Vizitarea unui vîrf revine la introducerea lui în S. Dacă vîrful curent nu are vecini încă nevizitaţi, atunci el este eliminat din stivă şi este efectuat un nou acces de preluare a noului vîrf al stivei ca vîrf curent. Calculul se încheie în momentul în care este efectuat un acces de preluare a vîrfului stivei ca vîrf curent şi se constată că S este vidă. Evident, nici în cazul acestei variante nu vor fi vizitate vîrfurile care nu sînt conectate cu vîrful iniţial ales.
16
Metode de programare
Exemplu 2.2.7. Pentru graful,
1 2
3 6 4 7
5
şi v0=1, prin aplicarea metodei descrise, rezultă următoarea evoluţie.
c
1
2
3
4
5
6
7
t t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 t=9 t=10 t=11 t=12 t=13 t=14
1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1 1 1 1 1
S t t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 t=9 t=10 t=11
1 2 4 3 6 7 6 3 4 5 4
1 2 4 3 6 3 4 2 4 2
1 2 4 3 4 2 1 2 1
1 2 4 2 1
1 2 1
1
1
16
Algoritmi și tehnici de programare
t=12 t=13 t=14
17
2 1
1
Ordinea în care sînt vizitate vîrfurile corespunzător acestei variante este: 1, 2, 4, 3, 6, 7, 5. Următoarea sursă C implementează varianta precedentă de parcurgere DF. #include <stdio.h> #include #include typedef struct nn{ int inf; struct nn *leg; }nod,* pnod; int insereaza_stiva(pnod *head,int info) { pnod nou; if(nou=(pnod)malloc(sizeof(nod))){ nou->inf=info; nou->leg=*head; *head=nou; return 1; } else return 0; } int extrage_stiva(pnod *head,int *info) { if(head){ pnod aux=*head; *info=(*head)->inf; (*head)=(*head)->leg; free(aux); return 1; } else return 0;} void depth_first(int v0,int a[10][10],int n) { pnod head=NULL; int c[10]; for(int i=0;i
18
Metode de programare
printf("Numarul de varfuri:");scanf("%i",&n); printf("\nMatricea de adiacenta\n"); for(int i=0;i
2.2.3. Parcurgerea în adîncime în varianta generalizată – DFG Următoarea variantă de implementare a parcurgerii în adîncime, DFG, determină vizitarea tutror vîrfurilor grafului analizat (considerat neorientat sau direcţionat), indiferent dacă acesta este conex sau neconex. Fie G=(V,E) un graf oarecare. Vom presupune în continuare că nici un vîrf din V nu este etichetat cu informaţia 0. Implementare traversării DFG utilizează următoarele structuri, A, matricea de adiacenţă a grafului; p, vectorul predecesorilor (vezi § 2.2.1); f, vectorul care marchează încheierea analizării listei vîrfurilor vecinilor nodului curent; mark, definit pentru orice v V prin, 0, dacă v nu a fost încă analizat mark[v]= 1, dacă v este procesat la momentul curent 2, dacă consultarea lui v este încheiată d, definit pentru orice v V prin d[v]=t, unde t este momentul de timp la care este iniţiată analiza vîrfului v. Considerînd t variabilă publică desemnînd momentul prelucrării, procedura DFG poate fi descrisă prin intermediul următoarelor funcţii. void DFG(graf G) { for( u V ){ mark[u]=0; p[u]=0; } t=0; for( u V ) if(!mark[u])DF_Visit(u); } void DF_Visit(varf u) { mark[u]=1; d[u]=t++; for( v V :A[u][v]==1) if(!mark[v]){ p[v]=u; DF_Visit(v); } mark[u]=2; f[u]=t++; }
18
Algoritmi și tehnici de programare
19
Prin aplicarea parcurgerii în adîncime în varianta generalizată sînt obţinute informaţii suplimentare ale grafului de intrare. Metoda DFG determină obţinerea subgraful predecesorilor, G p , de tip graf pădure (componentele conexe – vezi § 2.3- sînt arbori - vezi capitolul 9). Fiecare componentă conexă a lui G p este construită prin executarea modulului DF_Visit. De asemenea,
vîrfurile u ,v V au proprietatea că u pv dacă şi numai dacă funcţia DF_Visit(v) a fost apelată la momentul căutării în lista vecinilor vîrfului u. O altă proprietate importantă a metodei de parcurgere DFG este aceea că, după încheierea calculului, este determinată o structură de tip paranteză astfel. Dacă momentul selectării vîrfului u pentru procesare este marcat prin “(u” şi momentul încheierii prelucrării lui u este notat “u)”, atunci istoricul traversării DFG pentru calculul fiecărui arbore din G p poate fi reprezentat prin intermediul unei expresii corecte din punct de vedere al parantezării. Teorema 2.2.2 Corectitudinea parantezării determinată de aplicarea metodei DFG Fie G=(V,E) un graf sau un graf direcţionat. Prin aplicarea traversării DFG este obţinut următorul rezultat. Pentru orice u ,v V , una şi numai una din următoarele afirmaţii este adevărată, [Cor,Lei şa] 1) d u , f u şi d v, f v sînt disjuncte; 2)
d u, f u d v, f v şi u este un descendent al lui v în arborele corespunzător
din G p ; 3)
d u, f u d v, f v şi u este un ancestor al lui v în arborele corespunzător din Gp .
Observaţie Fie G=(V,E) un graf sau un graf direcţionat. Pe baza procedurii DFG poate fi realizată următoarea clasificare a elementelor e u ,v E ,
1) Muchii de tip arbore în DF- graful pădure G p , etichetate cu T: u ,v are eticheta T dacă procesarea vîrfului v a fost decisă ca rezultat al testării existenţei muchiei e; 2) Muchii de tip înapoi, cu etichetă B: u ,v este muchie B dacă v este ancestorul lui u într-o componentă conexă a DF- grafului pădure G p ;
3) Muchii de tip înainte, notate cu F: acele muchii u ,v , neetichetate cu T şi în care v este descendent al lui u într-o componentă conexă a DF- grafului pădure G p ;
4) Muchii de tip trecere, etichetate cu C: toate muchiile u ,v rămase neetichetate după încheierea etichetării cu T, B şi F. Teorema 2.2.3. Fie G=(V,E) un graf neorientat. Orice element e E este fie de tip T, fie de tip B. [Cor,Lei şa] Teorema 2.2.4. Criteriu de aciclicitate pentru grafuri direcţionate Un graf direcţionat este aciclic (vezi §2.4) dacă şi numai dacă nici una din muchii nu este de tip B. [Cor,Lei şa]
20
Metode de programare
Exemple 2.2.8. Pentru graful 1
8 3
2
6
4
9
10
5 7 obţinem, 1) ordinea de parcurgere DFG a vîrfurilor: 1,2,3,4,6,7,5,8,9,10 2) graful pădure G p ,
8 1
2
9
3 10
4 6
5
7 3) structurile paranteză: (1 (2 (3 3) (4 (6 (7 7) 6) (5 5) 4) 2) 1) şi (8 (9 (10 10) 9) 8) 4) clasificarea muchiilor,
2
T
1
10
4
B
T
T
T
T
6
9
3
T B
8
T
5
B
T 7 2.2.9 Fie graful direcţionat,
6 5
7 8
1
2
4
3
Prin parcurgerea DFG obţinem următoarea ordonare: 1,7,6,8,5,2,4,3. Subgraful predecesorilor este format din următoarele componente,
20
Algoritmi și tehnici de programare
21
1
2 4
7 6
3
8
5 Structurile paranteză: (1 (7 (6 (5 5) 6) (8 8) 7) 1) şi (2 (4 4) (3 3) 2). Clasificarea muchiilor grafului direcţionat este,
1 T
2 T
T B
6 T
4
F
7
C
T
T C
B 3
8 C
5
2.3. Drumuri în grafuri. Conexitate 2.3.1 Drumuri; definiţii Una dintre cele mai importante proprietăţi ale grafurilor o constituie posibilitatea de accesare, prin intermediul unei secvenţe de muchii (arce), dintr-un vîrf dat a oricărui alt vîrf al grafului, proprietate cunoscută sub numele de conexitate sau conexiune. Aşa după cum a rezultat în §2.2., dacă G=(V,E) este un graf conex, atunci pentru orice vîrf iniţial v0 considerat metodele BF şi DF permit vizitarea tuturor vîrfurilor din V. Definiţia 2.3.1. Fie G=(V,E) un graf, u,vV. Secvenţa de vîrfuri : u0, u1,..,un este un u-v drum dacă u0=u, un=v, uiui+1E pentru toţi i, 0 i n . Lungimea drumului, notată l() este egală cu n. Convenţional, se numeşte drum trivial, un drum cu l()=0. Definiţia 2.3.2. Fie : u0, u1,..,un un drum în graful G=(V,E). este un drum închis dacă u0=un; în caz contrar, se numeşte drum deschis. Drumul este elementar dacă oricare două vîrfuri din sînt distincte, cu excepţia, eventual, a extremităţilor. Drumul este proces dacă, pentru orice 0 i j n 1 uiui+1 ujuj+1. Evident, orice drum elementar este un proces.
22
Metode de programare
Exemplu 2.3.1. Pentru graful,
v2
v4 v5
v1
v3
1: v1, v2, v3, v2, v5, v3, v4 este un v1- v4 drum care nu este proces; 2: v1, v2, v5, v1, v3, v4 este un v1- v4 proces care nu este drum elementar; 3: v1, v3, v4 este un v1- v4 drum elementar. Definiţia 2.3.3. Fie : u0, u1,..,un un drum în graful G=(V,E). ’: v0, v1,..,vm este un subdrum al lui dacă ’ este un drum şi pentru orice j, 0 j m , există i, 0 i n astfel încît ui=vj. Observaţie Orice drum cu lungime cel puţin 1 conţine cel puţin un drum elementar cu aceleaşi extremităţi. Într-adevăr, dacă : u0, u1,..,un nu este elementar, atunci există 0 i j n şi i 0 sau j n astfel încît ui=uj. Atunci drumul
u j u j 1 ...u n , dacă i 0 : u0 u1 ...u i , dacă j 0 u u ...u u ...u , dacă i 0 , j n 0 1 i j 1 n '
este de asemenea un u0-un drum. Aplicînd în continuare eliminarea duplicatelor vîrfurilor în modul descris, rezultă în final un u0-um drum elementar.
Exemplu 2.3.2. În graful,
v2
v6
v1
v4 v3
v7
v5
v8
v10
v9
dacă : v1, v2, v4, v5, v3, v1, v2, v5, v6, v7, v8, v9, v5, v9, v8, v10, atunci 1: v1, v2, v5, v9, v8, v10, 2: v1, v2, v4, v5, v9, v8, v10 sînt v1-v10 subdrumuri elementare.
22
Algoritmi și tehnici de programare
23
2.3.2. Matricea existenţei drumurilor; algoritmul Roy-Warshall Lema 2.3.1. Fie G=(V,E) un graf, V n . Dacă A este matricea de adiacenţă asociată grafului, atunci, pentru orice p1, a ij( p ) este numărul vi-vj drumurilor distincte de lungime p din
graful G, unde A p aij( p ) . Demonstraţie Demonstrarea acestei afirmaţii este realizată prin inducţie după p Pentru p=1, deoarece pentru orice 1 i , j n există cel mult un vi-vj drum de lungime 1 şi dacă există, fie acesta Г: vi, vj. Rezultă că numărul vi-vj drumurilor de lungime 1 este egal cu aij1 .
Presupunem că Ap-1 = aij p 1 are proprietatea că pentru toţi 1 i , j n , aij p 1 este egal cu numărul vi-vj drumurilor de lungime p-1 în G.
Cum Ap=Ap-1A = aij p , rezultă că, 1 i , j n , a ij( p )
p
a k 1
( p 1 ) ik
a kj . Orice vi-vj drum
de lungime p în G conţine un vi-vk drum de lungime p-1 pentru un anume vk adiacent cu vj şi reciproc, pentru orice vk adiacent cu vj oricărui vi-vk drum de lungime p-1 îi corespunde un vi-vj drum de lungime p. Din relaţia care caracterizează elementele aij p , utilizînd ipoteza inductivă, rezultă
afirmaţia enunţată mai sus. Definiţia 2.3.4. Fie Mn({0,1)} mulţimea matricelor de dimensiuni nxn, componentele fiind elemente din mulţimea {0,1}. Pe Mn({0,1)}se definesc operaţiile binare, notate şi , astfel: pentru orice A=(aij), B=(bij) din Mn({0,1)}, A B=(cij), A B=(dij), unde 1 i , j n , cij=max{aij, bij} dij=max{min{aik, bkj}, 1 k n }.
; k 1 secvenţa de matrice definită k
(k )
Dacă A=(aij) Mn({0,1)}, se notează A a ij prin:
1
( k 1 )
k
, k 2 . Dacă A este matricea de adiacenţă a unui graf G=(V,E), atunci pentru fiecare k, A
A, A A A
(k ) 1, dacă există drum de la i la j de lungime k 1 k n 1 , a ij 0 , altfel (1)
(2)
( n 1 )
Matricea M A A A se numeşte matricea existenţei drumurilor în graful G. Semnificaţia componentelor matricei M este:
0 , dacă nu există vi v j drum în G 1 i , j n , mij 1, altfel
24
Metode de programare
Exemplu 2.3.3. Pentru graful,
2 1 3
4 0 1 A 1 1
1 0 0 0
1 0 0 1
1 0 , 1 0
1 2 0 A 1 1
0 1 1 1
1 1 1 1
1 1 , 1 1
1 3 1 A 1 1
1 0 1 1
1 1 1 1
1 1 1 1 1 1 , M 1 1 1 1 1 1
1 1 1 1
1 1 1 1
Observaţie Calculul matricei existenţei drumurilor permite verificarea dacă un graf dat este conex. Graful este conex dacă şi numai dacă toate componentele matricei M sînt egale cu 1. Algoritmul Roy-Warshall calculează matricea existenţei drumurilor într-un graf G cu n vîrfuri. void Roy_Warshall (unsigned char a[10][10],unsigned n,unsigned char m[10][10]) {int i,j,k; for (i=0;i
Datele de intrare sînt: n, numărul de noduri şi A, matricea de adiacenţă corespunzătoare grafului. Matricea M calculată de algoritm constituie ieşirea şi este matricea existenţei drumurilor în graful G.
2.3.3. Componente conexe ale unui graf Definiţia 2.3.5. Fie G=(V,E) graf netrivial. Vîrfurile u,v V sînt conectate dacă există un u-v drum în G. Definiţia 2.3.6. Dacă G este un graf, atunci o componentă conexă a lui G este un subgraf conex al lui G, maximal în raport cu proprietatea de conexitate.
24
Algoritmi și tehnici de programare
25
Exemplu 2.3.4. Componentele conexe ale grafului
1
5
2 6 4 3 sînt: C1={1,2,3}, C2={4,5}, C3={6}. Observaţii 1) Un graf este conex dacă şi numai dacă numărul componentelor sale conexe este 1. 2) Mulţimile de vîrfuri corespunzătoare oricăror două componente conexe distincte sînt disjuncte. Rezultă că mulţimile de vîrfuri corespunzătoare componentelor conexe ale unui graf formează o partiţie a mulţimii vîrfurilor grafului. Problema determinării componentelor conexe corespunzătoare unui graf poate fi rezolvată în modul următor. Iniţial, este selectat drept vîrf curent un vîrf al grafului pentru care este calculată componenta conexă care îl conţine. Dacă există vîrfuri care nu aparţin componentei conexe determinate, este ales drept vîrf curent unul dintre aceste vîrfuri. În continuare este aplicată aceeaşi metodă, pînă cînd au fost găsite toate componentele conexe ale grafului. Determinarea componentei conexe care conţine un vîrf v0 dat poate fi realizată pe baza următorului algoritm. Pentru G=(V,E), V n , n 1 şi v0 V, paşii algoritmului sînt: Pas1: V0={v0}; E0= ; i=0; Pas 2: repetă Pas 3 pînă cînd Vi=Vi-1 şi Ei=Ei-1 Pas 3: i=i+1;
Vi Vi 1 v / v V, u Vi 1 , uv E;
E i E i 1 e / e E, u Vi 1 , u incident cu e; Ieşirea este Gi=(Vi,Ei), componenta conexă din care face parte v0. Exemplu 2.3.5. Pentru graful,
1
4
2
5
7
8
3
9
6
Aplicarea algoritmului descris pentru v0=1, determină următoarea evoluţie: I Vi Ei i=0 {1} Ø i=1 {1,2,4} {(1,2),(1,4)} i=2 {1,2,4,7,8,5} {(1,2),(1,4),(2,7),(2,8),(7,8),(4,5),(4,7),(5,8)}
26
Metode de programare
2.3.4. Drumuri de cost minim Definiţia 2.3.7. Fie G=(V,E,w) un graf ponderat. Costul drumului : u1,u2,..,un, notat L(), este definit prin: n 1
L wu i ,u i 1 . i 1
Pentru orice u şi v vîrfuri conectate în G, u v, w-distanţa între u şi v, notată D(u,v), este definită prin, Du ,v minL , Duv , unde Duv desemnează mulţimea tuturor u-v drumurilor elementare din G. Dacă Duv este astfel încît D(u,v)=L(), drumul se numeşte drum de cost minim. Observaţie Cu toate că este utilizat termenul de w-distanţă, în general D nu este o distanţă în sensul matematic al cuvîntului.În particular, dacă funcţia pondere asociază valoarea 1 fiecărei muchii a grafului, atunci pentru fiecare pereche de vîrfuri distincte ale grafului, costul D(u,v) este lungimea unui cel mai scurt drum între cele două vîrfuri. În acest caz D este o distanţă pe mulţimea vîrfurilor. Algoritmul Dijkstra Următorul algoritm a fost propus de către E. W. Dijkstra pentru determinarea wdistanţelor D(u0,v) şi a cîte unui u0-v drum de cost minim pentru fiecare vîrf vu0 într-un graf ponderat, unde u0 este prestabilit.
Fie G=(V,E,w) un graf conex ponderat, u0V, SV, u0S. Se notează S V \ S şi
D u0 , S min Du0 , x ; x S . Fie v S astfel încît D(u0,v)=D(u0, S ), : u0, u1,…,upv un u0-
v drum de cost minim. Evident, 0ip uiS şi ’: u0, u1,…,up un u0- up drum de cost minim. De asemenea,
D u0 , S min Du0 ,u w( uv ); u S ,v S ,uv E .
Dacă xS, y S astfel încît D u0 , S Du0 , x w( xy ) , rezultă
Du0 , y Du0 , x w( xy ) .
Pentru determinarea a cîte unui cel mai ieftin u0-v drum, algoritmul consideră o etichetare dinamică a vîrfurilor grafului.Eticheta vîrfului v este (L(v),u), unde L(v) este lungimea unui cel mai ieftin u0-v drum determinat pînă la momentul respectiv şi u este predecesorul lui v pe un astfel de drum. Pentru (V,E,w) graf conex ponderat, V n şi u0V, calculul implicat de algoritmul Dijkstra poate fi descris astfel: Pas 1: i=0; S0={u0}; L(u0)=0, L(v)= pentru toţi v V, v≠u0. Dacă n=1 atunci stop Pas 2: Pentru toţi v S i , dacă L(v)>L(ui)+w(uiv), atunci L(v)=L(ui)+w(uiv) şi etichetează v cu (L(v),ui). Pas 3: Se determină d=min{L(v), v S i } şi se alege ui+1 S i astfel încît L(ui+1)=d. Pas 4: Si+1=Si {ui+1} Pas 5: i=i+1. Dacă i=n-1, atunci stop. Altfel, reia Pas 2. Observaţie Dacă (V,E,w) graf ponderat neconex, atunci, pentru u0V, algoritmul lui Dijkstra permite determinarea w-distanţelor D(u0,v) şi a cîte unui u0-v drum de cost minim pentru toate vîrfurile v din componenta conexă căreia îi aparţine u0.
26
Algoritmi și tehnici de programare
27
Exemplu 2.3.6. Fie graful ponderat, 1 5
1
2
9
3 16
2 5
5
4
Considerînd u0=1, etapele în aplicarea algoritmului Dijkstra sînt: P1: i=0; S0={1}; L(1)=0, L(i)= pentru toţi i 2,5 . P2: S 0 ={2,3,4,5}, u0=1 L(2)= >L(1)+5=5 L(2)=5, etichetează 2 cu 1 L(3)= >L(1)+1=1 L(3)=1, etichetează 3 cu 1 L(4)= >L(1)+9=9 L(4)=9, etichetează 4 cu 1 L(5)= , w(1,5)= , deci L(5) nu se modifică P3: selectează u1=3, L(3)=1, cea mai mică dintre w-distanţele calculate la P2 P4: S1={1,3} P5: i=i+1=1 ≠ 4, reia P2 P2: S1 ={2,4,5}, u1=3 Nu se modifică nici o etichetă şi nici o w-distanţă (w(3,i)= , pentru toţi i din
S1 ) P3: selectează u2=2, L(2)=5, cea mai mică dintre w-distanţele calculate la P2 P4: S2={1,3,2} P5: i=i+1=2 ≠ 4, reia P2 P2: S 2 ={4,5}, u2=2 L(4)= 9>L(2)+2=7 L(4)=7, etichetează 4 cu 2 L(5)= >L(2)+16=21, etichetează 5 cu 2 P3: selectează u3=4, L(4)=7, cea mai mică dintre w-distanţele calculate la P2 P4: S3={1,3,2,4} P5: i=i+1=3 ≠ 4, reia P2 P2: S 3 ={5}, u3=4 L(5)= 21>L(4)+5=12, etichetează 5 cu 4 P3: selectează u4=5, L(5)=12, cea mai mică dintre w-distanţele calculate la P2 P4: S3={1,3,2,4,5} P5: i=i+1=4, stop. Algoritmul calculează următoarele rezultate: Vîrful v pînă la care este 1 calculată w-distanţa D(1,v), eticheta lui v 0, 1
2
3
4
5
5, 1
1, 1
7, 2
12, 4
28
Metode de programare
Drumurile de cost minim de la vîrful 1 la fiecare dintre vîrfurile grafului se stabilesc pe baza sistemului de etichete astfel: drumul de la 1 la un vîrf v este dat de: v1, eticheta lui v, v2 eticheta lui v1 şamd, pînă se ajunge la eticheta 1. Astfel, v0 -drumurile de cost minim sînt: pînă la 2: 2,1; pînă la 3: 3,1; pînă la 4: 4,2,1; pînă la 5: 5,4,2,1. Următoarea sursă C implementează algoritmul Dijkstra. #include<stdio.h> #include #include typedef struct{ int predv; float L; } eticheta; void creaza(int *s,int *sb,int nv,int u0) { s[0]=u0; for(int j=0,i=0;ir[s[k]].L+w[sb[j]][s[k]]){ r[sb[j]].L=r[s[k]].L+w[sb[j]][s[k]]; r[sb[j]].predv=s[k]; } int ui; for(j=0;j
28
Algoritmi și tehnici de programare
29
modifica(s,sb,ui,&ns,&nb); } return r; } void main() { int n,i,j; clrscr(); printf("Numarul de varfuri"); scanf("%i",&n); printf("Matricea ponderilor:\n"); float w[50][50]; for(i=0;i
În anumite aplicaţii este necesară exclusiv determinarea w-distanţelor D(v0,v), pentru toţi vV. În acest caz algoritmul Roy-Floyd permite o rezolvare a acestei probleme mai simplu de implementat decît algoritmul Dijkstra. Algoritmul Roy-Floyd Pentru (V,E,w) graf ponderat, V n şi W matricea ponderilor, sistemul de w-distanţe D(v0,v), vV, poate fi calculat pe baza următoarei funcţii (similară algoritmului Roy-Warshall), void Roy_Floyd (float w[10][10],unsigned n,float d[10][10],float MAX) {int i,j,k; for (i=0;id[i][j]+d[j][k]) d[i][k]=d[i][j]+d[j][k]; }
Matricea D calculată de algoritm este matricea w-distanţelor D(u,v) în graful ponderat conex (V,E,w); pentru orice 1 i , j n
30
Metode de programare
D( vi ,v j ), vi ,v j sunt conectate d ij , altfel Într-adevăr, procedura realizează calculul dinamic al w-distanţei între oricare două vîrfuri i şi k, astfel: dacă există un drum i-k drum ce trece prin j ( 1 j n ), cu costul corespunzător (dij+djk) inferior costului curent (dik), atunci noul drum de la i la k via j este de cost mai mic decît costul drumului vechi, deci w-distanţa între i şi k trebuie reactualizată la dij+djk. Algoritmul Yen Algoritmul propus de Yen pentru calculul tuturor w-distanţelor într-un graf ponderat este mai eficient din punctul de vedere al volumului de operaţii decît algoritmul Roy-Floyd. Fie (V,E,w) un graf ponderat şi W matricea ponderilor. Pentru determinarea w-distanţelor de la vîrful vk fixat la celelalte vîrfuri ale grafului, algoritmul Yen iniţiază următoarele operaţii, Pas 1: D=W Pas 2: i=1; λ(k)=0, b(k)=0; λ(j)=0, pentru toţi 1 j n , j k Pas 3: Calculează min{dkj; 1 j n , λ(j)=1}; Determină j0 astfel încît λ(j0)=1 şi d kj0 = min{dkj; 1 j n , λ(j)=1} B(j0)= d kj0 , λ(j0)=0 d[k,j] =min{d[k,j],d[k,j0]+d[j0,j]}, pentru toţi j, 1 j n i=i+1 Pas 4: Dacă i
1 4 5
3 7
2 1 4
4
2 5 3
30
Algoritmi și tehnici de programare
31
Se consideră vk=1.
3 Pas 1: D 2 7 4
3 5
2 5 4 1
7 4
4 1
Pas 2: i=1, λ=(0,1,1,1,1); B(1)=0
3 Pas 3: j0=3, B(3)=2, λ=(0,1,0,1,1); D 2 7 4
3 5
2 5 4 1
6 4
3 1 ; i=2
Pas 4: i<5, reia Pas 3 Pas 3: j0=2, B(2)=3, λ=(0,0,0,1,1); nici o modificare în matricea D; i=3 Pas 4: i<5, reia Pas 3 Pas 3: j0=5, B(5)=3, λ=(0,0,0,1,0); nici o modificare în matricea D; i=4 Pas 4: i<5, reia Pas 3 Pas 3: j0=4, B(4)=6, λ=(0,0,0,0,0); nici o modificare în matricea D; i=5 Pas 4: i=5, stop.
2.4. Circuite şi cicluri în grafuri şi în digrafuri Definiţia 2.4.1. Fie G=(V,E) un graf netrivial, u, vV şi un u-v drum în G. se numeşte proces dacă toate muchiile drumului sînt distincte. Drumul este trivial dacă : u,u. Definiţia 2.4.2. Drumul este un circuit dacă este un proces netrivial închis. Definiţia 2.4.3. Circuitul : v1, v2,…., vn, v1 cu n3 este un ciclu al grafului, dacă, pentru orice i, j, cu 1 i , j n, i j , rezultă vivj. Observaţie Orice ciclu este un drum elementar închis. Definiţia 2.4.4. Graful G este aciclic dacă nu există cicluri în G. Observaţie Într-un digraf D noţiunile de proces, circuit, ciclu sînt definite ca şi în cazul grafurilor.
32
Metode de programare
Exemple 2.4.1. În graful, v1 v4 v2 v3 v5 v6 1: v1, v2, v3, v6, v5 este un proces; 2: v1, v2, v3, v6, v5, v3, v4, v1 este un circuit şi nu este ciclu; 3: v1, v3, v5, v4, v1 este un ciclu.
2.4.2. Drumul : v1,v2,v4,v3,v1 este un ciclu, deci graful conţine cicluri.
v1
v2
v3
v4
V1
V2
V3
V4
2.4.3. Digraful,
nu conţine cicluri. Definiţia 2.4.5. Fie D=(V,E) un digraf. Funcţiile grad exterior, odD, respectiv grad interior, idD, sînt definite prin, od D : V N ; id D : V N ,
u V , od D u v / v V , uv E , u V , id D u v / v V , vu E
Funcţia grad, notată degD, este definită astfel,
deg D : V N, u V, deg D u id D u od D u .
Algoritmul Marimont Procedura Marimont verifică dacă un digraf D=(V,E), V n , este sau nu aciclic. La terminarea calculului este afişat mesajul “DA”, dacă digraful D este aciclic, respectiv “NU”, în caz contrar. Descrierea pe paşi a algoritmului Marimont este, Pas 1: V0=V, E0=E, D0=(V0,E0) Pas 2: Dacă od D0 v 1 pentru toţi vV0, scrie “NU”, stop (dacă toate vîrfurile sînt extremităţi iniţiale ale măcar unui arc, atunci există cicluri în D0); altfel, continuă. Pas 3: Selectează vV0 cu od D0 v 0 ;V0=V0\{v}; E0=E0-{e/ eE0, e incidentă cu v în D0}; D0=(V0,E0) Pas 4: Dacă V0Ø, atunci reia pasul 2; altfel scrie “DA”, stop. Exemple 2.4.4 Pentru digraful,
32
Algoritmi și tehnici de programare
33
1 e1 4
e2
2
e3
e4
3
e5 5
evoluţia algoritmului Marimont este, Pas 1: V0={1,2,3,4,5}, E0={e1,e2,e3,e4,e5} Pas 2: od D0 5 0 , continuă
1 e1 4
e2
2
e3
e4
3
Pas 3: Selectează vîrful 5, elimină 5 din V0, elimină arcul e5 E0 Pas 4: reia de la pasul 2 Pas 2: od D0 i 1 pentru toţi i din V0 ={1,2,3,4}, scrie “NU”, stop. 2.4.5. Pentru digraful D:
6
e7
e9
5
4 e6
e1 e5
e3 3
e8
7
1 e4
2 e2
algoritmul Marimont determină următoarea secvenţă de operaţii: Pas 1: V0={1,2,3,4,5,6,7}, E0={e1,e2,e3,e4,e5,e6,e7,e8,e9} Pas 2: od D0 7 0 , continuă Pas 3: Selectează vîrful 7, elimină 7 din V0, elimină arcele e8 şi e9 din E0
D0:
6
e7
5
4 e6
1 e4
e1 e5
e3 3
2 e2
Pas 4: reia de la pasul 2 Pas 2: od D0 6 0 , continuă Pas 3: Selectează vîrful 6, elimină 6 din V0, elimină arcul e7 din E0 D0:
5
4 e6
1 e4
e1 e5
e3 3
2 e2
34
Metode de programare
Pas 4: reia de la pasul 2 Pas 2: od D0 5 0 , continuă Pas 3: Selectează vîrful 5, elimină 5 din V0, elimină arcul e6 din E0
D0:
1 e4
4
e1 e5
e3 3
2 e2
Pas 4: reia de la pasul 2 Pas 2: od D0 4 0 , continuă Pas 3: Selectează vîrful 4, elimină 4 din V0, elimină arcele e4, e5 şi e3 din E0
D0:
1 e1 2 e2 3 Pas 4: reia de la pasul 2 Pas 2: od D0 3 0 , continuă Pas 3: Selectează vîrful 3, elimină 3 din V0, elimină arcul e2 din E0
D0: 1 e1 2 Pas 4: reia de la pasul 2 Pas 2: od D0 2 0 , continuă Pas 3: Selectează vîrful 2, elimină 2 din V0, elimină arcul e1 din E0
D0: • 1 Pas 4: reia de la pasul 2 Pas 2: od D0 1 0 , continuă Pas 3: Selectează vîrful 1, elimină 1 din V0 V0=Ø Pas 4: scrie “DA”, stop. Algoritmul Marimont poate fi descris în C astfel, #include<stdio.h> #include typedef struct{ int vi,vf;} arc; int grad_exterior(arc *arce,int na,int v) { int od=0; for(int i=0;i
34
Algoritmi și tehnici de programare if(arce[i].vi==v) od++; return od; } void elimina_varf(int *varf,int *nv,int v) { int gasit=0; for(int i=0;(i<*nv)&&!gasit;i++) if(varf[i]==v){ gasit=1; for(int j=i+1;j<*nv;j++) varf[j-1]=varf[j]; } (*nv)--; } void elimina_arce(arc *arce,int *na, int v) { for(int i=0;i<*na;) if((arce[i].vi==v)||(arce[i].vf==v)){ for(int j=i+1;j<*na;j++){ arce[j-1].vi=arce[j].vi; arce[j-1].vf=arce[j].vf; } (*na)--; } else i++; } int ciclic(int *varf,arc *arce,int nv, int na) { for(int i=0;i
35
36
Metode de programare
printf("Numarul de varfuri"); scanf("%i",&n); for(i=0;i
36
Algoritmi și tehnici de programare
37
3. Structuri arborescente
Una dintre cele mai studiate clase de grafuri sînt cele de tip arbore. În acest capitol sînt prezentate principalele caracteristici ale arborilor, algoritmi pentru calculul arborelui parţial de cost minim, arbori direcţionaţi, arbori cu rădăcină şi arbori binari. Pe lîngă operaţiile primitive asupra arborilor – căutarea unei informaţii, inserarea unui nod, extragerea unui nod şi metode de parcurgere, sînt prezentate două clase importante de arbori binari: arbori de sortare şi arbori de structură.
3.1. Grafuri de tip arbore 3.1.1. Definiţii şi caracterizări ale grafurilor arbori Structurile cele mai simple şi care apar cel mai frecvent în aplicaţii sînt cele arborescente (arbori). Grafurile arbori constituie o subclasă a grafurilor conexe. Definiţia 3.1.1 Graful G este arbore dacă G este aciclic şi conex. Definiţia 3.1.2. Fie G=(V,E) graf arbore. Subgraful H=(V1,E1) al lui G este subarbore al lui G dacă H este graf arbore. Exemple 3.1.1. Graful 1 2
4
3
5
6 7
este arbore, deoarece, orice (i,j) E , i≠j, există un i-j drum şi graful nu conţine cicluri.
38
Metode de programare
3.1.2. Graful
1
4
3
2
7 5 7
nu este arbore, deoarece drumul :1,4,6,2,1 este un ciclu. 3.1.3. Graful
1
4
3
7
2 5
9
6 8
nu este arbore, deoarece conţine trei componente conexe: {1,2,3,4,6}, {3} şi {7,8}. Verificarea proprietăţii unui graf de a fi arbore poate fi realizată prin intermediul unor algoritmi care să verifice calităţile de conexitate şi respectiv aciclicitate. De asemenea, verificarea proprietăţii unui graf de a fi arbore poate fi realizată astfel. Proprietatea 1. Un graf G=(V,E), cu V n , E m este graf arbore dacă şi numai dacă G este aciclic şi n=m+1. Exemple 3.1.4. Graful din 3.1.1 este arbore, pentru că este aciclic şi n=7, m=6. 3.1.5. Graful din 3.1.2. nu este arbore pentru că este ciclic. 3.1.6. Graful din exemplul 3.1.3. nu este arbore deoarece este aciclic, dar n=9, m=6. Proprietatea 2 Un graf G=(V,E), cu V n , E m este graf arbore dacă şi numai dacă G este conex şi n=m+1. Exemple 3.1.7. Graful din 3.1.1. este arbore deoarece este conex şi n=m+1. 3.1.8. Graful conex din exemplul 3.1.2. nu este arbore pentru că n=6 şi m=8. 3.1.9. Graful din 3.1.3. nu este conex, deci nu este graf arbore. Observaţie Fie G=(V,E) un graf. Următoarele afirmaţii sînt echivalente, 1. G este graf arbore; 2. G este graf conex minimal: oricare ar fi eE, prin eliminarea muchiei e din E, graful rezultat nu este conex; 3. G este graf aciclic maximal: prin adăugarea unei noi muchii în graf rezultă cel puţin un ciclu.
38
Algoritmi și tehnici de programare
39
Definiţia 3.1.3. Se numeşte graf asimetric un digraf D=(V,E) cu proprietatea că pentru orice u ,v E dacă uvE, atunci vu E. Digraful D este simetric dacă u ,v E , uvE, dacă şi numai dacă vuE. Definiţia 3.1.4. Fie D=(V,E) digraf netrivial. Graful G=(V,E’), unde E’={uv/ uvE sau vuE} se numeşte graf suport al digrafului D. Definiţia 3.1.5. Un arbore direcţionat este un graf orientat asimetric şi astfel încît graful suport corespunzător lui este graf arbore. Definiţia 3.1.6. Arborele direcţionat T=(V,E) este arbore cu rădăcină dacă există rV astfel încît, pentru orice uV, u r, există r-u drum în T. Vîrful r se numeşte rădăcina arborelui direcţionat T. Definiţia 3.1.7. Fie T=(V,E) arbore direcţionat. Arborele T1=(V1,E1) este subarbore al lui T dacă V1V, E1E şi T1 este arbore direcţionat. Observaţie Graful suport al unui arbore direcţionat este aciclic, deci, pentru orice uV, u r, r-u drumul din T este unic. De asemenea, un arbore direcţionat are cel mult o rădăcină. Rezultă că, pentru orice uV, u r, distanţa de la rădăcină la vîrful u este egală cu numărul de muchii ale r-u drumului în T. Exemple 3.1.10. Arborele direcţionat
1
3 6
5
2
10
9
8
7
4
este arbore cu rădăcină 1.
3.1.11 Arborele direcţionat
1
2 7
3
4 5 nu are rădăcină. 3.1.12. Arborele
6
40
Metode de programare
1
2
4 6
5
8
10
este un subarbore cu rădăcină 1 al arborelui din 3.1.10.
3.1.2. Reprezentări şi parcurgeri ale arborilor orientaţi Definiţia 3.1.8. Un arbore orientat este un arbore direcţionat cu rădăcină. Definiţia 3.1.9. Fie T=(V,E), un arbore orientat cu rădăcină r. Un vîrf v 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. Deoarece orice arbore orientat este în particular digraf, reprezentarea arborilor orientaţi poate fi realizată prin utilizarea oricăreia dintre modalităţile prezentate în §8.1. Datorită caracteristicilor arborilor orientaţi pot fi însă obţinute reprezentări mai eficiente din punct de vedere al spaţiului de memorie solicitat. Una dintre modalităţi este reprezentarea de tip FIU-FRATE, care constă în numerotarea convenţională a vîrfurilor grafului şi memorarea, pentru fiecare vîrf i al arborelui, a următoarelor informaţii, - FIU(i): numărul ataşat primului descendent al vîrfului i; - FRATE(i): numărul ataşat vîrfului descendent al tatălui vîrfului i şi care urmează imediat lui i; - INF(i): informaţia ataşată vîrfului i (de obicei valoarea i). Pentru reprezentarea arborelui sînt reţinute rădăcina şi numărul nodurilor. Absenţa „fiului”, respectiv a :fratelui” unui vîrf este marcată printr-o valoare din afara mulţimii de numere ataşate vîrfurilor (de obicei valoarea 0). Exemplu 3.1.13. Arborele orientat
40
Algoritmi și tehnici de programare
41
1
2
3
5
6
9 10
11
4
7
12 13
8
14
15
16
este reprezentat astfel, N=16, R=1 (rădăcina), FIU=(2,5,0,8,0,9,0,14,0,0,0,0,0,0,0,0) FRATE=(0,3,4,0,6,7,0,0,10,11,12,13,0,15,16,0) O alternativă a reprezentării FIU-FRATE poate fi obţinută prin utilizarea structurile de date dinamice. Presupunînd că fiecare vîrf al arborelui are cel mult n descendenţi, fiecărui vîrf îi este ataşată structura, identificator vîrf
vector de legături către descendenţii vîrfului adresă fiu 1
…
adresă fiu n
Următoarea sursă C implementează problema construcţiei unui arbore orientat, reprezentat prin intermediul unei structuri dinamice arborescente. Numărul maxim de descendenţi ai unui nod este 4. În cazul unui număr mai mare de descendenţi este preferată în general reprezentarea FIU-FRATE, datorită dimensiunii spaţiului de memorie ocupat. Afişarea informaţiilor arborelui creat este realizată prin traversarea în A-preordine (a se vedea paragraful următor).
#include<stdio.h> #include #include typedef struct nod{ int inf; struct nod *fiu[4]; } arb, *arbore; void inserare_tata(arbore *ptata,int k,int info) { arbore nou=(arbore)malloc(sizeof(arb)); nou->inf=info; for(int i=0;i<4;i++)nou->fiu[i]=NULL; (*ptata)->fiu[k]=nou; }
42
Metode de programare
void inserare(arbore *ppred) { int j,info; arbore *pred; for(int nr=0;(*ppred)->fiu[nr];nr++){ (*pred)=(*ppred)->fiu[nr]; printf("Numarul de fii ai nodului %i:",(*pred)->inf); scanf("%i",&j); for(int k=0;k<j;k++){ scanf("%i",&info); inserare_tata(pred,k,info); } } for(nr=0;(*ppred)->fiu[nr];nr++) inserare(&((*ppred)->fiu[nr])); } void A_preordine(arbore r) { if(r){ printf("%i ",r->inf); for(int i=0;i<4;i++) A_preordine(r->fiu[i]); } } void main(){ clrscr(); int n,j,info; arbore radacina=NULL; printf("Introduceti informatiile pe niveluri\n"); printf("Introduceti radacina\n"); scanf("%i",&info); radacina=(arbore)malloc(sizeof(arb)); radacina->inf=info; for(int i=0;i<4;i++)radacina->fiu[i]=NULL; printf("Numarul de fii ai nodului %i",radacina->inf); scanf("%i",&j); for(int k=0;k<j;k++){ scanf("%i",&info); inserare_tata(&radacina,k,info); } arbore ppred=radacina; inserare(&ppred); printf("Parcurgerea A-preordine a arborelui : \n"); A_preordine(radacina); getch();}
Parcurgerea unui arbore orientat revine la aplicarea sistematică a unei reguli de vizitare a vîrfurilor arborelui. Cele mai utilizate reguli de parcurgere a arborilor orientaţi sînt A-preordine, A-postordine şi parcurgerea pe niveluri.
Parcurgerea în A-preordine Modalitatea de vizitare a vîrfurilor în parcurgerea în A-preordine poate fi descrisă astfel. Iniţial, rădăcina arborelui este selectată drept vîrf curent. Este vizitat vîrful curent şi sînt identificaţi descendenţii lui. Se aplică aceeaşi regulă de vizitare pentru arborii avînd ca rădăcini descendenţii vîrfului curent, arborii fiind vizitaţi în ordinea precizată prin numerele ataşate vîrfurilor rădăcină corespunzătoare.
42
Algoritmi și tehnici de programare
43
Exemplu 3.1.14. Pentru arborele orientat din exemplul 3.1.13., prin aplicarea parcurgerii în Apreordine, rezultă: 1,2,5,6,9,10,11,12,13,7,3,4,8,14,15,16. În reprezentarea FIU-FRATE, implementarea parcurgerii în A-preordine este realizată prin următoarea funcţie recursivă, cu parametru de intrare rădăcina arborelui curent. void A_preordine (nod R) { if (R){ vizit (R); A_preordine(FIU[R]); A_preordine(FRATE[R]); } }
În sursa prezentată în paragraful precedent, funcţia A-preordine implementează acest tip de traversare în cazul arborilor orientaţi reprezentaţi prin intermediul structurilor arborescente. Parcurgerea A-postordine Regula de parcurgerea în A-postordine este asemănătoare traversării A-preordine, singura diferenţă fiind aceea că, în acest tip de traversare, rădăcina fiecărui arbore este vizitată după ce au fost vizitate toate celelalte vîrfuri ale arborelui. Exemplu 3.1.15. Pentru arborele orientat din exemplul 3.1.13. ordinea de vizitare a vîrfurilor este: 5,9,10,11,12,13,6,7,2,3,14,15,16,8,4,1. Pentru arbori reprezentaţi prin structuri dinamice de date, implementarea parcurgerii în A-postordine poate fi obţinută pe baza următoarei funcţii recursive. Parametrul de intrare al funcţiei A_postordine reprezintă rădăcina arborelui curent în momentul apelului. void A_postordine (nod R) { if (R) { for(i=0;ileg[i]); vizit (R); } }
Observaţie Parcurgerile în A-preordine şi A-postordine sînt variante de parcurgeri în adîncime (variante ale metodei DF). Ambele metode consideră prioritare vîrfurile aflate la distanţă maximă faţă de rădăcina arborelui iniţial. Parcurgerea pe niveluri Parcurgerea unui arbore orientat pe niveluri constă în vizitarea vîrfurilor sale în ordinea crescătoare a distanţelor faţă de rădăcină. Exemplu 3.1.16. Pentru arborele definit în exemplul 3.1.13., prin aplicarea parcurgerii pe niveluri, rezultă următoarea ordine de vizitare a nodurilor, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16. Ca şi în cazul metodei BF, implementarea parcurgerii pe niveluri este bazată pe utilizarea unei structuri de coadă C. La momentul iniţial rădăcina arborelui este inserată în C.
44
Metode de programare
Atîta timp cît timp coada este nevidă, este preluat cu ştergere un vîrf din C, este vizitat şi sînt introduşi în coadă descendenţii săi. Calculul este încheiat cînd C=Ø. În cazul reprezentării FIU-FRATE a arborelui de traversat, parcurgerea pe niveluri poate fi implementată prin următoarea funcţie. void parcurgere_pe_niveluri(nod R,int FIU[],int FRATE[],int n) { ptcoada C=NULL;push(C,R); while (C) { pop(C,v); VIZIT(v); v=FIU[v]; while (v){ push(C,v); v=FRATE[v]; } } }
Observaţie Funcţiile push şi pop implementează inserarea unuei celule în coadă, respectiv extragerea unui element al cozii. Exemplu 3.1.17. Pentru arborele de la exemplul 3.1.13., evoluţia algoritmului este,
C t t=1
1
t=2
2
3
4
t=3
3
4
5
6
t=4
4
5
6
7
t=5
5
6
7
8
t=6
6
7
8
t=7
7
8
9
t=8
8
8
9
7
1
1
0
1
1
1
1
0
1
2
1 2
1 3
1 3
44
Algoritmi și tehnici de programare
t=9
t=10
t=11
t=12
t=13
t=14
t=15
t=16
45
9
1
1
1
1
0
1
2
3
1
1
1
1
1
0
1
2
3
4
1
1
1
1
1
1
2
3
4
5
1
1
1
1
1
2
3
4
5
6
1
1
1
1
3
4
5
6
1
1
1
4
5
6
1
1
5
6
1 4 1 5
1 5
1 6
1 6
1 6
1 5
t=17
deci vîrfurile sînt vizitate în ordinea: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16. Observaţie Metoda BF pentru parcurgerea grafurilor este o generalizare a tehnicii de parcurgere pe niveluri a arborilor orientaţi. O alternativă de implementare a parcurgerii pe niveluri poate fi descrisă prin intermediul funcţiilor recursive frati şi parc. Coada C este o variabilă globală şi este iniţializată cu rădăcina arborelui. Parcurgerea este realizată prin apelul parc(C). void frati(v) {if (v){push(C,v); fraţi(FRATE[v]); } } void parc() {if (C){pop(C,v);VIZIT(v); frati(FIU[v]); parc(); } }
46
Metode de programare
3.1.3. Arbori parţiali. Algoritmul Kruskal Definiţia 3.1.10. Fie G un graf. Subgraful parţial H este un arbore parţial al lui G dacă H este graf arbore. Definiţia 3.1.11. Fie G=(V,E,w) un graf ponderat conex.Dacă T=(V,E0) este un arbore parţial al grafului G’=(V,E), ponderea arborelui T, notată W(T), este definită prin w( e ) . W(T)=
eE0
Exemplu 3.1.18. Pentru graful ponderat
1 4 2
8
6
2
9
1
4
3
2
5
12
3
T este un arbore parţial de pondere 32.
1 4
2
3
2
6 8
4
5
9 3
Definiţia 3.1.12. Arborele parţial T0T(G) este arbore parţial minim pentru G dacă W(T0)=min{W(T); TT(G)}, unde T(G) este mulţimea arborilor parţiali corespunzători grafului G. Observaţie Dacă G este graf finit, atunci T(G) este o mulţime finită, deci orice graf finit ponderat şi conex are cel puţin un arbore parţial minim. În continuare este prezentat algoritmul Kruskal pentru determinarea unui arbore parţial minim al unui graf ponderat conex G=(V,E,w). Pas 1: i=1; E0= Pas 2: Determină R={e/eE \ Ei-1 astfel încît graful (V,Ei-1 {e}) este aciclic} Dacă R=, atunci stop; altfel, selectează eiR cu w(ei)=min{w(e), eR}; Ei=Ei{e } 1 i
46
Algoritmi și tehnici de programare
47
Pas 3: i=i+1 şi reia pasul 2. Arborele parţial de cost minim al grafului G este (V,Ei-1). Pentru implementarea algoritmului Kruskal, graful conex ponderat este reprezentat sub formă tabelară, muchiile fiind ordonate crescător după ponderi. Muchiile selectate de algoritm pot fi menţinute de asemenea într-o structură tabelară, sau doar marcate ca fiind incluse în mulţimea de muchii din arborele parţial minim a cărui construcţie este dorită. În varianta prezentată în continuare muchiile selectate sînt afişate. Verificarea condiţiei ca muchia selectată să nu formeze nici un ciclu cu muchiile selectate la etapele precedente este realizată prin utilizarea un vector TATA, definit astfel. Pentru fiecare vîrf i (vîrfurile grafului fiind numerotate de la 1 la n, unde n este numărul de noduri ale grafului), componenta TATA [i] este predecesorul său în arborele care conţine vîrful i construit pînă la momentul curent dacă i nu este rădăcina acelui arbore, respectiv TATA[i] este egal cu –numărul de vîrfuri ale arborelui de rădăcină i, în caz contrar. Componentele vectorului TATA sînt iniţializate cu valoarea -1. Calculul care realizează adăugarea unei noi muchii poate fi descris astfel. Este determinată o muchie de cost minim e=v1v2 care nu a fost selectată anterior. Dacă vîrfurile v1 şi v2 nu aparţin aceluiaşi arbore, atunci proprietatea de aciclicitate este îndeplinită şi muchia e este adăugată la structura curentă. Adăugarea muchiei e selectate este realizată prin reunirea arborilor din care fac parte v1 şi v2 de rădăcini r1, respectiv r2, astfel: dacă TATA[r1] #include int radacina(int v,int *tata) { int u=v; while(tata[u]>=0) u=tata[u]; return u; } int kruskal(int a[][3],int nm, int nv) { int tata[50],i,j; int c=0; for(i=0;i %i cost %i\n",v1+1,v2+1,a[j][2]); i++; } } return c; } void main() { clrscr();
48
Metode de programare
int nv,nm, a[100][3]; printf("Numarul de varfuri:");scanf("%i",&nv); printf("Numarul de muchii");scanf("%i",&nm); printf("Matricea de reprezentare\n"); for(int i=0;i
Exemplu 3.1.19. Evoluţia determinată de program pentru graful 1 4
2
2
2
8
6
8
1
3
9
4 4
3
2 2 1 1 5 A 3 1 4 5 3
3 4 6 5 4 2 6 6 6
1 2 2 3 4 4 8 8 9
este: i, j după cea de-a t-a iteraţie
muchia selectată
t=0
TATA
Costul
(-1,-1,-1,-1,-1,-1)
t=1,i=0,j=0
(2,3)
(-1,-2,2,-1,-1,-1)
1
t=2,i=1,j=1
(2,4)
(-1,-3,2,2,-1,-1)
2
t=3,i=2,j=2
(1,6)
(-2,-3,2,2,-1,1)
2
t=4,i=3,j=3
(1,5)
(-3,-3,2,2,1,1)
3
t=5,i=4,j=4 t=6,i=4,j=5
(-3,-3,2,2,1,1) (1,2)
(-5,1,1,2,1,1)
MUCHIILE ARBORELUI MINIM: {(2,3),(2,4),(1,6),(1,5),(1,2)}
4 COSTUL: 12
48
Algoritmi și tehnici de programare
49
3.2. Arbori binari 3.2.1. Reprezentarea arborilor binari. Modalităţi de parcurgere Definiţia 3.2.1. Un arbore binar este un arbore orientat cu proprietatea că pentru orice vîrf v, od(v)2. Dacă od(v)=2, cei doi descendenţi sînt desemnaţi ca descendent stîng (fiu stînga) respectiv descendent drept (fiu dreapta). Pentru vîrfurile cu od(v)=1, unicul descendent este specificat fie ca fiu stînga, fie ca fiu dreapta. Definiţia 3.1.2. Se numeşte nod terminal orice vîrf v al arborelui cu od(v)=0. În caz contrar nodul v este neterminal. Reprezentarea unui arbore binar este realizată printr-o structură arborescentă. Pentru fiecare nod N al arborelui binar sînt memorate informaţia asociată lui N şi legăturile către descendenţii lui. Absenţa unui descendent este reprezentată prin NULL. identificator legătură fiu legătură fiu nod stîng drept Definiţia 3.2.3. Fie T=(V,E) un arbore binar cu rădăcina R. Subarborele stîng al lui T este ST=(V\{R},E\{RS}), unde S este fiul stînga al rădăcinii. Subarborele drept al lui T este DT=(V\{R},E\{RD}), unde D este fiul dreapta al rădăcinii. Exemplu 3.2.1. Pentru arborele binar,
1 2
3
4
5 8
6
7
9
10
subarborii rădăcinii sînt:
2
3
4
6
5 8
Subarbore stîng
9
7
10 Subarbore drept
În plus faţă de metodele A-preordine, A-postordine şi pe niveluri, parcurgerile în preordine (RSD), inordine (SRD) şi respectiv postordine (SDR) sînt special considerate pentru arbori binari şi au multiple aplicaţii. Regula de vizitare pentru aceste tipuri de parcurgere revine la parcurgerea subarborelui stîng şi parcurgerea subarborelui drept corespunzători vîrfului curent. La momentul iniţial vîrful curent este rădăcina arborelui. Diferenţa dintre cele trei tipuri de parcurgere este dată de momentul în care devine vizitat fiecare vîrf al arborelui. În parcurgerea RSD (rădăcină-subarbore stîng-subarbore drept), fiecare vîrf al arborelui este vizitat în momentul în care este vîrf curent; în parcurgerea SRD, vizitarea vîrfului curent R este efectuată după ce a fost parcurs subarborele stîng al lui R, respectiv în parcurgerea SDR vizitarea fiecărui vîrf este efectuată după ce au fost parcurşi subarborii aferenţi lui.
50
Metode de programare
Exemplu 3.2.2. Pentru arborele de la exemplul 3.2.1., secvenţele de vîrfuri rezultate prin aplicarea parcurgerilor RSD, SRD, SDR sînt: - preordine: 1,2,4,8,5,3,6,9,10,7 - inordine: 4,8,2,5,1,9,6,10,3,7 - postordine: 8,4,5,2,9,10,6,7,3,1.
3.2.2. Arbori de sortare Definiţia 3.2.4. Un arbore de sortare este un arbore binar cu următoarele proprietăţi, - fiecărui nod i al arborelui îi este ataşată o informaţie INF(i) dintr-o mulţime ordonată de valori; - pentru fiecare nod i, INF(i) este mai mare decît INF(j), pentru toate nodurile j din subarborele stîng al arborelui cu rădăcină i; - pentru fiecare nod i, INF(i) este mai mică decît INF(j), pentru toate nodurile j din subarborele drept al arborelui cu rădăcină i; - pentru orice vîrfuri i şi j daca ij atunci INF(i)INF(j). Exemplu 3.2.3. Arborele binar
50
30 10
70 40
20
90 80
este arbore de sortare. Operaţiile primitive asupra arborilor de sortare sînt inserarea unui nod, ştergerea unui nod şi parcurgerea arborelui (în preordine, inordine sau postordine). Inserarea şi ştergerea de noduri aplicate unui arbore de sortare trebuie realizate astfel încît arborele rezultat să fie de asemenea arbore de sortare. Observaţie Parcurgerea în inordine a unui arbore de sortare determină obţinerea secvenţei informaţiilor asociate vîrfurilor arborelui în ordine crescătoare. Inserarea unui nod într-un arbore de sortare Algoritmul de inserare a unei informaţii nr în arborele de sortare de rădăcină rad este recursiv şi constă în efectuarea următoarelor operaţii: vîrful curent v la momentul iniţial este rădăcina arborelui; dacă arborele de rădăcină v este vid, este generat arborele cu un singur nod, cu informaţia ataşată nr; altfel: - dacă informaţia ataşată nodului v este mai mare decît nr, atunci vîrf curent devine fiul stînga al lui v; - dacă informaţia ataşată nodului v este egală cu nr, atunci stop; - dacă informaţia ataşată nodului v este mai mică decît nr, atunci vîrf curent devine fiul dreapta al lui v.
50
Algoritmi și tehnici de programare
51
Exemplu 3.2.4. Aplicarea algoritmul descris pentru inserarea informaţiei 55 în arborele de sortare din exemplul 3.2.3. determină următoarele operaţii, INF(v)=50; 50<55, inserează în subarborele cu rădăcina avînd informaţia ataşată 70. INF(v)=70; 70>55, inserează în subarborele stîng cu rădăcina NULL. Este creat nodul cu informaţie 55, fiu stîng al nodului de informaţie 70. Arborele rezultat este
50
30 10
70 40
20
90
55 80
Ştergerea unei informaţii dintr-un arbore de sortare Algoritmul pentru ştergerea unei informaţii nr din arborele de sortare de rădăcină rad este recursiv şi poate fi descris astfel. Vîrful curent v la momentul iniţial este rădăcina arborelui. 1. dacă arborele este vid atunci stop; 2. altfel a) dacă informaţia ataşată nodului v este mai mare decît nr, atunci vîrful curent devine fiul stînga al lui v; b) dacă informaţia ataşată nodului v este mai mică decît nr, vîrful curent devine fiul dreapta al lui v; c) dacă INF(v)=nr atunci: c1) dacă subarborele stîng este vid, atunci adresa vîrfului v este memorată într-o celulă suplimentară aux, v devine fiul dreapta al lui v, iar celula aux este eliberată din memorie; c2) dacă subarborele stîng este nevid atunci se determină cel mai mare element din subarborele stîng; c2.1) dacă fiul stînga al lui v nu are subarbore drept, atunci informaţia ataşată fiului stînga se transferă în vîrful curent, iar fiul stînga este înlocuit cu fiul său stînga şi este eliberată memoria corespunzătoare celulei v->fius; c2.2) altfel, se transferă în rădăcină informaţia ataşată ultimului nod p determinat la c2), nodul p este înlocuit cu fiul său stîng şi celula corespunzătoare lui p este eliberată din memorie. Exemplu 3.2.5. Ştergerea informaţiei 70 din arborele de sortare din exemplul 3.2.4. este realizată astfel: 70>50, decide ştergerea din subarborele drept 70=70, decide ştergerea din arborele curent: rădăcina etichetată cu 70; există subarbore stîng iar acesta nu are subarbore drept- nodul cu informaţie 70 este etichetat cu 55, iar p este înlocuit cu subarborele său stîng (vid). Arborele rezultat
52
Metode de programare
50
30 10
55 40
20
90 80
este arbore de sortare. Observaţie Punctul c) de la pasul 2 al algoritmului de eliminare a unei informaţii dintr-un arbore de sortare poate fi înlocuit cu: c) dacă INF(v)=nr atunci: c1) dacă subarborele drept este vid, atunci adresa vîrfului v este memorată într-o celulă suplimentară aux, v devine fiul stînga al lui v, iar celula aux este eliberată din memorie; c2) dacă subarborele drept este nevid atunci se determină cel mai mic element din subarborele drept, altfel c2.1.) dacă fiul dreapta al lui v nu are subarbore stîng, atunci informaţia ataşată fiului dreapta este transferată în vîrful curent, iar fiul dreapta este înlocuit cu fiul său dreapta şi este eliberată memoria corespunzătoare celulei v->fiud. c2.2) altfel, se transferă în rădăcină informaţia ataşată ultimului nod p determinat la c2), nodul p este înlocuit cu fiul său dreapta şi celula corespunzătoare lui p este eliberată din memorie. În următoarea sursă C sînt implementaţi algoritmii de adăugare şi ştergere în arbori de sortare. #include<stdio.h> #include #include typedef struct nod{ int inf; struct nod *l,*r; } arb, *arbore; void inserare(arbore *radacina,int info) { if(*radacina==NULL){ arbore nou; nou=(arbore)malloc(sizeof(arb)); nou->inf=info; nou->l=nou->r=NULL; *radacina=nou; } else if((*radacina)->inf>info) inserare(&((*radacina)->l),info); else if((*radacina)->infr),info); } int extragere(arbore *radacina,int info) {
52
Algoritmi și tehnici de programare if(*radacina==NULL) return 0; else if((*radacina)->inf>info) return extragere(&((*radacina)->l),info); else if((*radacina)->infr),info); else{ if((*radacina)->l==NULL){ arbore aux=*radacina; *radacina=(*radacina)->r; free(aux); } else{ arbore p,p1; for(p=(*radacina)->l;p->r;p1=p,p=p->r); if(((*radacina)->l)->r==NULL){ (*radacina)->inf=p->inf; (*radacina)->l=p->l; free(p); } else{ (*radacina)->inf=p->inf; arbore aux=p; p1->r=p->l; free(aux); } } return 1; } } void srd(arbore radacina) { if(radacina){ srd(radacina->l); printf("%i ",radacina->inf); srd(radacina->r); } } void main() { clrscr(); int n,info; arbore radacina=NULL; printf("Numarul de noduri:"); scanf("%i",&n); printf("Introduceti informatiile\n"); for(int i=0;i
53
54
Metode de programare
3.2.3. Arbori de structură Expresiile aritmetice în care intervin numai operatori binari pot fi reprezentate prin intermediul arborilor binari în care fiecare nod neterminal are doi fii. Definiţia 3.2.5. Un arbore de structură are vîrfurile etichetate astfel: - fiecare nod neterminal este etichetat cu un simbol corespunzător unuia dintre operatori; - fiecare nod terminal este etichetat cu un operand. Construcţia arborelui de structură corespunzător unei expresii aritmetice date se realizează pe baza parantezării existente în expresie şi a priorităţilor convenţional asociate operatorilor (ordinea operaţiilor) astfel încît rădăcina fiecărui subarbore este etichetată cu operatorul care se execută ultimul în evaluarea subexpresiei corespunzătoare acelui subarbore. Exemplu 3.2.6. Pentru expresia matematică (a+b)*(c-d)+e/g, arborele de structură corespunzător este
+
/
* + a
b
c
e
g
d
Construcţia arborelui de structură pentru o expresie s este realizată în două etape: 1. ataşarea de priorităţi operatorilor şi operanzilor; priorităţile ataşate permit eliminarea parantezelor fără ca semnificaţia expresiei să se modifice; 2. construcţia propriu-zisă. Prima etapă este realizată astfel: prioritatea iniţială a operatorilor ‘+’,’-‘ este 1 (dacă expresia nu conţine paranteze atunci în construcţie aceşti operatori vor fi primii luaţi în considerare în ordinea de la dreapta la stînga); - prioritatea iniţială a operatorilor ‘/’,’*‘ este 10 (dacă expresia nu conţine paranteze, aceştia sînt consideraţi după operatorii de prioritate 1 în ordinea de la dreapta la stînga); - prioritatea fiecărui operator este incrementată cu valoarea 10 pentru fiecare pereche de paranteze în interiorul cărora se află; - prioritatea ataşată fiecărui operand este MAXINT. După stabilirea sistemului de priorităţi sînt eliminate parantezele din expresie, ordinea de efectuare a operaţiilor în cadrul expresiei fiind indicată de vectorul de priorităţi ataşat. Construcţia arborelui de structură pe baza expresiei s din care au fost eliminate parantezele şi a vectorului de priorităţi, poate fi realizează recursiv în modul următor (la momentul iniţial expresia curentă este expresia dată): - pentru expresia curentă se determină operatorul/operandul de prioritate minimă care se ataşează ca etichetă a rădăcinii r a subarborelui de structură corespunzător ei; fie i poziţia acestuia în cadrul expresiei; -
54
Algoritmi și tehnici de programare
-
55
dacă expresia are un singur simbol, atunci r->fius=r->fiud=NULL; altfel, se consideră subexpresiile s1 şi s2, constînd din simbolurile de pe poziţiile 0 pînă la i-1 şi respectiv i+1 pînă la lungimea şirului s.; arborii de structură corespunzători subexpresiilor s1 şi s2 se ataşează ca subarbore stîng, respectiv subarbore drept vîrfului r.
Exemplu 3.2.7. Etapele calculului sistemului de priorităţi şi al arborelui de structură pentru expresia de la exemplul 3.2.6. pot fi descrise astfel, Dim 1 2 3 3 4 4 5 6 7 7 8 9 10 11
vectorul prioritate (MAXINT) (MAXINT,11) (MAXINT,11,MAXINT) (MAXINT,11,MAXINT) (MAXINT,11,MAXINT,10) (MAXINT,11,MAXINT,10) (MAXINT,11,MAXINT,10,MAXINT) (MAXINT,11,MAXINT,10,MAXINT,11) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT,1) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT,1,MAXINT) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT,1,MAXINT,10) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT,1,MAXINT,10,MAXINT)
După eliminarea parantezelor, expresia rezultată este s=a+b*c-d+e/g. Arborele de structură este construit astfel:
+ +
în construcţie
* în construcţie
în construcţie
în construcţie
în construcţie +
+
* + în construcţie
în construcţie
*
în construcţie în construcţie
+ a
în construcţie
în construcţie
în construcţie
56
Metode de programare
+
în construcţie
*
în construcţie
*
în construcţie
+ a
+
+ a
b
în construcţie
b
+
+ a
+
în construcţie
*
+
-
în construcţie a
c
în construcţie
*
b
în construcţie
b
c
d
+
/
* + a
b
în construcţie
în construcţie
d
c
+
/
* + a
e
b
c
în construcţie
d
56
Algoritmi și tehnici de programare
57
+
/
* + a
b
c
e
g
d
Observaţie Construcţia arborelui de structură poate fi realizată în ipoteza în care expresia este corectă. Definiţia 3.2.6. Se numeşte forma poloneză directă a unei expresii, expresia rezultată în urma parcurgerii RSD a arborelui de structură. Se numeşte forma poloneză inversă a unei expresii, expresia rezultată în urma parcurgerii SDR a arborelui de structură. Exemplu 3.2.8. Pentru expresia considerată la exemplul 3.2.7., forma poloneză directă este +*+abcd/eg. Forma poloneză inversă a expresiei date este ab+cd-*eg/+. Observaţie Parcurgerea arborelui în inordine determină secvenţa de simboluri rezultată prin eliminarea parantezelor din expresia dată. Restaurarea unei forme parantezate poate fi realizată printr-o parcurgere SRD şi anume în modul următor. La momentul iniţial vîrful curent este rădăcina arborelui de structură. Dacă vîrful curent v nu este vîrf terminal, atunci se generează (s1) eticheta(v)(s2), unde eticheta(v) este operatorul etichetă a vîrfului, s1 este secvenţa rezultată prin traversarea SRD a subarborelui stîng, s2 este secvenţa rezultată prin traversarea SRD a subarborelui drept. Dacă v este vîrf terminal atunci este generată secvenţa eticheta(v). Evaluarea expresiilor aritmetice pe baza arborilor de structură Traversarea SRD a arborelui de structură ataşat unei expresii aritmetice permite evaluarea expresiei pentru valorile curente corespunzătoare variabilelor. Evaluarea poate fi efectuată în mod recursiv astfel. La momentul iniţial vîrful curent este rădăcina arborelui. Dacă v este vîrf curent atunci noua informaţie asociată lui v este: - val(eticheta(v)), dacă v este vîrf terminal; - val(s1)eticheta(v)val(s2), dacă v este neterminal, unde val(s1), val(s2) sînt valorile rezultate prin evaluările subarborilor stîng şi respectiv drept ai lui v, val(eticheta(v)) este valoarea curentă a variabilei, dacă eticheta lui v este variabilă, respectiv valoarea constantei, dacă eticheta lui v este o constantă. Exemplu 3.2.9. Prin aplicarea metodei de evaluare descrise pentru a=3, b=2, c=5, d=2, e=6 şi g=2, obţinem:
58
Metode de programare
18
3
15 5 3
3 2
5
6
2
2
Construcţia arborelui de structură asociat unei expresii şi evaluarea expresiei pentru valori date ale operanzilor pot fi implementate prin intermediul următoarei surse C. #include<stdio.h> #include #include #include #include<string.h> #include<math.h> typedef struct nod{ char inf; float v; struct nod *l,*r; } arb, *arbore; void prioritati(char *s, int *prioritate) { int i,j,dim; //stabilirea prioritatilor for(i=j=dim=0;i<strlen(s);i++) switch(s[i]){ case ')':j-=10;break; case '(':j+=10;break; case '+':{prioritate[dim]=j+1;dim++;break;} case '-':{prioritate[dim]=j+1;dim++;break;} case '*':{prioritate[dim]=j+10;dim++;break;} case '/':{prioritate[dim]=j+10;dim++;break;} default:{prioritate[dim]=MAXINT;dim++;break;} } //eliminarea parantezelor for(i=0;i<strlen(s);) if((s[i]==')')||(s[i]=='(')){ for(j=i+1;j<strlen(s);j++)s[j-1]=s[j]; s[strlen(s)-1]='\0';} else i++; } void cr_arb_str(arbore *rad, unsigned p, unsigned u, char *s,int *pri) { int min=pri[p]; int poz=p; for(int i=p+1;i<=u;i++) if(min>pri[i]){min=pri[i];poz=i;} (*rad)=(arbore)malloc(sizeof(arb)); (*rad)->inf=s[poz]; if(p==u) (*rad)->l=(*rad)->r=NULL; else{
58
Algoritmi și tehnici de programare cr_arb_str(&((*rad)->l),p,poz-1,s,pri); cr_arb_str(&((*rad)->r),poz+1,u,s,pri); } } void forma_poloneza(arbore rad) { if(rad){ printf("%c",rad->inf); forma_poloneza(rad->l); forma_poloneza(rad->r); } } float eval(arbore rad) { char s[1]; if(rad){ if((rad->r==rad->l)&&(rad->l==NULL))return rad->v; else{ switch (rad->inf){ case '+':rad->v=eval(rad->l)+eval(rad->r);break; case '-':rad->v=eval(rad->l)-eval(rad->r);break; case '*':rad->v=eval(rad->l)*eval(rad->r);break; case '/':rad->v=eval(rad->l)/eval(rad->r);break; } return rad->v; } } } void atribuie_arbore(arbore rad) { if(rad){ if((rad->r==rad->l)&&(rad->l==NULL)){ printf("%c =",rad->inf); float t; scanf("%f",&t); rad->v=t; } else {atribuie_arbore(rad->l); atribuie_arbore(rad->r); } } } void main() { clrscr(); char s[100]; int p[100]; arbore radacina=NULL; printf("Expresia:"); scanf("%s",&s); prioritati(s,p); int n=strlen(s); cr_arb_str(&radacina,0,n-1,s,p); printf("\nForma poloneza inversa "); forma_poloneza(radacina); printf("\n Valori pentru varabile\n"); atribuie_arbore(radacina); printf("\nEvaluarea: %7.3f",eval(radacina)); getch(); }
59
60
Metode de programare
Bibliografie 1. [Aho, Hop şa] Aho A., Hopcroft J., Ullman J., Data Structures and Algorithms, Addison-Wesley, 1983 2. [Bras, Brat] Brassard G., Bratley P., Algoritmics: Theory and Practice, Prentice-Hall, 1988 3. [Cor, Lei şa] Cormen T., Leiserson C., Rivest R., Introduction to Algorithms, MIT Press, sixteenth printing, 1996 4. [Gon] Gonnet G.H., Handbook of Algorithms and Date Structures, Addison-Wesley, 1984 5. [Hor] Horowitz E., Sahni S., Fundamentals of Computer Algorithms, Computer Science Press, 1978 6. [Knu] Knuth D., Fundamental Algorithms, vol 1 of The Art of Computer Programming, Addison-Wesley, 1973 7. [Knu] Knuth D., Sorting and Searching, vol 3 of The Art of Computer Programming, Addison-Wesley, 1973 8. [Man] Manmber U., Introduction to Algorithms: A Creative Approach, AddisonWesley, 1989 9. [Pop, Geo şa] Popovici Ct., Georgescu H., State L., Bazele informaticii, vol 1, Tip. Universităţii din Bucureşti, 1990 10. [Tom] Tomescu I.., Probleme de combinatorică şi teoria grafurilor, Editura Didactică şi Pedagogică, Bucureşti, 1981 11. [Tud] Tudor S., Tehnici de programare, Ed. Teora, 1994 12. [Wil] Wilf H., Algorithms and Complexity, Prentice-Hall, 1986 13. [Negrescu, 1994] Liviu Negrescu, Limbajele C şi C++ pentru începători, Editura Microinfomatica, Cluj-Napoca, 1994 14. [Smeureanu, 1995] Ion Smeureanu, Ion Ivan, Marian Dârdală, Limbajul C/C++ prin exemple, Editura Cison, Bucureşti 1995 15. [Ghilic, 2003] Bogdan Ghilic-Micu, Ion Gh. Roşca, Constantin Apostol, Marian Stoica, Cătălina Lucia Cocianu, Algoritmi în programare, Editura ASE, Bucureşti 2003
60
1
Algoritmi si tehnici de programare (partea a II-a)
Material suport elaborat de Prof.dr. Ion Gh. Roşca Prof.dr. Bogdan Ghilic-Micu Conf.dr. Cătălina Cocianu Conf.dr. Marian Stoica Lect.dr. Cristian Uscatu Asist. Marinela Mircea
Editura ASE, Bucureşti 2007
2
Metode de programare
1. Introducere_______________________________________________3 2. Grafuri 3 2.1. Definiţii şi reprezentări ale grafurilor 2.1.1 Moduri de reprezentare a grafurilor 2.1.2. Reprezentarea matriceală 2.1.3. Reprezentarea tabelară 2.1.4. Reprezentarea prin intermediul listelor 2.2. Modalităţi de parcurgere a grafurilor 1.2.1. Metoda de parcurgere BF (Breadth First) 1.2.2. Metoda de parcurgere DF (Depth First) 1.2.3. Parcurgerea în adîncime în varianta generalizată – DFG 2.3. Drumuri în grafuri. Conexitate 2.3.1 Drumuri; definiţii 2.3.2. Matricea existenţei drumurilor; algoritmul Roy-Warshall 2.3.3. Componente conexe ale unui graf 2.3.4. Drumuri de cost minim 2.4. Circuite şi cicluri în grafuri şi în digrafuri
3
3. Structuri arborescente
37
3.1. Grafuri de tip arbore 3.1.1. Definiţii şi caracterizări ale grafurilor arbori 3.1.2. Reprezentări şi parcurgeri ale arborilor orientaţi 3.1.3. Arbori parţiali. Algoritmul Kruskal 3.2. Arbori binari 3.2.1. Reprezentarea arborilor binari. Modalităţi de parcurgere 3.2.2. Arbori de sortare 3.2.3. Arbori de structură
37
Bibliografie
_62
7
21
31
49
2
Algoritmi și tehnici de programare
3
1. Introducere
Grafurile sînt structuri de date cu aplicaţii în multe domenii ale informaticii, algoritmii pentru reprezentarea şi prelucrarea grafurilor fiind consideraţi fundamentali în acest domeniu. În subcapitolul 2.1 sînt prezentate principalele noţiuni ale domeniului, precum şi modalităţile uzuale de reprezentare a structurii de graf. În continuare sînt descrise tehnicile de parcurgere a grafurilor în lăţime şi în adîncime. Traversarea în adîncime a grafurilor determină obţinerea unei clasificări a muchiilor, în funcţie de care pot fi derivate diferite proprietăţi ale grafurilor. Verificarea conexităţii şi calculul drumurilor în grafuri sînt tratate în subcapitolul 2.3. În finalul capitolului este studiată problema determinării circuitelor şi ciclurilor în grafuri şi digrafuri.
2. Grafuri 2.1. Definiţii şi reprezentări ale grafurilor Definiţia 2.1.1. Se numeşte graf sau graf neorientat o structură G=(V,E), unde V este o mulţime nevidă iar E este o submulţime posibil vidă a mulţimii perechilor neordonate cu componente distincte din V. Elementele mulţimii V se numesc vîrfuri, iar obiectele mulţimii E se numesc muchii. Dacă e E, e (u,v) not. uv , vîrfurile u şi v se numesc extremităţi ale lui e, muchia e fiind determinată de vîrfurile u şi v. Dacă e=uv E se spune că vîrfurile u, v sînt incidente cu muchia e. Definiţia 2.1.2. Fie G=(V,E) graf. Vîrfurile u, v sînt adiacente în G dacă uv E. Definiţia 2.1.3. Graful G=(V,E) este graf finit, dacă V este o mulţime finită. În cadrul acestui capitol vor fi considerate în exclusivitate grafurile finite, chiar dacă acest lucru nu va fi precizat în mod explicit. Definiţia 2.1.4. Fie Gi =(V i,Ei), i=1,2 grafuri. G2 este un subgraf al grafului G1 dacă V2 V1 şi E2 E1 . G2 este este un graf parţial al lui G1 dacă V2=V1 şi G2 este subgraf al lui G1. Definiţia 2.1.5. Un digraf este o structură D=(V,E), unde V este o mulţime nevidă de vîrfuri, iar E este o mulţime posibil vidă de perechi ordonate cu componente elemente distincte din V. Elementele mulţimii E sînt numite arce sau muchii ordonate. Un graf direcţionat este o structură D=(V,E), unde V este o mulţime nevidă de vîrfuri, iar E este o mulţime posibil vidă de perechi ordonate cu componente elemente din V, nu neapărat distincte. Evident, orice digraf este un graf direcţionat. Terminologia utilizată relativ la digrafuri este similară celei corespunzătoare grafurilor. În continuare vom referi prin muchie şi elementele mulţimii E a unui graf direcţionat, în situaţia în care este tratat cazul unui graf oarecare (neorientat sau direcţionat). Definiţia 2.1.6. Se numeşte graf ponderat o structură (V,E,W), unde G=(V,E) este graf şi W este o funcţie definită prin W : E 0 , . Funcţia W este numită pondere şi ea asociază
4
Metode de programare
fiecărei muchii a grafului un cost/cîştig al parcurgerii ei. Definiţia 2.1.7. Fie G=(V,E) un graf, u,vV. Secvenţa de vîrfuri :u0,u1,..,un este un u-v drum dacă u0=u, un=v, uiui+1E pentru toţi i, 0 i n . Definiţia 2.1.8. Fie G=(V,E) un graf. Elementul vV se numeşte vîrf izolat dacă, pentru orice e E, u nu este incident cu e.
2.1.1 Moduri de reprezentare a grafurilor Cea mai simplă reprezentare a unui graf este cea intuitivă, grafică; fiecare vîrf este figurat printr-un punct, respectiv muchiile sînt reprezentate prin segmentele de dreaptă, orientate (în cazul digrafurilor) sau nu şi etichetate (în cazul grafurilor ponderate) sau nu, avînd ca extremităţi punctele corespunzătoare vîrfurilor care o determină Exemple 2.1.1. Fie G=(V,E) graf, cu V={1,2,3,4,5,6}, E={(1,2),(1,3),(2,5),(3,5),(5,6)}. O posibilă reprezentare grafică este,
1 2 4
6
5
3
2.1.2. Fie D=(V,E) digraf, V={1,…,5}, E={(1,2), (1,3), (1,5), (2,5), (3,5), (4,1), (5,4)}. Digraful poate fi reprezentat grafic astfel,
1
2
4
3 5 2.1.3. Fie D=(V,E) graf direcţionat, V={1,2,3,4,5}, E={(1,2), (1,3), (1,5) (2,5), (3,5), (4,4)}. Reprezentarea grafică este,
4
Algoritmi și tehnici de programare
5
1 4
2 3
5
2.1.4. Fie G=(V,E,W) graf ponderat, V={1,2,3,4}, E={(1,2), (1,3), (1,4), (2,3), (2,4)}, W((1,2))=5, W((1,3))=1, W((1,4))=7, W((2,3))=4, W((2,4))=2. O posibilă reprezentare grafică este:
1
5
1
2
4
3
2 7
4 În scopul reprezentării grafurilor în memoria calculatorului sînt utilizate în general următoarele structuri de date. 2.1.2. Reprezentarea matriceală Grafurile, digrafurile şi grafurile direcţionate pot fi reprezentate prin matricea de adiacenţă. Dacă G=(V,E ) este graf, digraf sau graf direcţionat cu V n , atunci matricea de adiacenţă A Mnxn({0,1}) are componentele,
1, dacă vi ,v j E aij , 0 , altfel
unde vi, vj reprezintă cel de-al i-lea, respectiv cel de-al j-lea nod din V. În cazul unui graf neorientat, matricea de adiacenţă este simetrică. Exemplu 2.1.5. Graful din exemplul 2.1.1, digraful din exemplul 2.1.2 şi graful direcţionat din exemplul 2.1.3 sînt reprezentate prin matricele de adiacenţă, 0 1 1 A 0 0 0
1 0 0 0 1 0
1 0 0 0 1 0
0 0 0 0 0 0
0 1 1 0 0 1
0 0 0 0 0 (2.1.1), A 0 0 1 1 0 0
1 0 0 0 0
1 0 0 0 0
0 0 0 0 1
1 0 1 0 1 (2.1.2), A 0 0 0 0 0
1 0 0 0 0
1 0 0 0 0
0 0 0 1 0
1 1 1 (2.1.3) 0 0
În cazul grafurilor ponderate, reprezentarea poate fi realizată prin matricea ponderilor. Dacă G=(V,E,W) este graf ponderat, V n , W Mnxn((0, )) are componentele,
6
Metode de programare
W ( vi ,v j ), dacă vi ,v j E wi , j , altfel
unde vi, vj reprezintă cel de-al i-lea, respectiv cel de-al j-lea nod din V, 0 , dacă ponderea are semnificaţia de cîştig, respectiv în cazul în care se doreşte reprezentarea costurilor ca ponderi ale grafului. Exemplu 2.1.6. Presupunînd că ponderile reprezintă costuri, matricea de reprezentare a grafului
5 din exemplul 2.1.4. este W 1 7
5 1 7 4 2 . 4 2
2.1.3. Reprezentarea tabelară Reţinînd muchiile prin intermediul extremităţilor şi eventual valoarea ponderii ei, se obţine reprezentarea tabelară, mai economică din punctul de vedere al spaţiului de memorie necesar. Dacă graful conţine vîrfuri izolate atunci este necesară păstrarea acestora într-un vector suplimentar VS. Mulţimea muchiilor este reţinută într-o matrice A cu E linii şi c coloane, unde c=2 dacă graful nu este ponderat, altfel c=3. În primele două coloane se scriu perechile de vîrfuri ce determină muchiile, în cazul grafurilor ponderate cea de-a treia coloană conţine valoarea ponderii muchiei respective. Exemple 2.1.7. Graful din exemplul 2.1.1 poate fi reprezentat astfel, VS=(4),
1 1 A 2 3 5
2 3 5 5 6
1 1 1 2.1.8. Digraful din exemplul 2.1.2 este reprezentat prin A 2 3 4 5
2 3 5 5 . 5 1 4
6
Algoritmi și tehnici de programare
7
1 1 1 2.1.9. Graful direcţionat din 2.1.3. este reprezentat prin A 2 3 4
2 3 5 . 5 5 4
2.1.10. Graful ponderat din exemplul 2.1.4. nu are vîrfuri izolate, deci este reprezentat 1 1 prin intermediul matricei A 2 1 2
2 3 3 4 4
5 1 4 . 7 2
2.1.4. Reprezentarea prin intermediul listelor Această reprezentare permite utilizarea economică a spaţiului de memorare şi, în anumite cazuri, implementări mai eficiente pentru anumite clase de algoritmi. Vîrfurile grafului sînt memorate într-o listă, fiecare nod al listei N conţinînd o referinţă spre lista vecinilor vîrfului memorat ca informaţie în N. Dacă graful nu este ponderat, el poate fi reprezentat prin structura listă de liste, şi anume: nodurile grafului se trec într-o listă L_nod, fiecare celulă avînd structura, informaţie legătură vecini legătură nod următor unde, cîmpul informaţie conţine identificatorul nodului; legătură vecini reprezintă referinţa spre începutul listei vecinilor; legătură nod următor conţine adresa următoarei celule din lista L_nod. Un graf ponderat poate fi reprezentat în mod similar, cu diferenţa că, fiecare celulă din lista vecinilor conţine şi ponderea muchiei respective (muchia care are ca extremităţi vîrful referit prin identificatorul de nod din lista vecinilor şi respectiv vîrful indicat de informaţia acelei celule din L_nod ce conţine adresa primului element al listei vecinilor).
2.2. Modalităţi de parcurgere a grafurilor Modalitatea de vizitare a tuturor vîrfurilor grafului în care fiecare vîrf al grafului este vizitat o singură dată se numeşte parcurgere sau traversare. În acest paragraf sînt prezentate metodele de parcurgere BF (în lăţime), DF (în adîncime) şi metoda DF generalizată, notată DFG. Primele două metode de parcurgere sînt aplicate grafurilor neorientate respectiv grafurilor direcţionate şi presupun selectarea unui vîrf iniţial v0 şi identificarea acelor vîrfuri ale grafului v cu proprietatea că există cel puţin un drum de la vîrful iniţial către v. Grafurile cu proprietatea că oricare două vîrfuri sînt conectate printr-un drum se numesc grafuri conexe şi sînt prezentate în § 2.3. Dacă graful este conex, atunci prin aplicarea metodelor de parcurgere vor fi identificate toate vîrfurile grafului. Cele două modalităţi de parcurgere sînt prezentate în continuare în cazul grafurilor neorientate, extinderea la digrafuri şi grafuri direcţionate fiind imediată. Studiul proprietăţii metodei BF de a calcula distanţele minim între
8
Metode de programare
orice vîrf al grafului conectat de vîrful iniţial şi vîrful iniţial este prezentat în cazul grafurilor oarecare. Parcurgerea DFG presupune vizitarea tuturor vîrfurilor unui graf sau graf direcţionat prin aplicarea metodei DF tuturor vîrfurilor care, după ultima traversare DF, nu au fost încă vizitate.
2.2.1. Metoda de parcurgere BF (Breadth First) Traversarea BF presupune parcurgerea în lăţime a grafului, în sensul că, vîrfurile grafului sînt prelucrate în ordinea crescătoare a distanţelor la vîrful iniţial (teorema 2.2.1). Distanţa de la u la v, notată u ,v , este numărul de muchii ale unui cel mai scurt u-v drum. La momentul iniţial vîrf curent este v0. Deoarece vîrful curent la fiecare moment trebuie să fie unul dintre vîrfurile aflate la distanţă minimă de v0 se poate proceda în modul următor: iniţial lui v0 i se asociază valoarea 0, d v0 0 şi fiecărui vîrf v v0 i se asociază
valoarea , d v . Dacă valoarea asociată vîrfului curent este m, atunci fiecăruia dintre vecinii acestuia de valoare li se asociază valoarea m+1. Se observă că, dacă după ce toate vîrfurile de valoare m au fost considerate şi nici unui vîrf nu i-a fost recalculată valoarea, atunci toate vîrfurile conectate cu v0 au fost vizitate, deci calculul se încheie. Exemple 2.2.1. Fie graful,
1 2
3 6 4 7
5
şi v0=1.Valorile calculate prin aplicarea metodei prezentate sînt, vîrf
1
2
3
4
5
6
7
0
0
1
0
1
1
1
1
2
0
1
1
1
2
2
1
0
1
1
1
2
2
1
d
8
Algoritmi și tehnici de programare
9
2.2.2. Fie graful,
1
8 3
2
6
4 5
9
10 11
7
şi v0=1. Se observă că vîrfurile 8, 9, 10 şi 11 nu sînt conectate cu vîrful iniţial. Valorile rezultate prin aplicarea metodei sînt:
1
2
3
4
5
6
7
8
9
10
11
0
0
1
0
1
1
1
1
2
0
1
1
2
1
2
1
0
1
1
2
1
2
1
vîrf d
Se observă că valorile lui d calculate în final reprezintă numărul de muchii corespunzător unui cel mai scurt drum care conectează vîrful iniţial cu vîrful respectiv, pentru vîrfurile neconectate cu v0 valoarea d[v0] rezultată la terminarea calculului este . Fie G=(V,E) un graf, V n . O alternativă de implementare a metodei BF este construită prin utilizarea următoarelor structuri de date, A matricea de adiacenţă a grafului; o structură de tip coadă, C, în care sînt introduse vîrfurile ce urmează a fi vizitate şi procesate (în sensul cercetării vecinilor lor); un vector c cu n componente, unde, dacă i 1a, fost adăugat în coadă ci altfel 0, Componentele vectorului c sînt iniţializate cu valoarea 0.
10
Metode de programare
Parcurgerea BF poate fi descrisă astfel, coada C este iniţializată cu vîrful v0; cît timp C Ø, este extras şi vizitat un vîrf i din coadă, apoi sînt introduşi în coadă vecinii lui i care nu au fost deja introduşi (acele vîrfuri k cu proprietatea că c[k]=0 şi a[i][k]=1). Vîrfurile i ce au fost introduse în coadă sînt marcate prin c[i]=1. Exemplu 2.2.3. Pentru graful din exemplul 2.2.1., aplicarea metodei de traversare BF determină următoarea evoluţie, c t t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8
1
2
3
4
5
6
7
1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1
0 1 1 1 1 1 1 1
1 2 3 4 7 5 6
3 4 7 5 6
4 7 5 6
7 5 6
C t t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8
Observaţie Deoarece graful din exemplul 2.2.1. este conex, traversarea BF realizează vizitarea tuturor vîrfurilor grafului. Aplicarea metodei BF grafului din exemplul 2.2.2. nu determină vizitarea vîrfurilor 8,9, 10 şi 11, deoarece acestea sînt vîrfuri neconectate cu vîrful iniţial . Cu alte cuvinte, metoda BF aplicată unui graf determină vizitarea tuturor vîrfurilor care sînt conectate cu vîrful iniţial selectat. Sursa C pentru implementarea metodei BF este, #include <stdio.h> #include
10
Algoritmi și tehnici de programare nou->inf=info; nou->leg=NULL; if(*head==NULL) *head=nou; else (*tail)->leg=nou; *tail=nou; return 1; } else return 0; } int extrage_coada(pnod *head,pnod *tail, int *info) { if(*head){ pnod aux=*head; *info=(*head)->inf; (*head)=(*head)->leg; free(aux); if(*head==NULL)*head=*tail=NULL; return 1; } else return 0;} void breadth_first(int v0,int a[10][10],int n) { pnod head=NULL; pnod tail=NULL; int c[10]; for(int i=0;i
11
12
Metode de programare
În continuare sînt prezentate o serie de rezultate prin care este demonstrată proprietatea parcurgerii BF de a calcula distanţa minimă de la orice vîrf v conectat de vîrful iniţial v0 la v0. Lema 2.2.1. Fie G=(V,E) un graf oarecare şi v0 V arbitrar. Atunci, pentru orice
muchie u ,v E , v0 ,v v0 ,u 1 . Demonstraţie Dacă u este conectat de v0 în G, atunci, evident, şi v este conectat de v0 în G. În acest caz, cel mai scurt drum de la v0 la v nu poate fi mai lung decît cel mai scurt drum de la v0 la u prelungit cu muchia (u,v), deci afirmaţia este demonstrată. În situaţia în care u nu este conectat de v0 în G, atunci, evident, rezultă inegalitatea v0 ,v v0 ,u 1 . Lema 2.2.2 Fie G=(V,E) un graf neorientat sau graf direcţionat şi v0 V vîrf iniţial al
procedurii de traversare BF. Atunci orice v V vizitat, are loc inegalitatea d v v0 ,v . Demonstraţie Afirmaţia este demonstrată prin inducţie după ordinea vizitării BF a elementelor v V conectate cu v0 în G.
Dacă v v0 , rezultă d v 0 şi, pentru orice u V \ v, d u u ,v , deci afirmaţia este adevărată. Fie v vîrful vizitat ca rezultat al procesării vîrfului u. Prin aplicarea ipotezei inductive, d u v0 ,u , a rezultatului lemei 2.2.1 şi a procedurii de parcurgere BF obţinem,
d v d u 1 v0 ,u 1 v0 ,v .
Deoarece vîrful v nu a fost anterior găsit în lista vecinilor nici unui nod studiat înaintea vîrfului u, v este inserat în C.
Lema 2.2.3 Fie G=(V,E) un graf neorientat sau graf direcţionat şi C v1 ,v2 ,...,v p
coada calculată la un moment al aplicării procedurii de parcurgere BF. Atunci următoarele inegalităţile sînt verificate, [Cor,Lei şa]
d v p d v1 1
d vi d vi 1 , i 1,..., p 1 .
Teorema 2.2.1. Corectitudinea procedurii BF Fie G=(V,E) graf neorientat sau graf direcţionat şi v0 V vîrf iniţial al procedurii de traversare BF. Atunci metoda BF calculează toate vîrfurile v conectate cu v0 în G şi, pentru orice v v0 , v V vizitat, un cel mai scurt v0-v drum este format dintr-un v0-u drum şi muchia (u,v), unde u este acel vîrf prin procesarea căruia este determinată vizitarea lui v. Demonstraţie Fie Vk v V / v0 ,v k mulţimea vîrfurilor situate la distanţă k de v0. Rezultatul teoremei este demonstrat prin inducţie după k, cu ipoteza inductivă, Ik: v Vk , există un singur moment al execuţiei procedurii BF în care este determinată următoarea evoluţie, d v k şi v C ; dacă v v0 , vîrful u care determină inserarea lui v în C este element al mulţimii Vk 1 .
Pentru k 0 , V0 v0 . La momentul iniţial, C v0 şi d v0 0 , deci I este verificată. Verificarea ipotezei Ik în condiţiile în care I0 ,…,Ik-1 sînt adevărate este bazată pe următoarea observaţie. Pe tot parcursul execuţiei procedurii BF, C Ø şi, dacă u C , atunci 12
Algoritmi și tehnici de programare
13
d u şi vîrful care a determinat procesarea lui u rămîn constante. Din
lema
rezultă
2.2.3.
că,
dacă
C v1 ,v2 ,...,v p ,
atunci
d vi d vi 1 , i 1,..., p 1 . Fie v Vk , k 1 . Din proprietatea de monotonie şi ipoteza Ik-1, rezultă că v a fost inserat în C după ce toate vîrfurile u Vk 1 au fost deja inserate în coadă. Deoarece v0 ,v k , obţinem că există un v0-v drum de lungime k şi u Vk 1 astfel încît
u ,v E . Fără a pierde din generalitate, vom presupune că u este primul vîrf din Vk 1 inserat în
C. La momentul în care vîrful u devine prim element al cozii C, toate vîrfurile vecine cu u în G sînt inserate în C, deci şi vîrful v. Rezultă că d v d u 1 k , unde u este acel vîrf care precede v pe un cel mai scurt v0-v drum. Observaţii 1. Demonstrarea teoremei de corectitudine a parcurgerii BF stabileşte şi o modalitate de calcul al unui cel mai scurt v0-v drum astfel. Pentru orice v V conectat cu v0 în G, fie pv V vîrful a cărui procesare a determinat inserarea lui v în C. Un v0-v drum de lungime minimă este v0- pv drumul cel mai scurt “prelungit” cu muchia pv,v . 2. Aplicarea metodei BF unui graf oarecare G determină obţinerea unui arbore (vezi
capitolul 9) Gp, numit subgraful predecesorilor definit de BF pe G, unde G p V p , E p şi
V p v V / pv V v0 , E p pv,v E / v V \ v0 .
Exemplu 2.2.4 Prin aplicarea procedurii BF grafului din 2.2.1, obţinem,
1 2 5
3 6
4
7
14
Metode de programare
2.2.2. Metoda de parcurgere DF (Depth First) Ideea metodei DF revine la parcurgerea în adîncime a grafurilor. Considerînd v0 vîrf iniţial şi M mulţimea vîrfurilor vizitate de procedură, pentru vizitarea vecinilor este considerat unul din vîrfurile din M cu proprietatea că lungimea drumului calculat de metodă pînă la vîrful iniţial v0 este maximă. Implementarea acestei metode poate fi realizată în mai multe moduri, pentru menţinerea mulţimii vîrfurilor grafului disponibilizate pînă la momentul curent fiind utilizată o structură de de date de tip stivă S. La momentul iniţial se introduce în stivă v0. La fiecare pas, se preia cu ştergere ca vîrf curent vîrful stivei S şi se introduc în stivă vecinii încă nevizitaţi ai vîrfului curent. Un vîrf se marchează ca vizitat în momentul introducerii lui în S. Calculul continuă pînă cînd este efectuat un acces de preluare din stivă şi se constată că S este vidă. Pentru gestiunea vîrfurilor vizitate, se utilizează un vector c cu n componente, unde n reprezintă numărul vîrfurilor grafului şi, la fiecare moment, componentele sînt:
1, dacă i a fost vizitat ci 0, altfel Componentele vectorului c vor fi iniţializate cu valoarea 0. Exemple 2.2.5. Pentru graful, 1 2
3 6 4 7
5
şi v0=1, prin aplicarea metodei descrise, rezultă următoarea evoluţie. c 1
2
3
4
5
6
7
t=1
1
0
0
0
0
0
0
t=2
1
1
1
1
0
0
1
t=3
1
1
1
1
0
1
1
t=4
1
1
1
1
0
1
1
t
14
Algoritmi și tehnici de programare
15
t=5
1
1
1
1
1
1
1
t=6
1
1
1
1
1
1
1
t=7
1
1
1
1
1
1
1
t=8
1
1
1
1
1
1
1
S t t=1
1
t=2
7
4
3
2
t=3
6
4
3
2
t=4
4
3
2
t=5
5
3
2
t=6
3
2
t=7
2
t=8
Ordinea în care sînt vizitate vîrfurilor corespunzător acestei variante de parcurgere DF este: 1, 2, 3, 4, 7, 6, 5. 2.2.6. Pentru graful din exemplul 2.2.2 vîrfurile 8,9,10 care nu sînt conectate cu vîrful iniţial nu vor fi vizitate nici prin aplicarea metodei DF. Ordinea în care sînt vizitate vîrfurilor corespunzător acestei variante este: 1, 2, 3, 4, 6, 7, 5. O variantă de implementare a metodei DF rezultă prin gestionarea stivei S în modul următor. Iniţial vîrful v0 este unicul component al lui S. La fiecare etapă se preia, fără ştergere, ca vîrf curent vîrful stivei. Se introduce în stivă unul dintre vecinii vîrfului curent încă nevizitat. Vizitarea unui vîrf revine la introducerea lui în S. Dacă vîrful curent nu are vecini încă nevizitaţi, atunci el este eliminat din stivă şi este efectuat un nou acces de preluare a noului vîrf al stivei ca vîrf curent. Calculul se încheie în momentul în care este efectuat un acces de preluare a vîrfului stivei ca vîrf curent şi se constată că S este vidă. Evident, nici în cazul acestei variante nu vor fi vizitate vîrfurile care nu sînt conectate cu vîrful iniţial ales.
16
Metode de programare
Exemplu 2.2.7. Pentru graful,
1 2
3 6 4 7
5
şi v0=1, prin aplicarea metodei descrise, rezultă următoarea evoluţie.
c
1
2
3
4
5
6
7
t t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 t=9 t=10 t=11 t=12 t=13 t=14
1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1 1 1 1 1
S t t=1 t=2 t=3 t=4 t=5 t=6 t=7 t=8 t=9 t=10 t=11
1 2 4 3 6 7 6 3 4 5 4
1 2 4 3 6 3 4 2 4 2
1 2 4 3 4 2 1 2 1
1 2 4 2 1
1 2 1
1
1
16
Algoritmi și tehnici de programare
t=12 t=13 t=14
17
2 1
1
Ordinea în care sînt vizitate vîrfurile corespunzător acestei variante este: 1, 2, 4, 3, 6, 7, 5. Următoarea sursă C implementează varianta precedentă de parcurgere DF. #include <stdio.h> #include
18
Metode de programare
printf("Numarul de varfuri:");scanf("%i",&n); printf("\nMatricea de adiacenta\n"); for(int i=0;i
2.2.3. Parcurgerea în adîncime în varianta generalizată – DFG Următoarea variantă de implementare a parcurgerii în adîncime, DFG, determină vizitarea tutror vîrfurilor grafului analizat (considerat neorientat sau direcţionat), indiferent dacă acesta este conex sau neconex. Fie G=(V,E) un graf oarecare. Vom presupune în continuare că nici un vîrf din V nu este etichetat cu informaţia 0. Implementare traversării DFG utilizează următoarele structuri, A, matricea de adiacenţă a grafului; p, vectorul predecesorilor (vezi § 2.2.1); f, vectorul care marchează încheierea analizării listei vîrfurilor vecinilor nodului curent; mark, definit pentru orice v V prin, 0, dacă v nu a fost încă analizat mark[v]= 1, dacă v este procesat la momentul curent 2, dacă consultarea lui v este încheiată d, definit pentru orice v V prin d[v]=t, unde t este momentul de timp la care este iniţiată analiza vîrfului v. Considerînd t variabilă publică desemnînd momentul prelucrării, procedura DFG poate fi descrisă prin intermediul următoarelor funcţii. void DFG(graf G) { for( u V ){ mark[u]=0; p[u]=0; } t=0; for( u V ) if(!mark[u])DF_Visit(u); } void DF_Visit(varf u) { mark[u]=1; d[u]=t++; for( v V :A[u][v]==1) if(!mark[v]){ p[v]=u; DF_Visit(v); } mark[u]=2; f[u]=t++; }
18
Algoritmi și tehnici de programare
19
Prin aplicarea parcurgerii în adîncime în varianta generalizată sînt obţinute informaţii suplimentare ale grafului de intrare. Metoda DFG determină obţinerea subgraful predecesorilor, G p , de tip graf pădure (componentele conexe – vezi § 2.3- sînt arbori - vezi capitolul 9). Fiecare componentă conexă a lui G p este construită prin executarea modulului DF_Visit. De asemenea,
vîrfurile u ,v V au proprietatea că u pv dacă şi numai dacă funcţia DF_Visit(v) a fost apelată la momentul căutării în lista vecinilor vîrfului u. O altă proprietate importantă a metodei de parcurgere DFG este aceea că, după încheierea calculului, este determinată o structură de tip paranteză astfel. Dacă momentul selectării vîrfului u pentru procesare este marcat prin “(u” şi momentul încheierii prelucrării lui u este notat “u)”, atunci istoricul traversării DFG pentru calculul fiecărui arbore din G p poate fi reprezentat prin intermediul unei expresii corecte din punct de vedere al parantezării. Teorema 2.2.2 Corectitudinea parantezării determinată de aplicarea metodei DFG Fie G=(V,E) un graf sau un graf direcţionat. Prin aplicarea traversării DFG este obţinut următorul rezultat. Pentru orice u ,v V , una şi numai una din următoarele afirmaţii este adevărată, [Cor,Lei şa] 1) d u , f u şi d v, f v sînt disjuncte; 2)
d u, f u d v, f v şi u este un descendent al lui v în arborele corespunzător
din G p ; 3)
d u, f u d v, f v şi u este un ancestor al lui v în arborele corespunzător din Gp .
Observaţie Fie G=(V,E) un graf sau un graf direcţionat. Pe baza procedurii DFG poate fi realizată următoarea clasificare a elementelor e u ,v E ,
1) Muchii de tip arbore în DF- graful pădure G p , etichetate cu T: u ,v are eticheta T dacă procesarea vîrfului v a fost decisă ca rezultat al testării existenţei muchiei e; 2) Muchii de tip înapoi, cu etichetă B: u ,v este muchie B dacă v este ancestorul lui u într-o componentă conexă a DF- grafului pădure G p ;
3) Muchii de tip înainte, notate cu F: acele muchii u ,v , neetichetate cu T şi în care v este descendent al lui u într-o componentă conexă a DF- grafului pădure G p ;
4) Muchii de tip trecere, etichetate cu C: toate muchiile u ,v rămase neetichetate după încheierea etichetării cu T, B şi F. Teorema 2.2.3. Fie G=(V,E) un graf neorientat. Orice element e E este fie de tip T, fie de tip B. [Cor,Lei şa] Teorema 2.2.4. Criteriu de aciclicitate pentru grafuri direcţionate Un graf direcţionat este aciclic (vezi §2.4) dacă şi numai dacă nici una din muchii nu este de tip B. [Cor,Lei şa]
20
Metode de programare
Exemple 2.2.8. Pentru graful 1
8 3
2
6
4
9
10
5 7 obţinem, 1) ordinea de parcurgere DFG a vîrfurilor: 1,2,3,4,6,7,5,8,9,10 2) graful pădure G p ,
8 1
2
9
3 10
4 6
5
7 3) structurile paranteză: (1 (2 (3 3) (4 (6 (7 7) 6) (5 5) 4) 2) 1) şi (8 (9 (10 10) 9) 8) 4) clasificarea muchiilor,
2
T
1
10
4
B
T
T
T
T
6
9
3
T B
8
T
5
B
T 7 2.2.9 Fie graful direcţionat,
6 5
7 8
1
2
4
3
Prin parcurgerea DFG obţinem următoarea ordonare: 1,7,6,8,5,2,4,3. Subgraful predecesorilor este format din următoarele componente,
20
Algoritmi și tehnici de programare
21
1
2 4
7 6
3
8
5 Structurile paranteză: (1 (7 (6 (5 5) 6) (8 8) 7) 1) şi (2 (4 4) (3 3) 2). Clasificarea muchiilor grafului direcţionat este,
1 T
2 T
T B
6 T
4
F
7
C
T
T C
B 3
8 C
5
2.3. Drumuri în grafuri. Conexitate 2.3.1 Drumuri; definiţii Una dintre cele mai importante proprietăţi ale grafurilor o constituie posibilitatea de accesare, prin intermediul unei secvenţe de muchii (arce), dintr-un vîrf dat a oricărui alt vîrf al grafului, proprietate cunoscută sub numele de conexitate sau conexiune. Aşa după cum a rezultat în §2.2., dacă G=(V,E) este un graf conex, atunci pentru orice vîrf iniţial v0 considerat metodele BF şi DF permit vizitarea tuturor vîrfurilor din V. Definiţia 2.3.1. Fie G=(V,E) un graf, u,vV. Secvenţa de vîrfuri : u0, u1,..,un este un u-v drum dacă u0=u, un=v, uiui+1E pentru toţi i, 0 i n . Lungimea drumului, notată l() este egală cu n. Convenţional, se numeşte drum trivial, un drum cu l()=0. Definiţia 2.3.2. Fie : u0, u1,..,un un drum în graful G=(V,E). este un drum închis dacă u0=un; în caz contrar, se numeşte drum deschis. Drumul este elementar dacă oricare două vîrfuri din sînt distincte, cu excepţia, eventual, a extremităţilor. Drumul este proces dacă, pentru orice 0 i j n 1 uiui+1 ujuj+1. Evident, orice drum elementar este un proces.
22
Metode de programare
Exemplu 2.3.1. Pentru graful,
v2
v4 v5
v1
v3
1: v1, v2, v3, v2, v5, v3, v4 este un v1- v4 drum care nu este proces; 2: v1, v2, v5, v1, v3, v4 este un v1- v4 proces care nu este drum elementar; 3: v1, v3, v4 este un v1- v4 drum elementar. Definiţia 2.3.3. Fie : u0, u1,..,un un drum în graful G=(V,E). ’: v0, v1,..,vm este un subdrum al lui dacă ’ este un drum şi pentru orice j, 0 j m , există i, 0 i n astfel încît ui=vj. Observaţie Orice drum cu lungime cel puţin 1 conţine cel puţin un drum elementar cu aceleaşi extremităţi. Într-adevăr, dacă : u0, u1,..,un nu este elementar, atunci există 0 i j n şi i 0 sau j n astfel încît ui=uj. Atunci drumul
u j u j 1 ...u n , dacă i 0 : u0 u1 ...u i , dacă j 0 u u ...u u ...u , dacă i 0 , j n 0 1 i j 1 n '
este de asemenea un u0-un drum. Aplicînd în continuare eliminarea duplicatelor vîrfurilor în modul descris, rezultă în final un u0-um drum elementar.
Exemplu 2.3.2. În graful,
v2
v6
v1
v4 v3
v7
v5
v8
v10
v9
dacă : v1, v2, v4, v5, v3, v1, v2, v5, v6, v7, v8, v9, v5, v9, v8, v10, atunci 1: v1, v2, v5, v9, v8, v10, 2: v1, v2, v4, v5, v9, v8, v10 sînt v1-v10 subdrumuri elementare.
22
Algoritmi și tehnici de programare
23
2.3.2. Matricea existenţei drumurilor; algoritmul Roy-Warshall Lema 2.3.1. Fie G=(V,E) un graf, V n . Dacă A este matricea de adiacenţă asociată grafului, atunci, pentru orice p1, a ij( p ) este numărul vi-vj drumurilor distincte de lungime p din
graful G, unde A p aij( p ) . Demonstraţie Demonstrarea acestei afirmaţii este realizată prin inducţie după p Pentru p=1, deoarece pentru orice 1 i , j n există cel mult un vi-vj drum de lungime 1 şi dacă există, fie acesta Г: vi, vj. Rezultă că numărul vi-vj drumurilor de lungime 1 este egal cu aij1 .
Presupunem că Ap-1 = aij p 1 are proprietatea că pentru toţi 1 i , j n , aij p 1 este egal cu numărul vi-vj drumurilor de lungime p-1 în G.
Cum Ap=Ap-1A = aij p , rezultă că, 1 i , j n , a ij( p )
p
a k 1
( p 1 ) ik
a kj . Orice vi-vj drum
de lungime p în G conţine un vi-vk drum de lungime p-1 pentru un anume vk adiacent cu vj şi reciproc, pentru orice vk adiacent cu vj oricărui vi-vk drum de lungime p-1 îi corespunde un vi-vj drum de lungime p. Din relaţia care caracterizează elementele aij p , utilizînd ipoteza inductivă, rezultă
afirmaţia enunţată mai sus. Definiţia 2.3.4. Fie Mn({0,1)} mulţimea matricelor de dimensiuni nxn, componentele fiind elemente din mulţimea {0,1}. Pe Mn({0,1)}se definesc operaţiile binare, notate şi , astfel: pentru orice A=(aij), B=(bij) din Mn({0,1)}, A B=(cij), A B=(dij), unde 1 i , j n , cij=max{aij, bij} dij=max{min{aik, bkj}, 1 k n }.
; k 1 secvenţa de matrice definită k
(k )
Dacă A=(aij) Mn({0,1)}, se notează A a ij prin:
1
( k 1 )
k
, k 2 . Dacă A este matricea de adiacenţă a unui graf G=(V,E), atunci pentru fiecare k, A
A, A A A
(k ) 1, dacă există drum de la i la j de lungime k 1 k n 1 , a ij 0 , altfel (1)
(2)
( n 1 )
Matricea M A A A se numeşte matricea existenţei drumurilor în graful G. Semnificaţia componentelor matricei M este:
0 , dacă nu există vi v j drum în G 1 i , j n , mij 1, altfel
24
Metode de programare
Exemplu 2.3.3. Pentru graful,
2 1 3
4 0 1 A 1 1
1 0 0 0
1 0 0 1
1 0 , 1 0
1 2 0 A 1 1
0 1 1 1
1 1 1 1
1 1 , 1 1
1 3 1 A 1 1
1 0 1 1
1 1 1 1
1 1 1 1 1 1 , M 1 1 1 1 1 1
1 1 1 1
1 1 1 1
Observaţie Calculul matricei existenţei drumurilor permite verificarea dacă un graf dat este conex. Graful este conex dacă şi numai dacă toate componentele matricei M sînt egale cu 1. Algoritmul Roy-Warshall calculează matricea existenţei drumurilor într-un graf G cu n vîrfuri. void Roy_Warshall (unsigned char a[10][10],unsigned n,unsigned char m[10][10]) {int i,j,k; for (i=0;i
Datele de intrare sînt: n, numărul de noduri şi A, matricea de adiacenţă corespunzătoare grafului. Matricea M calculată de algoritm constituie ieşirea şi este matricea existenţei drumurilor în graful G.
2.3.3. Componente conexe ale unui graf Definiţia 2.3.5. Fie G=(V,E) graf netrivial. Vîrfurile u,v V sînt conectate dacă există un u-v drum în G. Definiţia 2.3.6. Dacă G este un graf, atunci o componentă conexă a lui G este un subgraf conex al lui G, maximal în raport cu proprietatea de conexitate.
24
Algoritmi și tehnici de programare
25
Exemplu 2.3.4. Componentele conexe ale grafului
1
5
2 6 4 3 sînt: C1={1,2,3}, C2={4,5}, C3={6}. Observaţii 1) Un graf este conex dacă şi numai dacă numărul componentelor sale conexe este 1. 2) Mulţimile de vîrfuri corespunzătoare oricăror două componente conexe distincte sînt disjuncte. Rezultă că mulţimile de vîrfuri corespunzătoare componentelor conexe ale unui graf formează o partiţie a mulţimii vîrfurilor grafului. Problema determinării componentelor conexe corespunzătoare unui graf poate fi rezolvată în modul următor. Iniţial, este selectat drept vîrf curent un vîrf al grafului pentru care este calculată componenta conexă care îl conţine. Dacă există vîrfuri care nu aparţin componentei conexe determinate, este ales drept vîrf curent unul dintre aceste vîrfuri. În continuare este aplicată aceeaşi metodă, pînă cînd au fost găsite toate componentele conexe ale grafului. Determinarea componentei conexe care conţine un vîrf v0 dat poate fi realizată pe baza următorului algoritm. Pentru G=(V,E), V n , n 1 şi v0 V, paşii algoritmului sînt: Pas1: V0={v0}; E0= ; i=0; Pas 2: repetă Pas 3 pînă cînd Vi=Vi-1 şi Ei=Ei-1 Pas 3: i=i+1;
Vi Vi 1 v / v V, u Vi 1 , uv E;
E i E i 1 e / e E, u Vi 1 , u incident cu e; Ieşirea este Gi=(Vi,Ei), componenta conexă din care face parte v0. Exemplu 2.3.5. Pentru graful,
1
4
2
5
7
8
3
9
6
Aplicarea algoritmului descris pentru v0=1, determină următoarea evoluţie: I Vi Ei i=0 {1} Ø i=1 {1,2,4} {(1,2),(1,4)} i=2 {1,2,4,7,8,5} {(1,2),(1,4),(2,7),(2,8),(7,8),(4,5),(4,7),(5,8)}
26
Metode de programare
2.3.4. Drumuri de cost minim Definiţia 2.3.7. Fie G=(V,E,w) un graf ponderat. Costul drumului : u1,u2,..,un, notat L(), este definit prin: n 1
L wu i ,u i 1 . i 1
Pentru orice u şi v vîrfuri conectate în G, u v, w-distanţa între u şi v, notată D(u,v), este definită prin, Du ,v minL , Duv , unde Duv desemnează mulţimea tuturor u-v drumurilor elementare din G. Dacă Duv este astfel încît D(u,v)=L(), drumul se numeşte drum de cost minim. Observaţie Cu toate că este utilizat termenul de w-distanţă, în general D nu este o distanţă în sensul matematic al cuvîntului.În particular, dacă funcţia pondere asociază valoarea 1 fiecărei muchii a grafului, atunci pentru fiecare pereche de vîrfuri distincte ale grafului, costul D(u,v) este lungimea unui cel mai scurt drum între cele două vîrfuri. În acest caz D este o distanţă pe mulţimea vîrfurilor. Algoritmul Dijkstra Următorul algoritm a fost propus de către E. W. Dijkstra pentru determinarea wdistanţelor D(u0,v) şi a cîte unui u0-v drum de cost minim pentru fiecare vîrf vu0 într-un graf ponderat, unde u0 este prestabilit.
Fie G=(V,E,w) un graf conex ponderat, u0V, SV, u0S. Se notează S V \ S şi
D u0 , S min Du0 , x ; x S . Fie v S astfel încît D(u0,v)=D(u0, S ), : u0, u1,…,upv un u0-
v drum de cost minim. Evident, 0ip uiS şi ’: u0, u1,…,up un u0- up drum de cost minim. De asemenea,
D u0 , S min Du0 ,u w( uv ); u S ,v S ,uv E .
Dacă xS, y S astfel încît D u0 , S Du0 , x w( xy ) , rezultă
Du0 , y Du0 , x w( xy ) .
Pentru determinarea a cîte unui cel mai ieftin u0-v drum, algoritmul consideră o etichetare dinamică a vîrfurilor grafului.Eticheta vîrfului v este (L(v),u), unde L(v) este lungimea unui cel mai ieftin u0-v drum determinat pînă la momentul respectiv şi u este predecesorul lui v pe un astfel de drum. Pentru (V,E,w) graf conex ponderat, V n şi u0V, calculul implicat de algoritmul Dijkstra poate fi descris astfel: Pas 1: i=0; S0={u0}; L(u0)=0, L(v)= pentru toţi v V, v≠u0. Dacă n=1 atunci stop Pas 2: Pentru toţi v S i , dacă L(v)>L(ui)+w(uiv), atunci L(v)=L(ui)+w(uiv) şi etichetează v cu (L(v),ui). Pas 3: Se determină d=min{L(v), v S i } şi se alege ui+1 S i astfel încît L(ui+1)=d. Pas 4: Si+1=Si {ui+1} Pas 5: i=i+1. Dacă i=n-1, atunci stop. Altfel, reia Pas 2. Observaţie Dacă (V,E,w) graf ponderat neconex, atunci, pentru u0V, algoritmul lui Dijkstra permite determinarea w-distanţelor D(u0,v) şi a cîte unui u0-v drum de cost minim pentru toate vîrfurile v din componenta conexă căreia îi aparţine u0.
26
Algoritmi și tehnici de programare
27
Exemplu 2.3.6. Fie graful ponderat, 1 5
1
2
9
3 16
2 5
5
4
Considerînd u0=1, etapele în aplicarea algoritmului Dijkstra sînt: P1: i=0; S0={1}; L(1)=0, L(i)= pentru toţi i 2,5 . P2: S 0 ={2,3,4,5}, u0=1 L(2)= >L(1)+5=5 L(2)=5, etichetează 2 cu 1 L(3)= >L(1)+1=1 L(3)=1, etichetează 3 cu 1 L(4)= >L(1)+9=9 L(4)=9, etichetează 4 cu 1 L(5)= , w(1,5)= , deci L(5) nu se modifică P3: selectează u1=3, L(3)=1, cea mai mică dintre w-distanţele calculate la P2 P4: S1={1,3} P5: i=i+1=1 ≠ 4, reia P2 P2: S1 ={2,4,5}, u1=3 Nu se modifică nici o etichetă şi nici o w-distanţă (w(3,i)= , pentru toţi i din
S1 ) P3: selectează u2=2, L(2)=5, cea mai mică dintre w-distanţele calculate la P2 P4: S2={1,3,2} P5: i=i+1=2 ≠ 4, reia P2 P2: S 2 ={4,5}, u2=2 L(4)= 9>L(2)+2=7 L(4)=7, etichetează 4 cu 2 L(5)= >L(2)+16=21, etichetează 5 cu 2 P3: selectează u3=4, L(4)=7, cea mai mică dintre w-distanţele calculate la P2 P4: S3={1,3,2,4} P5: i=i+1=3 ≠ 4, reia P2 P2: S 3 ={5}, u3=4 L(5)= 21>L(4)+5=12, etichetează 5 cu 4 P3: selectează u4=5, L(5)=12, cea mai mică dintre w-distanţele calculate la P2 P4: S3={1,3,2,4,5} P5: i=i+1=4, stop. Algoritmul calculează următoarele rezultate: Vîrful v pînă la care este 1 calculată w-distanţa D(1,v), eticheta lui v 0, 1
2
3
4
5
5, 1
1, 1
7, 2
12, 4
28
Metode de programare
Drumurile de cost minim de la vîrful 1 la fiecare dintre vîrfurile grafului se stabilesc pe baza sistemului de etichete astfel: drumul de la 1 la un vîrf v este dat de: v1, eticheta lui v, v2 eticheta lui v1 şamd, pînă se ajunge la eticheta 1. Astfel, v0 -drumurile de cost minim sînt: pînă la 2: 2,1; pînă la 3: 3,1; pînă la 4: 4,2,1; pînă la 5: 5,4,2,1. Următoarea sursă C implementează algoritmul Dijkstra. #include<stdio.h> #include
28
Algoritmi și tehnici de programare
29
modifica(s,sb,ui,&ns,&nb); } return r; } void main() { int n,i,j; clrscr(); printf("Numarul de varfuri"); scanf("%i",&n); printf("Matricea ponderilor:\n"); float w[50][50]; for(i=0;i
În anumite aplicaţii este necesară exclusiv determinarea w-distanţelor D(v0,v), pentru toţi vV. În acest caz algoritmul Roy-Floyd permite o rezolvare a acestei probleme mai simplu de implementat decît algoritmul Dijkstra. Algoritmul Roy-Floyd Pentru (V,E,w) graf ponderat, V n şi W matricea ponderilor, sistemul de w-distanţe D(v0,v), vV, poate fi calculat pe baza următoarei funcţii (similară algoritmului Roy-Warshall), void Roy_Floyd (float w[10][10],unsigned n,float d[10][10],float MAX) {int i,j,k; for (i=0;i
Matricea D calculată de algoritm este matricea w-distanţelor D(u,v) în graful ponderat conex (V,E,w); pentru orice 1 i , j n
30
Metode de programare
D( vi ,v j ), vi ,v j sunt conectate d ij , altfel Într-adevăr, procedura realizează calculul dinamic al w-distanţei între oricare două vîrfuri i şi k, astfel: dacă există un drum i-k drum ce trece prin j ( 1 j n ), cu costul corespunzător (dij+djk) inferior costului curent (dik), atunci noul drum de la i la k via j este de cost mai mic decît costul drumului vechi, deci w-distanţa între i şi k trebuie reactualizată la dij+djk. Algoritmul Yen Algoritmul propus de Yen pentru calculul tuturor w-distanţelor într-un graf ponderat este mai eficient din punctul de vedere al volumului de operaţii decît algoritmul Roy-Floyd. Fie (V,E,w) un graf ponderat şi W matricea ponderilor. Pentru determinarea w-distanţelor de la vîrful vk fixat la celelalte vîrfuri ale grafului, algoritmul Yen iniţiază următoarele operaţii, Pas 1: D=W Pas 2: i=1; λ(k)=0, b(k)=0; λ(j)=0, pentru toţi 1 j n , j k Pas 3: Calculează min{dkj; 1 j n , λ(j)=1}; Determină j0 astfel încît λ(j0)=1 şi d kj0 = min{dkj; 1 j n , λ(j)=1} B(j0)= d kj0 , λ(j0)=0 d[k,j] =min{d[k,j],d[k,j0]+d[j0,j]}, pentru toţi j, 1 j n i=i+1 Pas 4: Dacă i
1 4 5
3 7
2 1 4
4
2 5 3
30
Algoritmi și tehnici de programare
31
Se consideră vk=1.
3 Pas 1: D 2 7 4
3 5
2 5 4 1
7 4
4 1
Pas 2: i=1, λ=(0,1,1,1,1); B(1)=0
3 Pas 3: j0=3, B(3)=2, λ=(0,1,0,1,1); D 2 7 4
3 5
2 5 4 1
6 4
3 1 ; i=2
Pas 4: i<5, reia Pas 3 Pas 3: j0=2, B(2)=3, λ=(0,0,0,1,1); nici o modificare în matricea D; i=3 Pas 4: i<5, reia Pas 3 Pas 3: j0=5, B(5)=3, λ=(0,0,0,1,0); nici o modificare în matricea D; i=4 Pas 4: i<5, reia Pas 3 Pas 3: j0=4, B(4)=6, λ=(0,0,0,0,0); nici o modificare în matricea D; i=5 Pas 4: i=5, stop.
2.4. Circuite şi cicluri în grafuri şi în digrafuri Definiţia 2.4.1. Fie G=(V,E) un graf netrivial, u, vV şi un u-v drum în G. se numeşte proces dacă toate muchiile drumului sînt distincte. Drumul este trivial dacă : u,u. Definiţia 2.4.2. Drumul este un circuit dacă este un proces netrivial închis. Definiţia 2.4.3. Circuitul : v1, v2,…., vn, v1 cu n3 este un ciclu al grafului, dacă, pentru orice i, j, cu 1 i , j n, i j , rezultă vivj. Observaţie Orice ciclu este un drum elementar închis. Definiţia 2.4.4. Graful G este aciclic dacă nu există cicluri în G. Observaţie Într-un digraf D noţiunile de proces, circuit, ciclu sînt definite ca şi în cazul grafurilor.
32
Metode de programare
Exemple 2.4.1. În graful, v1 v4 v2 v3 v5 v6 1: v1, v2, v3, v6, v5 este un proces; 2: v1, v2, v3, v6, v5, v3, v4, v1 este un circuit şi nu este ciclu; 3: v1, v3, v5, v4, v1 este un ciclu.
2.4.2. Drumul : v1,v2,v4,v3,v1 este un ciclu, deci graful conţine cicluri.
v1
v2
v3
v4
V1
V2
V3
V4
2.4.3. Digraful,
nu conţine cicluri. Definiţia 2.4.5. Fie D=(V,E) un digraf. Funcţiile grad exterior, odD, respectiv grad interior, idD, sînt definite prin, od D : V N ; id D : V N ,
u V , od D u v / v V , uv E , u V , id D u v / v V , vu E
Funcţia grad, notată degD, este definită astfel,
deg D : V N, u V, deg D u id D u od D u .
Algoritmul Marimont Procedura Marimont verifică dacă un digraf D=(V,E), V n , este sau nu aciclic. La terminarea calculului este afişat mesajul “DA”, dacă digraful D este aciclic, respectiv “NU”, în caz contrar. Descrierea pe paşi a algoritmului Marimont este, Pas 1: V0=V, E0=E, D0=(V0,E0) Pas 2: Dacă od D0 v 1 pentru toţi vV0, scrie “NU”, stop (dacă toate vîrfurile sînt extremităţi iniţiale ale măcar unui arc, atunci există cicluri în D0); altfel, continuă. Pas 3: Selectează vV0 cu od D0 v 0 ;V0=V0\{v}; E0=E0-{e/ eE0, e incidentă cu v în D0}; D0=(V0,E0) Pas 4: Dacă V0Ø, atunci reia pasul 2; altfel scrie “DA”, stop. Exemple 2.4.4 Pentru digraful,
32
Algoritmi și tehnici de programare
33
1 e1 4
e2
2
e3
e4
3
e5 5
evoluţia algoritmului Marimont este, Pas 1: V0={1,2,3,4,5}, E0={e1,e2,e3,e4,e5} Pas 2: od D0 5 0 , continuă
1 e1 4
e2
2
e3
e4
3
Pas 3: Selectează vîrful 5, elimină 5 din V0, elimină arcul e5 E0 Pas 4: reia de la pasul 2 Pas 2: od D0 i 1 pentru toţi i din V0 ={1,2,3,4}, scrie “NU”, stop. 2.4.5. Pentru digraful D:
6
e7
e9
5
4 e6
e1 e5
e3 3
e8
7
1 e4
2 e2
algoritmul Marimont determină următoarea secvenţă de operaţii: Pas 1: V0={1,2,3,4,5,6,7}, E0={e1,e2,e3,e4,e5,e6,e7,e8,e9} Pas 2: od D0 7 0 , continuă Pas 3: Selectează vîrful 7, elimină 7 din V0, elimină arcele e8 şi e9 din E0
D0:
6
e7
5
4 e6
1 e4
e1 e5
e3 3
2 e2
Pas 4: reia de la pasul 2 Pas 2: od D0 6 0 , continuă Pas 3: Selectează vîrful 6, elimină 6 din V0, elimină arcul e7 din E0 D0:
5
4 e6
1 e4
e1 e5
e3 3
2 e2
34
Metode de programare
Pas 4: reia de la pasul 2 Pas 2: od D0 5 0 , continuă Pas 3: Selectează vîrful 5, elimină 5 din V0, elimină arcul e6 din E0
D0:
1 e4
4
e1 e5
e3 3
2 e2
Pas 4: reia de la pasul 2 Pas 2: od D0 4 0 , continuă Pas 3: Selectează vîrful 4, elimină 4 din V0, elimină arcele e4, e5 şi e3 din E0
D0:
1 e1 2 e2 3 Pas 4: reia de la pasul 2 Pas 2: od D0 3 0 , continuă Pas 3: Selectează vîrful 3, elimină 3 din V0, elimină arcul e2 din E0
D0: 1 e1 2 Pas 4: reia de la pasul 2 Pas 2: od D0 2 0 , continuă Pas 3: Selectează vîrful 2, elimină 2 din V0, elimină arcul e1 din E0
D0: • 1 Pas 4: reia de la pasul 2 Pas 2: od D0 1 0 , continuă Pas 3: Selectează vîrful 1, elimină 1 din V0 V0=Ø Pas 4: scrie “DA”, stop. Algoritmul Marimont poate fi descris în C astfel, #include<stdio.h> #include
34
Algoritmi și tehnici de programare if(arce[i].vi==v) od++; return od; } void elimina_varf(int *varf,int *nv,int v) { int gasit=0; for(int i=0;(i<*nv)&&!gasit;i++) if(varf[i]==v){ gasit=1; for(int j=i+1;j<*nv;j++) varf[j-1]=varf[j]; } (*nv)--; } void elimina_arce(arc *arce,int *na, int v) { for(int i=0;i<*na;) if((arce[i].vi==v)||(arce[i].vf==v)){ for(int j=i+1;j<*na;j++){ arce[j-1].vi=arce[j].vi; arce[j-1].vf=arce[j].vf; } (*na)--; } else i++; } int ciclic(int *varf,arc *arce,int nv, int na) { for(int i=0;i
35
36
Metode de programare
printf("Numarul de varfuri"); scanf("%i",&n); for(i=0;i
36
Algoritmi și tehnici de programare
37
3. Structuri arborescente
Una dintre cele mai studiate clase de grafuri sînt cele de tip arbore. În acest capitol sînt prezentate principalele caracteristici ale arborilor, algoritmi pentru calculul arborelui parţial de cost minim, arbori direcţionaţi, arbori cu rădăcină şi arbori binari. Pe lîngă operaţiile primitive asupra arborilor – căutarea unei informaţii, inserarea unui nod, extragerea unui nod şi metode de parcurgere, sînt prezentate două clase importante de arbori binari: arbori de sortare şi arbori de structură.
3.1. Grafuri de tip arbore 3.1.1. Definiţii şi caracterizări ale grafurilor arbori Structurile cele mai simple şi care apar cel mai frecvent în aplicaţii sînt cele arborescente (arbori). Grafurile arbori constituie o subclasă a grafurilor conexe. Definiţia 3.1.1 Graful G este arbore dacă G este aciclic şi conex. Definiţia 3.1.2. Fie G=(V,E) graf arbore. Subgraful H=(V1,E1) al lui G este subarbore al lui G dacă H este graf arbore. Exemple 3.1.1. Graful 1 2
4
3
5
6 7
este arbore, deoarece, orice (i,j) E , i≠j, există un i-j drum şi graful nu conţine cicluri.
38
Metode de programare
3.1.2. Graful
1
4
3
2
7 5 7
nu este arbore, deoarece drumul :1,4,6,2,1 este un ciclu. 3.1.3. Graful
1
4
3
7
2 5
9
6 8
nu este arbore, deoarece conţine trei componente conexe: {1,2,3,4,6}, {3} şi {7,8}. Verificarea proprietăţii unui graf de a fi arbore poate fi realizată prin intermediul unor algoritmi care să verifice calităţile de conexitate şi respectiv aciclicitate. De asemenea, verificarea proprietăţii unui graf de a fi arbore poate fi realizată astfel. Proprietatea 1. Un graf G=(V,E), cu V n , E m este graf arbore dacă şi numai dacă G este aciclic şi n=m+1. Exemple 3.1.4. Graful din 3.1.1 este arbore, pentru că este aciclic şi n=7, m=6. 3.1.5. Graful din 3.1.2. nu este arbore pentru că este ciclic. 3.1.6. Graful din exemplul 3.1.3. nu este arbore deoarece este aciclic, dar n=9, m=6. Proprietatea 2 Un graf G=(V,E), cu V n , E m este graf arbore dacă şi numai dacă G este conex şi n=m+1. Exemple 3.1.7. Graful din 3.1.1. este arbore deoarece este conex şi n=m+1. 3.1.8. Graful conex din exemplul 3.1.2. nu este arbore pentru că n=6 şi m=8. 3.1.9. Graful din 3.1.3. nu este conex, deci nu este graf arbore. Observaţie Fie G=(V,E) un graf. Următoarele afirmaţii sînt echivalente, 1. G este graf arbore; 2. G este graf conex minimal: oricare ar fi eE, prin eliminarea muchiei e din E, graful rezultat nu este conex; 3. G este graf aciclic maximal: prin adăugarea unei noi muchii în graf rezultă cel puţin un ciclu.
38
Algoritmi și tehnici de programare
39
Definiţia 3.1.3. Se numeşte graf asimetric un digraf D=(V,E) cu proprietatea că pentru orice u ,v E dacă uvE, atunci vu E. Digraful D este simetric dacă u ,v E , uvE, dacă şi numai dacă vuE. Definiţia 3.1.4. Fie D=(V,E) digraf netrivial. Graful G=(V,E’), unde E’={uv/ uvE sau vuE} se numeşte graf suport al digrafului D. Definiţia 3.1.5. Un arbore direcţionat este un graf orientat asimetric şi astfel încît graful suport corespunzător lui este graf arbore. Definiţia 3.1.6. Arborele direcţionat T=(V,E) este arbore cu rădăcină dacă există rV astfel încît, pentru orice uV, u r, există r-u drum în T. Vîrful r se numeşte rădăcina arborelui direcţionat T. Definiţia 3.1.7. Fie T=(V,E) arbore direcţionat. Arborele T1=(V1,E1) este subarbore al lui T dacă V1V, E1E şi T1 este arbore direcţionat. Observaţie Graful suport al unui arbore direcţionat este aciclic, deci, pentru orice uV, u r, r-u drumul din T este unic. De asemenea, un arbore direcţionat are cel mult o rădăcină. Rezultă că, pentru orice uV, u r, distanţa de la rădăcină la vîrful u este egală cu numărul de muchii ale r-u drumului în T. Exemple 3.1.10. Arborele direcţionat
1
3 6
5
2
10
9
8
7
4
este arbore cu rădăcină 1.
3.1.11 Arborele direcţionat
1
2 7
3
4 5 nu are rădăcină. 3.1.12. Arborele
6
40
Metode de programare
1
2
4 6
5
8
10
este un subarbore cu rădăcină 1 al arborelui din 3.1.10.
3.1.2. Reprezentări şi parcurgeri ale arborilor orientaţi Definiţia 3.1.8. Un arbore orientat este un arbore direcţionat cu rădăcină. Definiţia 3.1.9. Fie T=(V,E), un arbore orientat cu rădăcină r. Un vîrf v 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. Deoarece orice arbore orientat este în particular digraf, reprezentarea arborilor orientaţi poate fi realizată prin utilizarea oricăreia dintre modalităţile prezentate în §8.1. Datorită caracteristicilor arborilor orientaţi pot fi însă obţinute reprezentări mai eficiente din punct de vedere al spaţiului de memorie solicitat. Una dintre modalităţi este reprezentarea de tip FIU-FRATE, care constă în numerotarea convenţională a vîrfurilor grafului şi memorarea, pentru fiecare vîrf i al arborelui, a următoarelor informaţii, - FIU(i): numărul ataşat primului descendent al vîrfului i; - FRATE(i): numărul ataşat vîrfului descendent al tatălui vîrfului i şi care urmează imediat lui i; - INF(i): informaţia ataşată vîrfului i (de obicei valoarea i). Pentru reprezentarea arborelui sînt reţinute rădăcina şi numărul nodurilor. Absenţa „fiului”, respectiv a :fratelui” unui vîrf este marcată printr-o valoare din afara mulţimii de numere ataşate vîrfurilor (de obicei valoarea 0). Exemplu 3.1.13. Arborele orientat
40
Algoritmi și tehnici de programare
41
1
2
3
5
6
9 10
11
4
7
12 13
8
14
15
16
este reprezentat astfel, N=16, R=1 (rădăcina), FIU=(2,5,0,8,0,9,0,14,0,0,0,0,0,0,0,0) FRATE=(0,3,4,0,6,7,0,0,10,11,12,13,0,15,16,0) O alternativă a reprezentării FIU-FRATE poate fi obţinută prin utilizarea structurile de date dinamice. Presupunînd că fiecare vîrf al arborelui are cel mult n descendenţi, fiecărui vîrf îi este ataşată structura, identificator vîrf
vector de legături către descendenţii vîrfului adresă fiu 1
…
adresă fiu n
Următoarea sursă C implementează problema construcţiei unui arbore orientat, reprezentat prin intermediul unei structuri dinamice arborescente. Numărul maxim de descendenţi ai unui nod este 4. În cazul unui număr mai mare de descendenţi este preferată în general reprezentarea FIU-FRATE, datorită dimensiunii spaţiului de memorie ocupat. Afişarea informaţiilor arborelui creat este realizată prin traversarea în A-preordine (a se vedea paragraful următor).
#include<stdio.h> #include
42
Metode de programare
void inserare(arbore *ppred) { int j,info; arbore *pred; for(int nr=0;(*ppred)->fiu[nr];nr++){ (*pred)=(*ppred)->fiu[nr]; printf("Numarul de fii ai nodului %i:",(*pred)->inf); scanf("%i",&j); for(int k=0;k<j;k++){ scanf("%i",&info); inserare_tata(pred,k,info); } } for(nr=0;(*ppred)->fiu[nr];nr++) inserare(&((*ppred)->fiu[nr])); } void A_preordine(arbore r) { if(r){ printf("%i ",r->inf); for(int i=0;i<4;i++) A_preordine(r->fiu[i]); } } void main(){ clrscr(); int n,j,info; arbore radacina=NULL; printf("Introduceti informatiile pe niveluri\n"); printf("Introduceti radacina\n"); scanf("%i",&info); radacina=(arbore)malloc(sizeof(arb)); radacina->inf=info; for(int i=0;i<4;i++)radacina->fiu[i]=NULL; printf("Numarul de fii ai nodului %i",radacina->inf); scanf("%i",&j); for(int k=0;k<j;k++){ scanf("%i",&info); inserare_tata(&radacina,k,info); } arbore ppred=radacina; inserare(&ppred); printf("Parcurgerea A-preordine a arborelui : \n"); A_preordine(radacina); getch();}
Parcurgerea unui arbore orientat revine la aplicarea sistematică a unei reguli de vizitare a vîrfurilor arborelui. Cele mai utilizate reguli de parcurgere a arborilor orientaţi sînt A-preordine, A-postordine şi parcurgerea pe niveluri.
Parcurgerea în A-preordine Modalitatea de vizitare a vîrfurilor în parcurgerea în A-preordine poate fi descrisă astfel. Iniţial, rădăcina arborelui este selectată drept vîrf curent. Este vizitat vîrful curent şi sînt identificaţi descendenţii lui. Se aplică aceeaşi regulă de vizitare pentru arborii avînd ca rădăcini descendenţii vîrfului curent, arborii fiind vizitaţi în ordinea precizată prin numerele ataşate vîrfurilor rădăcină corespunzătoare.
42
Algoritmi și tehnici de programare
43
Exemplu 3.1.14. Pentru arborele orientat din exemplul 3.1.13., prin aplicarea parcurgerii în Apreordine, rezultă: 1,2,5,6,9,10,11,12,13,7,3,4,8,14,15,16. În reprezentarea FIU-FRATE, implementarea parcurgerii în A-preordine este realizată prin următoarea funcţie recursivă, cu parametru de intrare rădăcina arborelui curent. void A_preordine (nod R) { if (R){ vizit (R); A_preordine(FIU[R]); A_preordine(FRATE[R]); } }
În sursa prezentată în paragraful precedent, funcţia A-preordine implementează acest tip de traversare în cazul arborilor orientaţi reprezentaţi prin intermediul structurilor arborescente. Parcurgerea A-postordine Regula de parcurgerea în A-postordine este asemănătoare traversării A-preordine, singura diferenţă fiind aceea că, în acest tip de traversare, rădăcina fiecărui arbore este vizitată după ce au fost vizitate toate celelalte vîrfuri ale arborelui. Exemplu 3.1.15. Pentru arborele orientat din exemplul 3.1.13. ordinea de vizitare a vîrfurilor este: 5,9,10,11,12,13,6,7,2,3,14,15,16,8,4,1. Pentru arbori reprezentaţi prin structuri dinamice de date, implementarea parcurgerii în A-postordine poate fi obţinută pe baza următoarei funcţii recursive. Parametrul de intrare al funcţiei A_postordine reprezintă rădăcina arborelui curent în momentul apelului. void A_postordine (nod R) { if (R) { for(i=0;i
Observaţie Parcurgerile în A-preordine şi A-postordine sînt variante de parcurgeri în adîncime (variante ale metodei DF). Ambele metode consideră prioritare vîrfurile aflate la distanţă maximă faţă de rădăcina arborelui iniţial. Parcurgerea pe niveluri Parcurgerea unui arbore orientat pe niveluri constă în vizitarea vîrfurilor sale în ordinea crescătoare a distanţelor faţă de rădăcină. Exemplu 3.1.16. Pentru arborele definit în exemplul 3.1.13., prin aplicarea parcurgerii pe niveluri, rezultă următoarea ordine de vizitare a nodurilor, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16. Ca şi în cazul metodei BF, implementarea parcurgerii pe niveluri este bazată pe utilizarea unei structuri de coadă C. La momentul iniţial rădăcina arborelui este inserată în C.
44
Metode de programare
Atîta timp cît timp coada este nevidă, este preluat cu ştergere un vîrf din C, este vizitat şi sînt introduşi în coadă descendenţii săi. Calculul este încheiat cînd C=Ø. În cazul reprezentării FIU-FRATE a arborelui de traversat, parcurgerea pe niveluri poate fi implementată prin următoarea funcţie. void parcurgere_pe_niveluri(nod R,int FIU[],int FRATE[],int n) { ptcoada C=NULL;push(C,R); while (C) { pop(C,v); VIZIT(v); v=FIU[v]; while (v){ push(C,v); v=FRATE[v]; } } }
Observaţie Funcţiile push şi pop implementează inserarea unuei celule în coadă, respectiv extragerea unui element al cozii. Exemplu 3.1.17. Pentru arborele de la exemplul 3.1.13., evoluţia algoritmului este,
C t t=1
1
t=2
2
3
4
t=3
3
4
5
6
t=4
4
5
6
7
t=5
5
6
7
8
t=6
6
7
8
t=7
7
8
9
t=8
8
8
9
7
1
1
0
1
1
1
1
0
1
2
1 2
1 3
1 3
44
Algoritmi și tehnici de programare
t=9
t=10
t=11
t=12
t=13
t=14
t=15
t=16
45
9
1
1
1
1
0
1
2
3
1
1
1
1
1
0
1
2
3
4
1
1
1
1
1
1
2
3
4
5
1
1
1
1
1
2
3
4
5
6
1
1
1
1
3
4
5
6
1
1
1
4
5
6
1
1
5
6
1 4 1 5
1 5
1 6
1 6
1 6
1 5
t=17
deci vîrfurile sînt vizitate în ordinea: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16. Observaţie Metoda BF pentru parcurgerea grafurilor este o generalizare a tehnicii de parcurgere pe niveluri a arborilor orientaţi. O alternativă de implementare a parcurgerii pe niveluri poate fi descrisă prin intermediul funcţiilor recursive frati şi parc. Coada C este o variabilă globală şi este iniţializată cu rădăcina arborelui. Parcurgerea este realizată prin apelul parc(C). void frati(v) {if (v){push(C,v); fraţi(FRATE[v]); } } void parc() {if (C){pop(C,v);VIZIT(v); frati(FIU[v]); parc(); } }
46
Metode de programare
3.1.3. Arbori parţiali. Algoritmul Kruskal Definiţia 3.1.10. Fie G un graf. Subgraful parţial H este un arbore parţial al lui G dacă H este graf arbore. Definiţia 3.1.11. Fie G=(V,E,w) un graf ponderat conex.Dacă T=(V,E0) este un arbore parţial al grafului G’=(V,E), ponderea arborelui T, notată W(T), este definită prin w( e ) . W(T)=
eE0
Exemplu 3.1.18. Pentru graful ponderat
1 4 2
8
6
2
9
1
4
3
2
5
12
3
T este un arbore parţial de pondere 32.
1 4
2
3
2
6 8
4
5
9 3
Definiţia 3.1.12. Arborele parţial T0T(G) este arbore parţial minim pentru G dacă W(T0)=min{W(T); TT(G)}, unde T(G) este mulţimea arborilor parţiali corespunzători grafului G. Observaţie Dacă G este graf finit, atunci T(G) este o mulţime finită, deci orice graf finit ponderat şi conex are cel puţin un arbore parţial minim. În continuare este prezentat algoritmul Kruskal pentru determinarea unui arbore parţial minim al unui graf ponderat conex G=(V,E,w). Pas 1: i=1; E0= Pas 2: Determină R={e/eE \ Ei-1 astfel încît graful (V,Ei-1 {e}) este aciclic} Dacă R=, atunci stop; altfel, selectează eiR cu w(ei)=min{w(e), eR}; Ei=Ei{e } 1 i
46
Algoritmi și tehnici de programare
47
Pas 3: i=i+1 şi reia pasul 2. Arborele parţial de cost minim al grafului G este (V,Ei-1). Pentru implementarea algoritmului Kruskal, graful conex ponderat este reprezentat sub formă tabelară, muchiile fiind ordonate crescător după ponderi. Muchiile selectate de algoritm pot fi menţinute de asemenea într-o structură tabelară, sau doar marcate ca fiind incluse în mulţimea de muchii din arborele parţial minim a cărui construcţie este dorită. În varianta prezentată în continuare muchiile selectate sînt afişate. Verificarea condiţiei ca muchia selectată să nu formeze nici un ciclu cu muchiile selectate la etapele precedente este realizată prin utilizarea un vector TATA, definit astfel. Pentru fiecare vîrf i (vîrfurile grafului fiind numerotate de la 1 la n, unde n este numărul de noduri ale grafului), componenta TATA [i] este predecesorul său în arborele care conţine vîrful i construit pînă la momentul curent dacă i nu este rădăcina acelui arbore, respectiv TATA[i] este egal cu –numărul de vîrfuri ale arborelui de rădăcină i, în caz contrar. Componentele vectorului TATA sînt iniţializate cu valoarea -1. Calculul care realizează adăugarea unei noi muchii poate fi descris astfel. Este determinată o muchie de cost minim e=v1v2 care nu a fost selectată anterior. Dacă vîrfurile v1 şi v2 nu aparţin aceluiaşi arbore, atunci proprietatea de aciclicitate este îndeplinită şi muchia e este adăugată la structura curentă. Adăugarea muchiei e selectate este realizată prin reunirea arborilor din care fac parte v1 şi v2 de rădăcini r1, respectiv r2, astfel: dacă TATA[r1]
48
Metode de programare
int nv,nm, a[100][3]; printf("Numarul de varfuri:");scanf("%i",&nv); printf("Numarul de muchii");scanf("%i",&nm); printf("Matricea de reprezentare\n"); for(int i=0;i
Exemplu 3.1.19. Evoluţia determinată de program pentru graful 1 4
2
2
2
8
6
8
1
3
9
4 4
3
2 2 1 1 5 A 3 1 4 5 3
3 4 6 5 4 2 6 6 6
1 2 2 3 4 4 8 8 9
este: i, j după cea de-a t-a iteraţie
muchia selectată
t=0
TATA
Costul
(-1,-1,-1,-1,-1,-1)
t=1,i=0,j=0
(2,3)
(-1,-2,2,-1,-1,-1)
1
t=2,i=1,j=1
(2,4)
(-1,-3,2,2,-1,-1)
2
t=3,i=2,j=2
(1,6)
(-2,-3,2,2,-1,1)
2
t=4,i=3,j=3
(1,5)
(-3,-3,2,2,1,1)
3
t=5,i=4,j=4 t=6,i=4,j=5
(-3,-3,2,2,1,1) (1,2)
(-5,1,1,2,1,1)
MUCHIILE ARBORELUI MINIM: {(2,3),(2,4),(1,6),(1,5),(1,2)}
4 COSTUL: 12
48
Algoritmi și tehnici de programare
49
3.2. Arbori binari 3.2.1. Reprezentarea arborilor binari. Modalităţi de parcurgere Definiţia 3.2.1. Un arbore binar este un arbore orientat cu proprietatea că pentru orice vîrf v, od(v)2. Dacă od(v)=2, cei doi descendenţi sînt desemnaţi ca descendent stîng (fiu stînga) respectiv descendent drept (fiu dreapta). Pentru vîrfurile cu od(v)=1, unicul descendent este specificat fie ca fiu stînga, fie ca fiu dreapta. Definiţia 3.1.2. Se numeşte nod terminal orice vîrf v al arborelui cu od(v)=0. În caz contrar nodul v este neterminal. Reprezentarea unui arbore binar este realizată printr-o structură arborescentă. Pentru fiecare nod N al arborelui binar sînt memorate informaţia asociată lui N şi legăturile către descendenţii lui. Absenţa unui descendent este reprezentată prin NULL. identificator legătură fiu legătură fiu nod stîng drept Definiţia 3.2.3. Fie T=(V,E) un arbore binar cu rădăcina R. Subarborele stîng al lui T este ST=(V\{R},E\{RS}), unde S este fiul stînga al rădăcinii. Subarborele drept al lui T este DT=(V\{R},E\{RD}), unde D este fiul dreapta al rădăcinii. Exemplu 3.2.1. Pentru arborele binar,
1 2
3
4
5 8
6
7
9
10
subarborii rădăcinii sînt:
2
3
4
6
5 8
Subarbore stîng
9
7
10 Subarbore drept
În plus faţă de metodele A-preordine, A-postordine şi pe niveluri, parcurgerile în preordine (RSD), inordine (SRD) şi respectiv postordine (SDR) sînt special considerate pentru arbori binari şi au multiple aplicaţii. Regula de vizitare pentru aceste tipuri de parcurgere revine la parcurgerea subarborelui stîng şi parcurgerea subarborelui drept corespunzători vîrfului curent. La momentul iniţial vîrful curent este rădăcina arborelui. Diferenţa dintre cele trei tipuri de parcurgere este dată de momentul în care devine vizitat fiecare vîrf al arborelui. În parcurgerea RSD (rădăcină-subarbore stîng-subarbore drept), fiecare vîrf al arborelui este vizitat în momentul în care este vîrf curent; în parcurgerea SRD, vizitarea vîrfului curent R este efectuată după ce a fost parcurs subarborele stîng al lui R, respectiv în parcurgerea SDR vizitarea fiecărui vîrf este efectuată după ce au fost parcurşi subarborii aferenţi lui.
50
Metode de programare
Exemplu 3.2.2. Pentru arborele de la exemplul 3.2.1., secvenţele de vîrfuri rezultate prin aplicarea parcurgerilor RSD, SRD, SDR sînt: - preordine: 1,2,4,8,5,3,6,9,10,7 - inordine: 4,8,2,5,1,9,6,10,3,7 - postordine: 8,4,5,2,9,10,6,7,3,1.
3.2.2. Arbori de sortare Definiţia 3.2.4. Un arbore de sortare este un arbore binar cu următoarele proprietăţi, - fiecărui nod i al arborelui îi este ataşată o informaţie INF(i) dintr-o mulţime ordonată de valori; - pentru fiecare nod i, INF(i) este mai mare decît INF(j), pentru toate nodurile j din subarborele stîng al arborelui cu rădăcină i; - pentru fiecare nod i, INF(i) este mai mică decît INF(j), pentru toate nodurile j din subarborele drept al arborelui cu rădăcină i; - pentru orice vîrfuri i şi j daca ij atunci INF(i)INF(j). Exemplu 3.2.3. Arborele binar
50
30 10
70 40
20
90 80
este arbore de sortare. Operaţiile primitive asupra arborilor de sortare sînt inserarea unui nod, ştergerea unui nod şi parcurgerea arborelui (în preordine, inordine sau postordine). Inserarea şi ştergerea de noduri aplicate unui arbore de sortare trebuie realizate astfel încît arborele rezultat să fie de asemenea arbore de sortare. Observaţie Parcurgerea în inordine a unui arbore de sortare determină obţinerea secvenţei informaţiilor asociate vîrfurilor arborelui în ordine crescătoare. Inserarea unui nod într-un arbore de sortare Algoritmul de inserare a unei informaţii nr în arborele de sortare de rădăcină rad este recursiv şi constă în efectuarea următoarelor operaţii: vîrful curent v la momentul iniţial este rădăcina arborelui; dacă arborele de rădăcină v este vid, este generat arborele cu un singur nod, cu informaţia ataşată nr; altfel: - dacă informaţia ataşată nodului v este mai mare decît nr, atunci vîrf curent devine fiul stînga al lui v; - dacă informaţia ataşată nodului v este egală cu nr, atunci stop; - dacă informaţia ataşată nodului v este mai mică decît nr, atunci vîrf curent devine fiul dreapta al lui v.
50
Algoritmi și tehnici de programare
51
Exemplu 3.2.4. Aplicarea algoritmul descris pentru inserarea informaţiei 55 în arborele de sortare din exemplul 3.2.3. determină următoarele operaţii, INF(v)=50; 50<55, inserează în subarborele cu rădăcina avînd informaţia ataşată 70. INF(v)=70; 70>55, inserează în subarborele stîng cu rădăcina NULL. Este creat nodul cu informaţie 55, fiu stîng al nodului de informaţie 70. Arborele rezultat este
50
30 10
70 40
20
90
55 80
Ştergerea unei informaţii dintr-un arbore de sortare Algoritmul pentru ştergerea unei informaţii nr din arborele de sortare de rădăcină rad este recursiv şi poate fi descris astfel. Vîrful curent v la momentul iniţial este rădăcina arborelui. 1. dacă arborele este vid atunci stop; 2. altfel a) dacă informaţia ataşată nodului v este mai mare decît nr, atunci vîrful curent devine fiul stînga al lui v; b) dacă informaţia ataşată nodului v este mai mică decît nr, vîrful curent devine fiul dreapta al lui v; c) dacă INF(v)=nr atunci: c1) dacă subarborele stîng este vid, atunci adresa vîrfului v este memorată într-o celulă suplimentară aux, v devine fiul dreapta al lui v, iar celula aux este eliberată din memorie; c2) dacă subarborele stîng este nevid atunci se determină cel mai mare element din subarborele stîng; c2.1) dacă fiul stînga al lui v nu are subarbore drept, atunci informaţia ataşată fiului stînga se transferă în vîrful curent, iar fiul stînga este înlocuit cu fiul său stînga şi este eliberată memoria corespunzătoare celulei v->fius; c2.2) altfel, se transferă în rădăcină informaţia ataşată ultimului nod p determinat la c2), nodul p este înlocuit cu fiul său stîng şi celula corespunzătoare lui p este eliberată din memorie. Exemplu 3.2.5. Ştergerea informaţiei 70 din arborele de sortare din exemplul 3.2.4. este realizată astfel: 70>50, decide ştergerea din subarborele drept 70=70, decide ştergerea din arborele curent: rădăcina etichetată cu 70; există subarbore stîng iar acesta nu are subarbore drept- nodul cu informaţie 70 este etichetat cu 55, iar p este înlocuit cu subarborele său stîng (vid). Arborele rezultat
52
Metode de programare
50
30 10
55 40
20
90 80
este arbore de sortare. Observaţie Punctul c) de la pasul 2 al algoritmului de eliminare a unei informaţii dintr-un arbore de sortare poate fi înlocuit cu: c) dacă INF(v)=nr atunci: c1) dacă subarborele drept este vid, atunci adresa vîrfului v este memorată într-o celulă suplimentară aux, v devine fiul stînga al lui v, iar celula aux este eliberată din memorie; c2) dacă subarborele drept este nevid atunci se determină cel mai mic element din subarborele drept, altfel c2.1.) dacă fiul dreapta al lui v nu are subarbore stîng, atunci informaţia ataşată fiului dreapta este transferată în vîrful curent, iar fiul dreapta este înlocuit cu fiul său dreapta şi este eliberată memoria corespunzătoare celulei v->fiud. c2.2) altfel, se transferă în rădăcină informaţia ataşată ultimului nod p determinat la c2), nodul p este înlocuit cu fiul său dreapta şi celula corespunzătoare lui p este eliberată din memorie. În următoarea sursă C sînt implementaţi algoritmii de adăugare şi ştergere în arbori de sortare. #include<stdio.h> #include
52
Algoritmi și tehnici de programare if(*radacina==NULL) return 0; else if((*radacina)->inf>info) return extragere(&((*radacina)->l),info); else if((*radacina)->inf
53
54
Metode de programare
3.2.3. Arbori de structură Expresiile aritmetice în care intervin numai operatori binari pot fi reprezentate prin intermediul arborilor binari în care fiecare nod neterminal are doi fii. Definiţia 3.2.5. Un arbore de structură are vîrfurile etichetate astfel: - fiecare nod neterminal este etichetat cu un simbol corespunzător unuia dintre operatori; - fiecare nod terminal este etichetat cu un operand. Construcţia arborelui de structură corespunzător unei expresii aritmetice date se realizează pe baza parantezării existente în expresie şi a priorităţilor convenţional asociate operatorilor (ordinea operaţiilor) astfel încît rădăcina fiecărui subarbore este etichetată cu operatorul care se execută ultimul în evaluarea subexpresiei corespunzătoare acelui subarbore. Exemplu 3.2.6. Pentru expresia matematică (a+b)*(c-d)+e/g, arborele de structură corespunzător este
+
/
* + a
b
c
e
g
d
Construcţia arborelui de structură pentru o expresie s este realizată în două etape: 1. ataşarea de priorităţi operatorilor şi operanzilor; priorităţile ataşate permit eliminarea parantezelor fără ca semnificaţia expresiei să se modifice; 2. construcţia propriu-zisă. Prima etapă este realizată astfel: prioritatea iniţială a operatorilor ‘+’,’-‘ este 1 (dacă expresia nu conţine paranteze atunci în construcţie aceşti operatori vor fi primii luaţi în considerare în ordinea de la dreapta la stînga); - prioritatea iniţială a operatorilor ‘/’,’*‘ este 10 (dacă expresia nu conţine paranteze, aceştia sînt consideraţi după operatorii de prioritate 1 în ordinea de la dreapta la stînga); - prioritatea fiecărui operator este incrementată cu valoarea 10 pentru fiecare pereche de paranteze în interiorul cărora se află; - prioritatea ataşată fiecărui operand este MAXINT. După stabilirea sistemului de priorităţi sînt eliminate parantezele din expresie, ordinea de efectuare a operaţiilor în cadrul expresiei fiind indicată de vectorul de priorităţi ataşat. Construcţia arborelui de structură pe baza expresiei s din care au fost eliminate parantezele şi a vectorului de priorităţi, poate fi realizează recursiv în modul următor (la momentul iniţial expresia curentă este expresia dată): - pentru expresia curentă se determină operatorul/operandul de prioritate minimă care se ataşează ca etichetă a rădăcinii r a subarborelui de structură corespunzător ei; fie i poziţia acestuia în cadrul expresiei; -
54
Algoritmi și tehnici de programare
-
55
dacă expresia are un singur simbol, atunci r->fius=r->fiud=NULL; altfel, se consideră subexpresiile s1 şi s2, constînd din simbolurile de pe poziţiile 0 pînă la i-1 şi respectiv i+1 pînă la lungimea şirului s.; arborii de structură corespunzători subexpresiilor s1 şi s2 se ataşează ca subarbore stîng, respectiv subarbore drept vîrfului r.
Exemplu 3.2.7. Etapele calculului sistemului de priorităţi şi al arborelui de structură pentru expresia de la exemplul 3.2.6. pot fi descrise astfel, Dim 1 2 3 3 4 4 5 6 7 7 8 9 10 11
vectorul prioritate (MAXINT) (MAXINT,11) (MAXINT,11,MAXINT) (MAXINT,11,MAXINT) (MAXINT,11,MAXINT,10) (MAXINT,11,MAXINT,10) (MAXINT,11,MAXINT,10,MAXINT) (MAXINT,11,MAXINT,10,MAXINT,11) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT,1) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT,1,MAXINT) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT,1,MAXINT,10) (MAXINT,11,MAXINT,10,MAXINT,11,MAXINT,1,MAXINT,10,MAXINT)
După eliminarea parantezelor, expresia rezultată este s=a+b*c-d+e/g. Arborele de structură este construit astfel:
+ +
în construcţie
* în construcţie
în construcţie
în construcţie
în construcţie +
+
* + în construcţie
în construcţie
*
în construcţie în construcţie
+ a
în construcţie
în construcţie
în construcţie
56
Metode de programare
+
în construcţie
*
în construcţie
*
în construcţie
+ a
+
+ a
b
în construcţie
b
+
+ a
+
în construcţie
*
+
-
în construcţie a
c
în construcţie
*
b
în construcţie
b
c
d
+
/
* + a
b
în construcţie
în construcţie
d
c
+
/
* + a
e
b
c
în construcţie
d
56
Algoritmi și tehnici de programare
57
+
/
* + a
b
c
e
g
d
Observaţie Construcţia arborelui de structură poate fi realizată în ipoteza în care expresia este corectă. Definiţia 3.2.6. Se numeşte forma poloneză directă a unei expresii, expresia rezultată în urma parcurgerii RSD a arborelui de structură. Se numeşte forma poloneză inversă a unei expresii, expresia rezultată în urma parcurgerii SDR a arborelui de structură. Exemplu 3.2.8. Pentru expresia considerată la exemplul 3.2.7., forma poloneză directă este +*+abcd/eg. Forma poloneză inversă a expresiei date este ab+cd-*eg/+. Observaţie Parcurgerea arborelui în inordine determină secvenţa de simboluri rezultată prin eliminarea parantezelor din expresia dată. Restaurarea unei forme parantezate poate fi realizată printr-o parcurgere SRD şi anume în modul următor. La momentul iniţial vîrful curent este rădăcina arborelui de structură. Dacă vîrful curent v nu este vîrf terminal, atunci se generează (s1) eticheta(v)(s2), unde eticheta(v) este operatorul etichetă a vîrfului, s1 este secvenţa rezultată prin traversarea SRD a subarborelui stîng, s2 este secvenţa rezultată prin traversarea SRD a subarborelui drept. Dacă v este vîrf terminal atunci este generată secvenţa eticheta(v). Evaluarea expresiilor aritmetice pe baza arborilor de structură Traversarea SRD a arborelui de structură ataşat unei expresii aritmetice permite evaluarea expresiei pentru valorile curente corespunzătoare variabilelor. Evaluarea poate fi efectuată în mod recursiv astfel. La momentul iniţial vîrful curent este rădăcina arborelui. Dacă v este vîrf curent atunci noua informaţie asociată lui v este: - val(eticheta(v)), dacă v este vîrf terminal; - val(s1)eticheta(v)val(s2), dacă v este neterminal, unde val(s1), val(s2) sînt valorile rezultate prin evaluările subarborilor stîng şi respectiv drept ai lui v, val(eticheta(v)) este valoarea curentă a variabilei, dacă eticheta lui v este variabilă, respectiv valoarea constantei, dacă eticheta lui v este o constantă. Exemplu 3.2.9. Prin aplicarea metodei de evaluare descrise pentru a=3, b=2, c=5, d=2, e=6 şi g=2, obţinem:
58
Metode de programare
18
3
15 5 3
3 2
5
6
2
2
Construcţia arborelui de structură asociat unei expresii şi evaluarea expresiei pentru valori date ale operanzilor pot fi implementate prin intermediul următoarei surse C. #include<stdio.h> #include
58
Algoritmi și tehnici de programare cr_arb_str(&((*rad)->l),p,poz-1,s,pri); cr_arb_str(&((*rad)->r),poz+1,u,s,pri); } } void forma_poloneza(arbore rad) { if(rad){ printf("%c",rad->inf); forma_poloneza(rad->l); forma_poloneza(rad->r); } } float eval(arbore rad) { char s[1]; if(rad){ if((rad->r==rad->l)&&(rad->l==NULL))return rad->v; else{ switch (rad->inf){ case '+':rad->v=eval(rad->l)+eval(rad->r);break; case '-':rad->v=eval(rad->l)-eval(rad->r);break; case '*':rad->v=eval(rad->l)*eval(rad->r);break; case '/':rad->v=eval(rad->l)/eval(rad->r);break; } return rad->v; } } } void atribuie_arbore(arbore rad) { if(rad){ if((rad->r==rad->l)&&(rad->l==NULL)){ printf("%c =",rad->inf); float t; scanf("%f",&t); rad->v=t; } else {atribuie_arbore(rad->l); atribuie_arbore(rad->r); } } } void main() { clrscr(); char s[100]; int p[100]; arbore radacina=NULL; printf("Expresia:"); scanf("%s",&s); prioritati(s,p); int n=strlen(s); cr_arb_str(&radacina,0,n-1,s,p); printf("\nForma poloneza inversa "); forma_poloneza(radacina); printf("\n Valori pentru varabile\n"); atribuie_arbore(radacina); printf("\nEvaluarea: %7.3f",eval(radacina)); getch(); }
59
60
Metode de programare
Bibliografie 1. [Aho, Hop şa] Aho A., Hopcroft J., Ullman J., Data Structures and Algorithms, Addison-Wesley, 1983 2. [Bras, Brat] Brassard G., Bratley P., Algoritmics: Theory and Practice, Prentice-Hall, 1988 3. [Cor, Lei şa] Cormen T., Leiserson C., Rivest R., Introduction to Algorithms, MIT Press, sixteenth printing, 1996 4. [Gon] Gonnet G.H., Handbook of Algorithms and Date Structures, Addison-Wesley, 1984 5. [Hor] Horowitz E., Sahni S., Fundamentals of Computer Algorithms, Computer Science Press, 1978 6. [Knu] Knuth D., Fundamental Algorithms, vol 1 of The Art of Computer Programming, Addison-Wesley, 1973 7. [Knu] Knuth D., Sorting and Searching, vol 3 of The Art of Computer Programming, Addison-Wesley, 1973 8. [Man] Manmber U., Introduction to Algorithms: A Creative Approach, AddisonWesley, 1989 9. [Pop, Geo şa] Popovici Ct., Georgescu H., State L., Bazele informaticii, vol 1, Tip. Universităţii din Bucureşti, 1990 10. [Tom] Tomescu I.., Probleme de combinatorică şi teoria grafurilor, Editura Didactică şi Pedagogică, Bucureşti, 1981 11. [Tud] Tudor S., Tehnici de programare, Ed. Teora, 1994 12. [Wil] Wilf H., Algorithms and Complexity, Prentice-Hall, 1986 13. [Negrescu, 1994] Liviu Negrescu, Limbajele C şi C++ pentru începători, Editura Microinfomatica, Cluj-Napoca, 1994 14. [Smeureanu, 1995] Ion Smeureanu, Ion Ivan, Marian Dârdală, Limbajul C/C++ prin exemple, Editura Cison, Bucureşti 1995 15. [Ghilic, 2003] Bogdan Ghilic-Micu, Ion Gh. Roşca, Constantin Apostol, Marian Stoica, Cătălina Lucia Cocianu, Algoritmi în programare, Editura ASE, Bucureşti 2003
60
Related Documents
Atp Id - Grafuri.pdf
November 2019 13
Atp
July 2020 14
Atp Officer
June 2020 10
Atp Clerk
June 2020 10
Atp Synthase
November 2019 15
Atp Iii
November 2019 10More Documents from ""
Atp Id - Grafuri.pdf
November 2019 13
Cerinte Atp Id.docx
November 2019 8
Contour Cutting Guide In Photoprint 6
December 2019 6
3.pdf
November 2019 20
