Cuprins
- 8.Arbori
- 8.1. Arbori generalizaţi
- 8.1.1. Definiţii
- 8.1.2. Tipul de date abstract arbore generalizat
- 8.1.3. Traversarea arborilor generalizaţi
- 8.1.3.1. Traversarea arborilor generalizaţi prin tehnici bazate pe
- căutarea în adâncime: preordine, inordine şi postordine
- 8.1.3.2. Traversarea arborilor generalizaţi prin tehnica căutării prin
- cuprindere
- 8.1.4. Tehnici de implementare a TDA arbore generalizat
- 8.1.4.1. Implementarea arborilor generalizaţi cu ajutorul tablourilor
- 8.1.4.2. Implementarea arborilor generalizaţi cu ajutorul listelor
- 8.1.4.3. Implementarea structurii arbore generalizat pe baza
- relaţiilor “primul-fiu” şi “frate-dreapta”
- 8.2. Arbori binari
- 8.2.1. Definiţii
- 8.2.2. Tehnica transformării unei structuri de arbore generalizat într-o
- structură de arbore binar
- 8.2.3. TDA Arbore binar
- 8.2.4. Tehnici de implementare a arborilor binari
- 8.2.4.1. Implementarea arborilor binari cu ajutorul structurii tablou
- 8.2.4.2. Implementarea arborilor binari cu ajutorul pointerilor
- 8.2.5. Traversarea arborilor binari
- 8.2.5.1. Traversarea arborilor binari prin tehnici bazate pe căutarea
- în adâncime
- 8.2.5.2. Traversarea arborilor binari prin tehnica căutări prin
- cuprindere
- 8.2.6. Aplicaţii ale arborilor binari
- 8.2.6.1. Construcţia şi reprezentarea grafică a unui arbore binar
- de înălţime minimă
- 8.3. Arbori binari ordonaţi
- 8.3.1. Definiţii
- 8.3.2. Tipul de date abstract arbore binar ordonat
- 8.3.3. Tehnici de căutare în arbori binari ordonaţi
- 8.3.4. Inserţia nodurilor în ABO. Crearea arborilor binari ordonaţi
- 8.3.5. Suprimarea nodurilo în ABO
- 8.3.6. Analiza căutarii în ABO
- 8.3.7. Arbori binari parţial ordonaţi
- 8.3.8. Aplicaţii ale ABO.
- 8.3.8.1. Problema concordanţei
- 8.4 Arbori binari echilibraţi AVL
- 8.4.1. Definirea arborilor echilibraţi AVL
- 8.4.2. Inserţia nodurilor în arbori echilibraţi AVL
- 8.4.3. Suprimarea nodurilor în arbori echilibraţi AVL
- 8.5. Arbori multicăi
- 8.5.1. Generalităţi
- 8.5.2. Arbori-B
- 8.5.2.1. Definire
- 8.5.2.2. Căutarea cheilor în arbori-B
- 8.5.2.3. Inserţia nodurilor în arbori-B
- 8.5.2.4. Suprimarea nodurilor în arbori-B
- 10. Structura de date graf
- 10.1. Definiţii
- 10.2. Tipul de date abstract graf
- 10.2.1. TDA graf. Varianta 1 (Shiflet)
- 10.2.2. TDA graf. Varianta 2 (Decker)
- 10.3. Tehnici de implementare a tipului de date abstract graf
- 10.3.1. Implementarea grafurilor cu ajutorul matricilor de adiacenţe
- 10.3.1.1. Studiu de caz 1
- 10.3.1.2. Studiu de caz 2
- 10.3.2. Implementarea grafurilor cu ajutorul structurilor de adiacenţe
- 10.3.2.1. Studiu de caz 1
- 10.3.2.2. Studiu de caz 2
- 10.3.2.3. Studiu de caz 3
- 10.3.3. Considerente referitoare la stabilirea modului de reprezentare a
- unui TDA graf.
- 10.4. Tehnici fundamentale de traversare a grafurilor
- 10.4.1. Traversarea grafurilor prin tehnica căutării ”în adâncime” (”Depth-
- First Search”)
- 10.4.1.1. Căutarea "în adâncime", varianta CLR
- 10.4.1.2. Căutare ”în adâncime” în grafuri reprezentate prin
- structuri de adiacenţe
- 10.4.1.3. Căutare ”în adâncime” în grafuri reprezentate prin
- matrici de adiacenţe
- 10.4.1.4. Căutare ”în adâncime” nerecursivă
- 10.4.1.5. Analiza căutării ”în adâncime”
- 10.4.2. Traversarea grafurilor prin tehnica căutării ”prin cuprindere”
- (”Breadth-First Search”)
- 10.4.2.1. Căutarea "prin cuprindere", varianta CLR
- 10.4.2.2. Căutare ”prin cuprindere” în grafuri reprezentate prin
- structuri de adiacenţe
- 10.4.2.3. Analiza căutării ”prin cuprindere”
- 10.4.3. Comparaţie între tehnicile fundamentale de traversare a grafurilor
- 10.5. Aplicaţii ale traversării grafurilor
- 10.5.2. Grafuri şi conexiuni
- 10.5.2.1. Determinarea componenetelor conexe ale unui
- graf
- 10.5.2.2. Puncte de articulaţie şi componente biconexe
- 10.5.2.3. Determinarea punctelor de articulaţie ale unui graf
- 10.6. Aplicaţii
- 11. Grafuri ponderate ("Weighted Graphs")
- 11.1. Arbori de acoperirie minimi ("Minimum-Cost Spanning Trees")
- 11.1.1. Proprietatea arborilor de acoperire minimi
- 11.2. Determinarea arborilor de acoperirie minimi
- 11.2.1. Algoritmul lui Prim
- 11.2.1.1. Exemplu de implementare a algoritmului lui Prim
- 11.2.2. Metoda căutării "bazate pe prioritate" ("Priority-First Search")
- 11.2.2.1. Consideraţii referitoare la metoda căutării "bazate pe
- prioritate"
- 11.2.3. Algoritmul lui Kruskal
- 11.2.3.1. Exemplu de implementare a algoritmului lui Kruskal
- 11.3. Drumul minim ("Shortest Path")
- 11.3.1. Determinarea drumurilor minime cu origine unică corespunzătoare unui
- nod al unui graf prin tehnica căutării "bazate pe prioritate"
- 11.4. Arbori de acoperire şi drumuri minime în grafuri dense
- 11.5. Considerente referitoare la performanţele comparate ale algoritmilor de
- determinare a arborilor de acoperire minimi
- 11.6. Aplicaţii
- 12. Grafuri orientate
Extras din curs
8. Arbori
8.1. Arbori generalizaţi
8.1.1. Definiţii
În definirea noţiunii de arbore se porneşte de la noţiunea de vector.
Fie V o mulţime având elementele a1, a2,....an.
Pe mulţimea V se poate defini o aşa numită "relaţie de precedenţă" în felul următor: se spune că ai precede pe aj dacă i < j. Aceasta se notează: aipaj.
Se poate verifica uşor că relaţia astfel definită are următoarele proprietăţi, valabile pentru structura de vector:
(1) Oricare ar fi a∈V avem aa. (S-a notat cu relaţia "nu precede");
pp
(2) Dacă apb şi bpc atunci ac (tranzitivitate); [8.1.1.a] p
(3) Oricare ar fi a∈V şi b∈V, dacă a≠b atunci avem fie ab fie ba. pp
Din proprietăţile (1) şi (2) rezultă că relaţia de precedenţă nu determină în V ”bucle închise”, adică nu există nici o secvenţă de elemente care se preced două câte două şi în care ultimul element este acelaşi cu primul, cum ar fi de exemplu abcda. pppp
Proprietatea (3) precizează că relaţia de precedenţă este definită pentru oricare două elemente a şi b ale lui V, cu singura condiţie ca a≠b.
Fie V o mulţime finită peste elementele căreia s-a definit o relaţie de precedenţă, stabilind referitor la fiecare pereche de elemente, care dintre ele îl precede pe celalălalt.
Dacă această relaţie posedă proprietăţile [8.1.1.a], atunci ea imprima peste mulţimea V o structură de vector (fig.8.1.1.a).
a b cde
Fig. 8.1.1.a. Structură de vector
În figura 8.1.1.b apare o altă reprezentare intuitivă a unei structuri de vector. Săgeţile din figură indică relaţia "succesor".
a b c d e
Fig.8.1.1.b. Relaţia succesor
Această relaţie se defineşte cu ajutorul relaţiei de precedenţă după cum urmează: dacă între elementele a şi b ale lui V este valabilă relaţia ab şi nu există nici un c∈V astfel ca acb atunci se zice că b este succesorul lui a. ppp
Se observă că relaţia "succesor" (mulţimea săgeţilor din figura 8.1.1.b.), precizează relaţia "precedenţă" fără a fi însă identică cu ea. Spre exemplu, există relaţia be (prin tranzitivitate), dar nici o săgeată nu conectează pe b cu e. p
În figura8.1.1.c apare o aşa numită structură de arbore care se defineşte prin generalizarea structurii de vector.
b cdg hf e ijnol k m ap nivelul 1 nivelul 2 nivelul 3 nivelul 4 nivelul 5
Fig. 8.1.1.c. Structură de arbore
Astfel, dacă în cazul vectorului, toate elementele cu excepţia ultimului au exact un succesor, la structura de arbore se admite ca fiecare element să aibă un număr oarecare de succesori, inclusiv zero, cu restricţia ca două elemente distincte să nu aibă acelaşi succesor.
Relaţia succesor defineşte o relaţie de precedenţă pe structura de arbore. Astfel, din figura avem bp, dn, etc. pp
Relaţia de precedenţă definită pe structura de arbore se bucură de proprietăţile (1) şi (2) de la [8.1.1.a] dar nu satisface proprietatea (3).
Într-adevăr în figura 8.1.1.c, pentru elementele b şi c nu este valabilă nici una din relaţiile bc sau cb, la fel pentru elementele d şi k. Prin urmare, relaţia de precedenţă este definită numai pentru o parte a perechilor de elemente ale arborelui, cu alte cuvinte este o relaţie parţială. pp
În general, o structură de arbore se defineşte ca o mulţime A de n≤0 noduri de acelaşi tip, peste care s-a definit o relaţie de precedenţă având proprietăţile (1) şi (2) de la [8.1.1.a] precum şi următoarele două proprietăţi [8.1.1b]:
(3) Oricare ar fi b,c∈A, astfel încît bpc şi cb, dacă bd şi ce atunci d
pp≠e. Cu alte cuvinte, două elemente oarecare între care nu există relaţia de precedeţă nu pot avea acelaşi succesor. [8.1.1.b]
(4) Dacă A nu este vidă (n >0) atunci există un element numit rădăcină, care precede toate celelalte elemente.
Pentru structura de arbore se poate formula şi o altă definiţie echivalentă cu cea de mai sus.
Prin arbore, se înţelege o mulţime de n0 noduri de acelaşi tip, care dacă nu este vidă, atunci are un anumit nod numit rădăcină, iar restul nodurilor formează un număr finit de arbori, doi câte doi disjuncţi. ≥
Se constată că atât această definiţie, cât şi structura pe care o defineşte, sunt recursive, lucru deosebit de important deoarece permite prelucrarea simplă a unei astfel de structuri cu ajutorul unor algoritmi recursivi.
Preview document
Conținut arhivă zip
- SlaviciCap08-1.pdf
- SlaviciCap08-2.pdf
- SlaviciCap08-3.pdf
- SlaviciCap10.pdf
- SlaviciCap11.pdf
- SlaviciCap12.pdf
- Slavici-Cuprins.pdf
- Slavici-Introducere.pdf