Arbori Si Grafuri

4 ARBORI ŞI GRAFURI 4.1 Arbori binari Fiind dată o mulţime M de elemente denumite noduri sau vârfuri, vom numi arbore (după Knuth) un set finit de noduri astfel încât: a) există un nod cu destinaţie specială, numit rădăcina arborelui; b) celelalte noduri sunt repartizate în m≥ 0 seturi disjuncte A1, A2, …, Am, fiecare set Ai constituind la rândul său un arbore. Elementele arborelui sunt nodurile şi legăturile dintre ele. Nodul rădăcină r îl considerăm ca fiind pe nivelul 0. Întrucât A1, A2, …, Am sunt la rândul lor arbori, fie r1, r2, …, rm rădăcinile lor. Atunci r1, r2, …, rm formează nivelul 1 al arborelui. Nodul r va avea câte o legătură la fiecare dintre nodurile r1, r2, …, rm. O astfel de viziune asupra arborilor este o viziune ierarhică, nodurile fiind subordonate unele altora, fiecare nod fiind subordonat direct unui singur nod, excepţie făcând rădăcina ce nu este subordonată nici unui nod. Dacă un nod nu are nici un nod subordonat, atunci se numeşte frunză sau nod terminal. O categorie răspândită de arbori o reprezintă arborii binari. Un arbore binar se compune din rădăcină şi din doi subarbori, numiţi subarborele stâng, respectiv drept. Se acceptă şi arbori binari cu 0 (zero) vârfuri.

1 8

2 3 4

9

5 6

7

Există mai multe forme de reprezentare a arborilor binari. Astfel avem: • Expresii cu paranteze complete. Expresia începe cu rădăcina arborelui iar fiecare vârf cu descendenţi este urmat de expresiile ataşate subarborilor, care au ca rădăcini descendenţii vârfului, despărţite între ele prin “,” şi cuprinse între paranteze mici. Când unul dintre des-

58

Arbori binari

cendenţi lipseşte, subexpresia respectivă este cuvântul vid (notat cu v). De exemplu, arborele precedent are expresia: 1(2(3(4(v, v),v),5(6(v,v),7(v,v))),8(v,9(v,v))). • Forma standard. Fiecărui vârf i se precizează descendentul său stâng ST(i), descendentul drept DR(i) şi informaţia INF(i). Lipsa unui descendent este indicată prin 0. Se cunoaşte şi rădăcina RAD. Pentru exemplul anterior, vectorii ST şi DR sunt: ST = (2, 3, 4, 0, 6, 0, 0, 0, 0); DR = (8, 5, 0, 0, 7, 0, 0, 9, 0); RAD = 1. • Reprezentarea tip "tată". Pentru fiecare vârf se memorează tatăl său TATA(i): TATA = (0, 1, 2, 3, 3, 5, 5, 1, 8), unde 0 (zero) semnifică lipsa tatălui. În afara acestor trei reprezentări mai există şi reprezentarea secvenţială. Pentru fiecare vârf se memorează numai INF(i) ataşată lui. Descendenţii vârfului se pot deduce printr-o numerotare adecvată a vârfurilor. Accesul de la rădăcina unui arbore/subarbore nevid la oricare alt nod sau vârf, presupune parcurgerea unui drum (căi), format din m arce (m ≥ 0) pentru care se găsesc n noduri (n = m + 1). Valoarea n, reprezintă nivelul pe care se găseşte nodul faţă de rădăcină. Prin convenţie nivelul rădăcinii este 1. Înălţimea unui arbore reprezintă maximul dintre nivelurile nodurilor terminale, iar numărul de descendenţi direcţi ai unui nod reprezintă ordinul nodului. În cazul în care ordinul nodurilor nu este limitat, arborele este numit multicăi. Orice arbore multicăi poate fi privit ca arbore binar, dacă orice nod are relaţia directă cu maximum alte două noduri. • Reprezentarea secvenţială. Un arbore binar se numeşte plin (total), dacă are 2k - 1 vârfuri pe nivelurile 1, 2, 3, ..., k, astfel încât pe fiecare nivel i apar 2i - 1 vârfuri. Altfel spus, arborele este plin dacă fiecare vârf, cu excepţia celor terminale, are descendenţi stâng şi drept. Vârfurile sunt numerotate în ordinea nivelurilor iar, pe fiecare nivel numerotarea se face de la stânga la dreapta. 1 nivel 1 2 4 8

3 5

6

nivel 2 7

nivel 3

9 10 nivel 4 11 12 13 14 15 Un arbore binar complet cu n vârfuri, se obţine astfel: se determină k ∈ N astfel încât k-1 2 ≤ n ≤ 2k şi se formează arborele binar plin cu 2k - 1 vârfuri, din care se elimină, eventual, vârfurile n + 1, n + 2, ..., 2k - 1. De exemplu, dacă din arborele anterior eliminăm vârfurile 13, 14, 15 se va obţine un arbore complet cu n = 12 vârfuri. Pentru un astfel de arbore folosim aceeaşi numerotare şi acelaşi vector INF(i), i = 1, … n. Restul informaţiei relative la arbore se deduce uşor. Astfel, pentru fiecare vârf i = 1, …, n, avem:

Arbori binari

59

2 ⋅i ≤ n 2 ⋅ i +1 ≤ n 2 ⋅ i, 2 ⋅ i + 1, ST(i) =  DR(i)=  nu exist ă , 2 ⋅ i > n nu exist ă , 2 ⋅i > n   Pentru un arbore binar oarecare, se procedează astfel: completăm arborele astfel încât el să fie complet, renumerotăm normal vârfurile iar pentru vârfurile nou introduse ataşăm o valoare care nu poate fi ataşată vreunui vârf real. Dacă un arbore binar are numai descendenţi drepţi, exceptând rădăcina, atunci reprezentarea nu este economică din punct de vedere al memoriei deoarece din cele 2n-1 componente ale vectorului INF, numai n componente sunt efective. Parcurgerea arborilor binari. Să considerăm că un arbore este reprezentat prin fiecare vârf al său, precum şi prin informaţia ataşată vârfurilor. Fie arborele: Prelucrarea informaţiei memorate într1 o structură de arbore implică parcurgerea arborelui, adică inspectarea sau vizitarea 2 3 fiecărui nod şi prelucrarea informaţiei specifice. Problema care se pune este cea a 4 ordinii în care se prelucrează nodurile ar6 7 5 borelui (rădăcina şi respectiv nodurile din subarbori). Există mai multe posibilităţi de 8 9 10 parcurgere. • Parcurgerea în inordine (stânga, rădăcină, dreapta). Rădăcina e prelucrată după nodurile din subarborele stâng dar înaintea celor din subarborele drept: (4, 2, 5, 8, 1, 6, 3, 9, 7, 10). • Parcurgerea în preordine (rădăcină, stânga, dreapta). Rădăcina e prelucrată înaintea nodurilor din subarborii stâng şi drept: (1, 2, 4, 5, 8, 3, 6, 7, 9, 10 ). • Parcurgerea în postordine (stânga, dreapta, rădăcină). Rădăcina e prelucrată după ce au fost prelucraţi subarborii stâng şi drept: (4, 8, 5, 2, 6, 9, 10, 7, 3, 1). Indiferent de tipul parcurgerii, ordinea relativă a tratării nodurilor terminale e aceeaşi (de la stânga la dreapta). Datele relative la arbore se vor introduce în ordinea: 1, 2, 4, 0, 0, 5, 0, 8, 0, 0, 3, 6, 0, 7, 9, 0, 0, 10, 0, 0. procedure InOrd(ST,DR,n,rad) integer ST(n),DR(n) i←rad do while sti 0: i←sti { se avansează spre stânga cât se poate } endwhile call visit(i) while dri=0 do { urcă până la primul vârf cu descendent drept } j←i, i←tatai

şi grafuri

i≥2 i =1

Arbori

 i/ 2 ,

TATA(i) =  nu exist ă ,

60

Arbori binari if i=0 then return endif until j=sti call visit(i) endwhile i←dri enddo return

Comentariu. Se pleacă din rădăcină şi se coboară spre stânga cât e posibil; când nu se mai poate coborî spre stânga, dar se poate coborî spre dreapta mergem un pas spre dreapta şi reluăm procedura. Dacă nu se poate nici spre dreapta urcăm "în sus" până ajungem la un vârf venind dinspre descendentul său stâng, vârf ce are descendent drept; trecem în acest descendent drept şi repetăm procedeul. Instrucţiunea call visit(i) arată că se prelucrează vârful i. Tatăl unui vârf reprezentat în tatai, i ≥ 2 se află în tata  i/2 . În algoritmul InOrd apar două probleme: − determinarea tatălui; − când se urcă de la un vârf i la tatăl său j trebuie ştiut dacă s-a venit din stânga sau din dreapta. O primă modalitate de rezolvare e aceea în care se foloseşte reprezentarea standard. Pentru fiecare vârf i se va memora şi tatăl său tatai şi atunci prima instrucţiune din do until devine i←tatai iar în condiţia din until devine j=sti. În reprezentarea standard este eficientă folosirea unei stive. Pentru aceasta, pe mulţimea vârfurilor arborelui se introduce relaţia: iRj dacă din j se ajunge în i coborând un pas la stânga şi apoi 0, 1 sau mai mulţi paşi spre dreapta. procedure InOrd1(ST,DR,n,rad) stack S integer ST(n), DR(n) do while sti=0 i S i←sti endwhile call visit(i) while dri=0 if S=0 then return endif i S call visit(i) endwhile i←dri enddo return

Arbori binari

61

procedure PreOrd(ST,DR,r,rad) integer ST(n), DR(n) i←rad do while sti0 call visit(i), i←sti endwhile call visit(i) while dri=0 do j←i i←tatai if i=0 then return endif until j=sti endwhile i←dri enddo return

În cazul folosirii unei stive (procedura PostOrd1), ea trebuie să conţină în permanenţă toate vârfurile care se află pe drumul ce uneşte vârful curent i cu rădăcina. procedure PostOrd(ST,DR,n,rad) integer ST(n), DR(n) do while sti0 i←sti endwhile while dri=0 do call visit(i) j←i i←tatai if i=0 then return

procedure PostOrd1(ST,DR,n,rad) Stack S integer ST(n), DR(n) i←rad, S0 do while sti0 Si, i←sti endwhile while dri=0 do call visit(i)

şi grafuri

procedure InOrd2(ST,DR,n,rad) Stack S integer ST(n), DR(n) i←rad S←0 do while sti0 i S i←sti endwhile call visit(i) if S=0 then return else i S call visit(i) i←dri endif enddo return

Arbori

În algoritmul InOrd1, stiva este iniţial vidă. Fie i un vârf curent. Dacă: − stiva este vidă rezultă că din rădăcină se ajunge la i coborând numai spre dreapta; − stiva e nevidă şi conţine în ordine, de la bază la vârf, elementele k1, k2, ..., ks; atunci: – i este în relaţia R cu ks, – ks este în relaţia R cu ks-1, – ..., – k2 este în relaţia R cu k1 – k1 este în relaţia R cu vreun alt vârf. În cazul particular al unui arbore binar strict avem procedura InOrd2

62

Arbori binari endif until j=sti endwhile i←dri enddo return

if S=0 then return endif j←i iS until j=sti endwhile iS i←dri enddo return

4.2 Arbori oarecare • O primă modalitate de reprezentare (legături fiu-frate) este aceea de a memora pentru fiecare vârf i următoarele informaţii: fiui (primul dintre descendenţii vârfului i), fratei (descendentul tatălui lui i care urmează imediat după i). Lipsa fiului, respectiv a fratelui este marcată cu 0. Dacă se identifică fiu cu st şi frate cu dr atunci fiecărui arbore oarecare i se poate ataşa un arbore binar. În figura următoare arborele din stânga este reprezentat prin cel din dreapta: 1 2

5

1

3

6

4

7

2

⇒ 5

3 6

4

7 Corespondenţa descrisă va reduce parcurgerea arborilor oarecare la parcurgerea arborilor binari. Concret, pe exemplul dat se va obţine: 1 2 5 3 6 7 4 (preordine), 5 2 6 7 3 4 1 (inordine) şi 5 7 6 4 3 2 1 (postordine). • A doua modalitate de reprezentare este de a forma pentru fiecare vârf o listă a descendenţilor săi. Pentru un arbore cu n vârfuri se consideră un vector infi ce conţine informaţia din cele n vârfuri şi un alt vector, cap. Dacă i este vârf terminal capi = 0, iar dacă lista descendenţilor lui i începe de la adresa a avem capi = a. Memorarea listelor descendenţilor vârfurilor n se poate realiza printr-o matrice M2, n - 1 folosind pentru ele alocarea înlănţuită. Pentru fiecare i∈{1, 2, ..., n-1} valoarea m1,i reprezintă un descendent al vârfului pentru care lista ataşată conţine coloana i din M, iar m2,i reprezintă

Arbori binari

63

numărul coloanei corespunzătoare următorului descendent sau 0 dacă nu există vreun alt descendent. Pentru arborele precedent avem: 3 4

cap = (2, 5, 6, 0, 0, 0, 0), M =  

7 0

5 0

4 0

2 3

6 . 7 

Se observă că următorul descendent al tatălui vârfului m1,i este m[1,m2,i] cu m2,i ≠ 0.

{ fiui0 }

{ fratei=0 }

Se observă că preordinea în arbore este echivalentă cu preordinea în arborele binar ataşat. Parcurgerea în postordine. Aceasta constă în a vizita subarborii ce au ca rădăcini descendenţii rădăcinii arborelui şi apoi rădăcina arborelui. Pe exemplul dat, obţinem: 5 2 6 7 3 4 1. Pentru procedura APostOrd se utilizează reprezentarea fiu-frate. procedure APostOrd(FIU,FRATE,n,rad) Stack S integer FIU(n), FRATE(n) i←rad, S←0 do while fiui0 iS

şi grafuri

procedure APreOrd(CAP,n,rad) Stack S integer CAP(n),M(2,n-1),rad i←rad, j←0, S←0 do while capi0 call visit(i) (i,j) S i←M[1,capi] j←M[2,capi] endwhile call visit(i) while j=0 if S=0 then return else (i,j) S endif endwhile i←M1,j, j←M2,j enddo return

Arbori

Parcurgerea arborilor oarecare. Metoda presupune o ordine bine stabilită între descendenţii fiecărui vârf. Parcurgerea în preordine constă în a vizita rădăcina, apoi în ordine subarborii săi. Pentru exemplul anterior parcurgerea furnizează vârfurile în ordinea: 1 2 5 3 6 7 4. Procedura APreOrd parcurge arborele în care s-a folosit reprezentarea a doua:

64

Arbori binari i←fiui endwhile call visit(i) while fratei=0 if S=0 then return else iS, call visit(i) endif endwhile i←fratei enddo return

4.3 Grafuri Un graf este un ansamblu G = (V, E) unde V este o mulţimea nevidă reprezentând mulţimea vârfurilor V = {x1, ..., xn} iar E este o relaţie definită pe V şi conţine arce de forma (xi, xj), în care xi este originea sau extremitatea iniţială a arcului iar xj este extremitatea finală. 4.3.1 Reprezentarea grafurilor Există trei modalităţi de reprezentare: • Matricea de adiacenţă. Ea este un tablou A de dimensiune n2 unde n = card(V), iar: 1, ( i , j ) ∈E , ai,j=  0, ( i, j ) ∉E. Pentru graful: 2

1 3

O variantă alternativă este dată de: valoarea muchiei ( i, j ), ai,j=  + ∞,

Matricea de adiacenţă este: 0  A(i, j) = 1 0 

1 0 1

0  1 . 0 

dac ă ( i, j ) ∈ E , dac ă ( i, j ) ∉ E.

Memoria necesară e de ordinul n2. Cu această reprezentare putem verifica uşor dacă două vârfuri sunt adiacente. De asemenea, se permite accesul rapid la arcele grafului fiind utilă această reprezentare când se testează frecvent prezenţa sau absenţa unui arc oarecare. Dacă numărul de arce este mai mic decât n2, reprezentarea e dezavantajoasă pentru că memoria nu este folosită eficient.

Arbori binari

65

• Listele de adiacenţă. Fiecărui vârf i, i se ataşează o listă de vârfuri adiacente lui. Pentru grafurile orientate, arcul trebuie să plece din vârful i. Într-un graf cu m muchii, suma lungimilor listelor de adiacenţă este 2 ⋅ m (dacă graful este orientat) sau m în caz contrar. Această reprezentare este recomandată când numărul muchiilor este mic. Căutarea este anevoioasă şi proporţională cu numărul de noduri. Pentru a determina dacă două vârfuri sunt adiacente, trebuie să analizăm lista de adiacenţă a lui i şi eventual a lui j. De aceea este mai eficientă matricea de adiacenţă.

2

→ → → →

1 2 3 4

3 4

2 1 2 2

3 4 3

4

• Listă de muchii (i, j). Pentru graful anterior cu patru vârfuri reprezentarea este: 1 2 2 3

2 3 4 4

Această reprezentare este eficientă când se vor examina toate muchiile grafului. 4.3.2 Parcurgerea grafurilor Algoritmul de parcurgere ParcGraf, utilizează două mulţimi de noduri: mulţimea Vizit (mulţimea nodurilor vizitate) şi mulţimea Neexplor (submulţime a lui Vizit şi conţine noduri ai căror vecini au fost parţial exploraţi). Explorarea începe cu un nod i, dat. Dacă rămân noduri neparcurse, se alege unul dintre ele şi se parcurge din nou algoritmul. Procedeul se repetă până la parcurgerea tuturor nodurilor. procedure ParcGraf(i) Vizit i * prelucrare informaţie din i NeexplorVizit while Neexplor <>  * alege un nod din Neexplor şi găseşte (v,w) arc neexploatat, ce pleacă din v if (v,w) nu există then Şterge v din Neexplor else

Arbori

listele de adiacenţă sunt:

1

şi grafuri

Pentru graful:

66

Arbori binari if w  Vizit then adaugă w prelucrează informaţia din Vizit adaugă w la Neexplor endif endif endwhile return

Parcurgerea nodurilor se realizează prin metodele: • Algoritmul DF (Depth First). Se porneşte de la un nod iniţial v. Se alege o muchie (v, w), incidentă în v şi w. Fie nodul curent x. Căutarea continuă cu muchia (x, y), care este incidentă în x şi y, şi în care y nu a fost vizitat anterior, nodul y devenind nod curent. După epuizarea tuturor drumurilor care pleacă din y, algoritmul revine în x, parcurgerea continuând cu următoarea muchie. Numele algoritmului provine din faptul că parcurgerea se realizează având ca direcţie prioritară adâncimea grafului. Fie graful: 1 3

2

4 6

5 7

8

Dacă se începe cu nodul 1, parcurgerea DF este 1, 2, 5, 3, 7, 6, 4, 8. Acest algoritm se foloseşte pentru găsirea ieşirii din labirint: se merge la stânga spre vârfuri noi, cât timp este posibil; când nu mai este posibil ne întoarcem un pas şi încercăm să mergem spre cel mai din stânga dintre vârfurile învecinate şi neatinse etc. Pentru a face distincţie între nodurile parcurse şi neparcurse folosim un vector Vizit cu n componente în care: 1, dacă nodul i a fost parcurs Vizit i =  0, în caz contrar

Procedura de rezolvare este: procedure DF(i) Viziti←1 for () j vecin cu i if Vizitj=0 then call DF(j) endif endfor return

{ prelucrează nod i }

Arbori binari

67

Pentru parcurgerea întregului graf, apelul procedurii se realizează prin: for i=1,n if Viziti=0 then call DF(i) endif endfor

Se va utiliza un vector Vizit cu n componente, cu aceeaşi semnificaţie ca la parcurgerea DF. De asemenea, se va folosi o coadă în care sunt introduse vârfurile nevizitate, deci încă neprelucrate. Procedura BF constă în a extrage pe rând, un element din coadă şi a introduce apoi în coadă descendenţii nevizitaţi, vizitându-i în acelaşi timp. Prin i se notează vârful de la care se pleacă. Algoritmul se termină când coada este vidă. procedure BF(i) * iniţilizează coada call push(i) Viziti←1 * prelucrează nod i while coada nu este vidă j←pop for toţi vecinii k ai lui j if Vizitk=0 then call push(k) Vizitk←1 * prelucrează nodul k endif endfor endwhile return

• Algoritmul D (Depth). Spre deosebire de BF, aici se prelucrează mereu numai ultimul element la care s-a ajuns. Lista folosită nu mai este coadă ci stivă. Pentru exemplul dat, rezultatul parcurgerii este 1, 2, 3, 4, 6, 7, 8, 5.

şi grafuri

• Algoritmul BF (Breadth First). Se pleacă cu vârful v, care se marchează ca fiind vizitat. Se parcurg apoi toate nodurile adiacente cu v (toţi descendenţii lui v). Se alege un descendent al lui v, (fie acesta w) şi se parcurg toţi descendenţii lui w etc. Parcurgerea se execută în lăţime. Pentru graful anterior, ordinea de parcurgere este 1, 2, 3, 4, 5, 6, 7, 8.

Arbori

Atenţie! Este necesar să folosim o stivă ce va conţine în ordine vârfurile aflate pe drumul ce uneşte vârful iniţial cu cel curent şi o variabilă ce numără vârfurile vizitate.