Lista ierarhică
De fapt, acest mod de a reprezenta grafice este doar o implementare internă a listei de adjacități. într-o listă liniară există numere de "vârfuri inițiale", iar în rest - numere de vârfuri adiacente sau indicatori către aceste vârfuri. Ca exemplu (a se vedea Figura 11.11), oferim o listă ierarhică. definirea digraphului. prezentat în Fig. 11.6.
Fig. 11.11. Exemplu de listă ierarhică
tip uk_versh = ^ vershina;
uk_duga = ^ duga;
vershina = înregistrare
număr. integer;
sled_vershina. uk_versh;
spisok_dug. uk_duga
se încheie;
duga = înregistrare
konec_dugi. uk_versh;
sled_duga. uk_duga;
se încheie;
Avantajul evident al acestui mod de a reprezenta grafice este utilizarea economică a memoriei. Și chiar o mică redundanță a datelor, la care trebuie să se recurgă în cazul unui grafic nedirecționat. setând fiecare margine ca două arce. este răscumpărată de flexibilitatea întregii structuri, ceea ce este deosebit de convenabil dacă aveți nevoie de reconstrucție frecventă în cadrul programului.
Dacă adăugați câmpuri la descrierile tipului de date date care ar putea stoca greutățile de vârfuri și arce. apoi în același mod putem specifica și grafice ponderate (digraphs).
Un arbore este un caz special al unui grafic. utilizate cel mai mult în programare.
Definiții de bază
Sunt destul de puțini copaci echivalenți. aici sunt doar câteva dintre ele.
- Un arbore este un grafic conectat fără cicluri.
- Un arbore este un grafic conectat. în care pentru N nodurile există întotdeauna exact o muchie N-1.
- Un arbore este un grafic. între oricare dintre cele două vârfuri din care există o singură cale.
În mod similar, un arbore orientat este definit ca un digraph. în care nu există mai mult de o cale între două vârfuri.
Tabelul 11.4. Exemple de copaci
Fig. 11.12. Înălțimea copacului 3
Vom studia și vom folosi doar un singur caz particular de arbori orientați - arborii rădăcini (vezi Figura 11.12).
Arborele rădăcină este un arbore orientat. în care se pot distinge vârfuri de trei tipuri: rădăcina. frunze (alt nume: noduri terminale) și alte noduri (nonterminale); și două condiții obligatorii trebuie îndeplinite:
- nu arce lasă frunzele; de la alte noduri pot exista cât mai multe arce pe care le doriți;
- nici un arc nu intră în rădăcină; toate celelalte vârfuri vin într-un singur arc.
În mod tradițional, matematică și științe legate de acesta (inclusiv programarea teoretice) copacii „cresc“ cu susul în jos: se face numai pentru frunze de prelungire comoditate, dacă este necesar. Astfel, în figuri, rădăcina copacului este vârful cel mai de sus. iar frunzele sunt cele mai mici.
Vârful vârfului v este vârful. din care emană arcul. introducerea vârfului v. Descendentul vârfului v este vârful. în care vine arcul. provenind de la vârful v. În aceste condiții, puteți da alte definiții conceptelor de rădăcină și foaie. rădăcina nu are strămoși. foaia nu are descendenți.
Un arbore binar este un copac rădăcină. fiecare vârf al căruia nu are mai mult de doi copii. În acest caz, uneori vorbesc despre copilul din stânga și despre copilul potrivit pentru vârful actual.
Înălțimea arborelui rădăcină reprezintă numărul maxim de arce. separând frunzele de rădăcină. Dacă arborele nu este ponderat, atunci înălțimea acestuia este doar distanța de la rădăcină la cea mai exterioară coală.
În concluzie, vom da o definiție care leagă grafice arbitrare copacilor mai dens.
Scheletul unui grafic este un copac. Aceasta se obține după ce s-au îndepărtat niște margini din grafic (a se vedea figura 11.13).
Fig. 11.13. Concepția scheletului
Articole similare
Trimiteți-le prietenilor: