ARBORI ŞI GRAFURI

4.1 Arbori binari

Fiind dată o mulţime M de elemente denumite noduri sau vârfuri, vom numi arbore (du-pă 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 m0 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ăcini-le 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 nu-meş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.

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-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))).

58 Arbori binari

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 nu-merotare 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 nodu-lui. Î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ârfu-rile sunt numerotate în ordinea nivelurilor iar, pe fiecare nivel numerotarea se face de la stânga la dreapta.

Un arbore binar complet cu n vârfuri, se obţine astfel: se determină k N astfel încât 2k - 1  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:

TATA(i) =

ST(i) = DR(i)=

Arbori binari 59

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 va-loare 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 reprezen-tarea 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 într-o structură de arbore implică parcurgerea arborelui, adică inspectarea sau vizitarea fiecărui nod şi prelucrarea informaţiei spe-cifice. Problema care se pune este cea a ordinii în care se prelucrează nodurile ar-borelui (rădăcina şi respectiv nodurile din subarbori). Există mai multe posibilităţi de 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 nodu-rilor 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)iraddo

while sti0: isti { se avansează spre stânga cât se poate }endwhilecall visit(i)while dri=0

do { urcă până la primul vârf cu descendent drept }

ji, itatai

if i=0 then returnendif

until j=sti

call visit(i)endwhileidri

enddoreturn

60 Arbori binari

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 re-luă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 descen-dent 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. Pen-

tru fiecare vârf i se va memora şi tatăl său tatai şi atunci prima instrucţiune din do until devine itatai 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ân-ga şi apoi 0, 1 sau mai mulţi paşi spre dreapta.

procedure InOrd1(ST,DR,n,rad)stack Sinteger ST(n), DR(n)do

while sti=0iSisti

endwhilecall visit(i)while dri=0

if S=0 then returnendifiS call visit(i)

endwhileidri

enddoreturn

Î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

Arbori binari 61

procedure InOrd2(ST,DR,n,rad)Stack Sinteger ST(n), DR(n)iradS0do

while sti0iS isti

endwhilecall visit(i)if S=0 then return else iS call visit(i) idri

endifenddoreturn

procedure PreOrd(ST,DR,r,rad)integer ST(n), DR(n)iraddo

while sti0call visit(i), isti

endwhilecall visit(i)while dri=0

dojiitatai

if i=0 then returnendif

until j=sti

endwhileidri

enddoreturn

Î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 sti0isti

endwhilewhile dri=0

docall visit(i)jiitatai

if i=0 then returnendif

until j=sti

endwhileidri

enddoreturn

procedure PostOrd1(ST,DR,n,rad)

Stack Sinteger ST(n), DR(n)irad, S0do

while sti0Si, isti

endwhilewhile dri=0

docall visit(i)if S=0 then returnendifjiiS

until j=sti

endwhileiSidri

enddoreturn

62 Arbori binari

4.2 Arbori oarecare

O primă modalitate de reprezentare (legături fiu-frate) este aceea de a memora pentru fie-care vârf i următoarele informaţii: fiui (primul dintre descendenţii vârfului i), fratei (descen-dentul 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:

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 descen-denţ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 fo-losind 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ă numărul coloanei corespunzătoare următorului descendent sau 0 dacă nu există vreun alt descendent. Pentru arborele precedent avem:

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

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

Parcurgerea arborilor oarecare. Metoda presupune o ordine bine stabilită între descen-denţii fiecărui vârf. Parcurgerea în preordine constă în a vizita rădăcina, apoi în ordine sub-arborii 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:

Arbori binari 63

procedure APreOrd(CAP,n,rad)Stack Sinteger CAP(n),M(2,n-1),radirad, j0, S0do

while capi0 { fiui0 }call visit(i)(i,j)SiM[1,capi]jM[2,capi]

endwhilecall visit(i)while j=0 { fratei=0 }

if S=0 then return else (i,j)S

endifendwhile

iM1,j, jM2,j

enddoreturn

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 descen-denţ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 Sinteger FIU(n), FRATE(n)irad, S0do

while fiui0iSifiui

endwhilecall visit(i)while fratei=0

if S=0 then return else iS, call visit(i)

endifendwhileifratei

enddoreturn

64 Arbori binari

4.3 Grafuri

Un graf este un ansamblu G = (V, E) unde V este o mulţimea nevidă reprezentând mulţi-mea 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:

ai,j=

Pentru graful:Matricea de adiacenţă este:

A(i, j) = .

O variantă alternativă este dată de:

ai,j=

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.

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 lungi-milor 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ţă.

Pentru graful:

Arbori binari 65

listele de adiacenţă sunt:

1 22 1 3 43 2 44 2 3

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

1 22 32 43 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 nodu-rilor.

procedure ParcGraf(i)Viziti * prelucrare informaţie din iNeexplorVizitwhile 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 Neexplorelse

if w Vizit then adaugă w

prelucrează informaţia din Vizitadaugă w la Neexplor

endifendif

endwhilereturn

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ă

66 Arbori binari

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 reali-zează având ca direcţie prioritară adâncimea grafului.

Fie graful:

Dacă se începe cu nodul 1, parcurgerea DF este 1, 2, 5, 3, 7, 6, 4, 8. Acest algoritm se fo-loseşte pentru găsirea ieşirii din labirint: se merge la stânga spre vârfuri noi, cât timp este po-sibil; 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:

Procedura de rezolvare este:

procedure DF(i) Viziti1for () j vecin cu i { prelucrează nod i }

if Vizitj=0 then call DF(j)endif

endforreturn

Pentru parcurgerea întregului graf, apelul procedurii se realizează prin:

for i=1,nif Viziti=0 then call DF(i)endif

endfor

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.

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 binari 67

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ă coadacall push(i)Viziti1* prelucrează nod iwhile coada nu este vidă

jpopfor toţi vecinii k ai lui j

if Vizitk=0then call push(k)

Vizitk1* prelucrează nodul k

endifendfor

endwhilereturn

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.