10. Structura de date graf

n problemele care apar n programare, matematic, inginerie n general i n multe alte domenii, apare adeseori necesitatea reprezentrii unor relaii arbitrare ntre diferite obiecte, respectiv a interconexiunilor dintre acestea.

Spre exemplu, dndu-se traseele aeriene ale unui stat se cere s se precizeze

drumul optim dintre dou orae.

o Criteriul de optimalitate poate fi spre exemplu timpul sau preul, drumul optim putnd s difere pentru cele dou situaii.

Circuitele electrice sunt alte exemple evidente n care interconexiunile dintre

obiecte joac un rol central.

o Piesele (tranzistoare, rezistene, condensatoare) sunt interconectate prin fire electrice.

o Astfel de circuite pot fi reprezentate i prelucrate de ctre un sistem de

calcul n scopul rezolvrii unor probleme simple cum ar fi: Sunt toate piesele date conectate n acelai circuit? sau a unor probleme mai complicate cum ar fi: Este funcional n anumit circuit electric?.

Un al treilea exemplu l reprezint planificarea activitilor, n care obiectele

sunt task-uri (activiti, procese) iar interconexiunile precizeaz care dintre activiti trebuiesc finalizate naintea altora.

o ntrebarea la care trebuie s ofere un rspuns este: Cnd trebuie

planificat fiecare activitate?.

Structurile de date care pot modela n mod natural situaii de natura celor mai sus prezentate sunt cele derivate din conceptul matematic cunoscut sub denumirea de graf.

Teoria grafurilor este o ramur major a matematicii combinatorii care n timp a

fost i este nc intens studiat.

o Multe din proprietile importante i utile ale grafurilor au fost demonstrate, altele cu un grad sporit de dificultate i ateapt nc rezolvarea.

n cadrul capitolului de fa vor fi prezentate doar cteva din proprietile

fundamentale ale grafurilor n scopul nelegerii algoritmilor fundamentali de prelucrare a structurilor de date graf.

o Ca i n multe alte domenii, studiul algoritmic al grafurilor respectiv al

structurilor de date graf, este de dat relativ recent astfel nct alturi de algoritmii fundamentali cunoscui de mai mult vreme, muli dintre algoritmii de mare interes au fost descoperii n ultimii ani [Se88].

10.1. Definiii

Un graf, n cea mai larg accepiune a termenului, poate fi definit ca fiind o colecie

de noduri i arce.

o Un nod este un obiect care poate avea un nume i eventual alte proprieti asociate

o Un arc este o conexiune neorientat ntre dou noduri.

Notnd cu N mulimea nodurilor i cu A mulimea arcelor, un graf G poate fi precizat

formal prin enunul G=(N,A). n figura 10.1.a. (a),(b) apar dou exemple de grafuri.

a

b

c d

e 3 2

1

Fig.10.1.a. Exemple de grafuri

Ordinul unui graf este numrul de noduri pe care acesta le conine i se noteaz cu |G|.

Arcele definesc o relaie de inciden ntre perechile de noduri.

Dou noduri conectate printr-un arc se numesc adiacente, altfel ele sunt

independente.

Dac a este un arc care leag nodurile x i y (a~(x,y)), atunci a este incident cu x,y.

o Singura proprietate presupus pentru aceast relaie este simetria [10.1.a]

------------------------------------------------------------ (x,y)A =>(y,x)A unde A este mulimea arcelor. [10.1.a] ------------------------------------------------------------

Un graf poate fi definit astfel nct s aib un arc a~(x,x).

o Un astfel de arc se numete bucl ("loop"). o Dac relaia de inciden este reflexiv, atunci fiecare nod conine o astfel

de bucl.

Exist i posibilitatea ca s existe mai multe arce care conecteaz aceeai pereche de noduri.

o ntr-un astfel de caz se spune c cele dou noduri sunt conectate printr-un

arc multiplu.

n figura 10.1.a (b) este reprezentat un graf cu bucl i arc multiplu.

Grafurile n care nu sunt acceptate arce multiple se numesc grafuri simple.

Numrul de arce incidente unui nod reprezint gradul nodului respectiv.

o Se numete graf regulat acel graf n care toate nodurile sunt de acelai

grad.

ntr-un graf complet de ordinul n notat cu Kn, fiecare pereche de noduri este adiacent.

o n figura 10.1.b. apar reprezentate grafurile complete pn la ordinul 6.

K0 K1 K2 K3 K4 K5 K6

Fig.10.1.b. Exemple de grafuri complete

Un graf se numete planar dac el poate fi astfel reprezentat ntr-un plan, nct oricare dou arce ale sale se intersecteaz numai n noduri [GG78].

O teorem demonstrat de Kuratowski precizeaz c orice graf neplanar conine

cel puin unul din urmtoarele grafuri de baz: 1. 5-graful complet (K5), sau 2. Graful utilitar n care exist dou mulimi de cte trei noduri, fiecare nod

fiind conectat nodurile din cealalt mulime.

Fig.10.1.c. Graf utilitar

Un graf se numete bipartit dac nodurile sale pot fi partiionate n dou mulimi distincte N1 i N2 astfel nct orice arc al su conecteaz un nod din N1 cu un nod din N2.

o Spre exemplu graful utilitar este un n acelai timp un graf bipartit.

Fie G=(N,A) un graf cu mulimea nodurilor N i cu mulimea arcelor A. Un

subgraf al lui G este graful G'= (N',A') unde:

1. N'este o submulime a lui N; 2. A' const din arce (x,y) ale lui A, astfel nct x i y aparin lui N'.

n figura 10.1.d apare un exemplu de graf (a) i un subgraf al su (b).

a b

d c

a b

c

Fig.10.1 d. Graf i un subgraf al su

Dac mulime de arce A' conine toate arcele (x,y) ale lui A pentru care att x ct i y sunt n N', atunci G' se numete subgraf indus al lui G [AH85].

Un graf poate fi reprezentat n manier grafic marcnd nodurile sale i trasnd linii

care materializeaz arcele.

o n acelai timp ns, un graf poate fi conceput ca i un tip de date abstracte, independent de o anumit reprezentare.

o Spre exemplu fig.10.1.e (a) respectiv (b) reprezint unul i acelai graf.

o Un graf, poate fi definit spre exemplu preciznd doar mulimea nodurilor i

mulimea arcelor sale.

A G

F

B C

E

D

H I

J K

L M

(a)

G A

F

B C

E

D

L

M

I H

J K

(b)

Fig.10.1.e. Reprezentri echivalente ale unui graf

n anumite aplicaii, cum ar fi exemplul cu traseele aeriene, poziia nodurilor (oraelor) este precizat fizic prin amplasarea lor pe harta real a statului, rearanjarea structurii fiind lipsit de sens.

n alte aplicaii ns, cum ar fi planificarea activitilor, sunt importante nodurile

i arcele ca atare independent de dispunerea lor geometric.

n cadrul capitolului de fa vor fi abordai algoritmi generali, care prelucreaz colecii de noduri i arce, fcnd abstracie de dispunerea lor geometric, cu alte cuvinte fcnd abstracie de topologia grafurilor.

Se numete drum (path) de la nodul x la nodul y, o secven de noduri

n1,n2,...,nj n care nodurile succesive sunt conectate prin arce aparinnd grafului.

o Lungimea unui drum este egal cu numrul de arce care compun drumul. o La limit, un singur nod precizeaz un drum la el nsui de lungime zero.

Un drum se numete simplu dac toate nodurile sale, exceptnd eventual primul

i ultimul sunt distincte.

Un ciclu (bucl) este un drum simplu de lungime cel puin 1, care ncepe i se sfrete n acelai nod.

Dac exist un drum de la nodul x la nodul y se spune c acel drum conecteaz

cele dou noduri, respectiv nodurile x i y sunt conectate.

Un graf se numete conex, dac de la fiecare nod al su exist un drum spre oricare alt nod al grafului, respectiv dac oricare pereche de noduri aparinnd grafului este conectat.

o Intuitiv, dac nodurile se consider obiecte fizice, iar conexiunile fire care

le leag, atunci un graf conex rmne unitar, indiferent de care nod ar fi suspendat n aer.

Un graf care nu este conex este format din componente conexe.

o Spre exemplu, graful din fig.10.1.a este format din trei componente conexe.

Un graf se numete ciclic dac conine cel puin un ciclu.

o Un ciclu care include toate arcele grafului o singur dat se numete ciclu

eulerian (hamiltonian). o Este uor de observat c un asemenea ciclu exist numai dac graful este

conex i gradul fiecrui nod este par.

Un graf conex aciclic se mai numete i arbore liber.

o n fig.10.1.f apare un graf constnd din dou componente conexe n care fiecare component conex este un arbore liber.

o Se remarc n acest sens, observaia ca arborii sunt de fapt cazuri

particulare ale grafurilor.

o Un grup de arbori neconectai formeaz o pdure (forest).

Un arbore de acoperire (spanning tree) al unui graf, este un subgraf care conine toate nodurile grafului iniial, dar dintre conexiuni numai attea cte sunt necesare formrii unui arbore.

o Se face precizarea c termenul de acoperire n acest context are sensul termenului cuprindere.

Fig.10.1.f. Graf aciclic format din dou componente conexe

n figura 10.1.g este prezentat un graf (a) i un arbore de acoperire al grafului (b).

A G

F

B C

E

D

(a)

A G

F

B C

E

D

(b)

Fig.10.1.g. Graf i un arbore de acoperire al grafului

Un arbore liber poate fi transformat ntr-un arbore ordinar dac se suspend

arborele de un nod considerat drept rdcin i se orienteaz arcele spre rdcin. Arborii liberi au dou proprieti importante:

1. Orice arbore liber cu n noduri conine exact n-1 arce (cte un arc la

fiecare nod, mai puin rdcina); 2. Dac unui arbore liber i se adaug un arc el devine obligatoriu un

graf ciclic.

De aici rezult dou consecine importante i anume:

1. Un graf cu n noduri i mai puin de n-1 arce nu poate fi conex; 2. Pot exista grafuri cu n noduri i n-1 arce care nu sunt arbori liberi.

(Spre exemplu dac au mai multe componente conexe).

Notnd cu n numrul de noduri ale unui graf i cu a numrul de arce, atunci a poate lua orice valoare ntre 0 i (1/2)n(n-1).

o Graful care conine toate arcele posibile este graful complet de ordinul n

(Kn). o Graful care are relativ puine arce (spre exemplu a

o Graful cu un numr de arce apropiat de graful complet se numete graf

dens.

Dependena fundamental a topologiei unui graf de doi parametri (n i a), face ca studiul comparativ al algoritmilor utilizai n prelucrarea grafurilor s devin mai complicat din cauza posibilitilor multiple care pot s apar.

Grafurile prezentate pn n prezent se numesc i grafuri neorientate i ele

reprezint cea mai simpl categorie de grafuri. Prin asocierea de informaii suplimentare nodurilor i arcelor, se pot obine

categorii de grafuri mai complicate.

Astfel, ntr-un graf ponderat (weighted graph), fiecrui arc i se asociaz o valoare (de regul ntreag) numit pondere care poate reprezenta spre exemplu o distan sau un cost.

n cadrul grafurilor orientate (directed graphs), arcele sunt orientate, avnd

un sens precizat, de la x la y spre exemplu.

o In acest caz x se numete coada sau sursa arcului iar y vrful sau destinaia sa.

o Pentru reprezentarea arcelor orientate se utilizeaz sgei sau segmente

direcionate (fig.10.1.h. (a), (b),(c)).

(a) x y

A G

F E

(b)

1 2

3 4

(c)

Fig.10.1.h. Grafuri orientate Grafurile orientate ponderate se mai numesc i reele (networks). Informaiile suplimentare referitoare la noduri i arce nuaneaz i n acelai timp

complic manipularea grafurilor care le conin.

10.2. Tipul de date abstract graf Pentru a defini tipul de date abstract (TDA) graf este necesar:

o (1) Precizarea modelului matematic care contureaz conceptul de graf prezentat n paragraful anterior

o (2) Precizarea operaiilor definite pe acest model. n cele ce urmeaz se prezint

dou variante, una extins i alta redus, de seturi de operatori afereni unui TDA graf.

10.2.1. TDA graf. Varianta 1 (Shiflet)

n cadrul variantei Shiflet [Sh90] un graf este considerat ca i o structur de noduri i arce.

Fiecare nod are o cheie care identific n mod univoc nodul.

Modelul matematic, notaiile utilizate i setul de operatori preconizat pentru aceast variant apar n [10.2.1.a]:

------------------------------------------------------------ TDA Graf (Varianta 1 - Shiflet) [10.2.1.a] Modelul matematic: graful definit n sens matematic. Notaii:

TipGraf - tipul de date abstract graf; TipElement - tipul asociat poriunii element a nodului TipCheie - tipul asociat poriunii cheie a unui

element TipInfo - tipul corespunzator poriunii de informaie a unui element TipIndicNod - tip referin la structura unui nod TipIndicArc - tip referin la structura unui arc Operatori:

1. InitGraf(g: TipGraf); - procedur care creeaz graful vid g;

2. GrafVid(g: TipGraf):boolean; - operator care returneaz

true dac graful este vid respectiv false n caz contrar;

3. GrafPlin(g: TipGraf):boolean; - operator boolean care

returneaz true dac graful este plin. Se precizeaz faptul c aceast funcie este legat direct de maniera de implementare a grafului. Valoarea ei adevrat presupune faptul c zona de memorie alocat structurii a fost epuizat i n consecin nu se mai pot aduga noi noduri.

4. CheieElemGraf(g: TipGraf, e: TipElement): TipCheie; -

operator care returneaz cheia elementului e aparinnd grafului g.

5. CautaCheieGraf(g: TipGraf; k: TipCheie); - operator

boolean care returneaz valoarea adevrat dac cheia k este gsit n graful g.

6. IndicaNod(g: TipGraf; k: TipCheie; var indicNod: TipIndicNod); - operator care face ca IndicNod s indice acel nod din g care are cheia k, presupunnd c un astfel de nod exist.

7. IndicaArc(g: TipGraf; k1,k2: TipCheie; var indicArc:

TipIndicArc);- operator care face ca indicArc s indice arcul care conecteaz nodurile cu cheile k1 i k2 din graful g, presupunnd c arcul exist. n caz contrar indicArc ia valoarea indicatorului vid.

8. ArcVid(g: TipGraf; indicArc: TipIndicArc):boolean; -

operator boolean care returneaz valoarea adevrat dac arcul indicat de indicArc este vid.

9. InserNod(var g: TipGraf; e: TipElement); - operator

care nsereaz un nod e n graful g ca un nod izolat (fr conexiuni). Se presupune c naintea inseriei n g nu exist nici un nod care are cheia identic cu cheia lui e.

10. InserArc(var g: TipGraf; k1,k2: TipCheie);- operator

care nsereaz n g un arc incident nodurilor avnd cheile k1 i k2. Se presupune c cele dou noduri exist i c arcul respectiv nu exist naintea inseriei.

11. SuprimNod(var g: TipGraf; indicNod: TipIndicNod); -

operator care suprim din g nodul precizat de indicNod, mpreun cu toate arcele incidente. Se presupune c naintea suprimrii, un astfel de nod exist.

12. SuprimArc(var g: TipGraf; indicArc: TipIndicArc); -

operator care suprim din g, arcul precizat de indicArc. Se presupune c naintea suprimrii un astfel de arc exist.

13. ActualizNod(var g: TipGraf; indicNod: TipIndicNod: x:

TipInfo); - operator care plaseaz valoarea lui x n poriunea informaie a nodului indicat de indicNod din graful g. Se presupune c indicNod precizeaz un nod al grafului.

14. FurnizeazaNod(g:TipGraf; indicNod: TipIndicNod):

TipElement; - operator care returneaz valoarea elementului memorat n nodul indicat de indicNod n graful g.

15. TraversGraf(var g: TipGraf; Vizit (ListArgumente)) -

operator care realizeaz traversarea grafului g, executnd pentru fiecare element al acestuia procedura Vizit(ListaArgumente), unde Vizit este o procedur specificat de utilizator iar ListArgumente este lista de parametri a acesteia.

---------------------------------------------------------

10.3. Tehnici de implementare a tipului de date abstract graf

n vederea prelucrrii grafurilor concepute ca i tipuri de date abstracte (TDA) cu ajutorul sistemelor de calcul, este necesar la primul rnd stabilirea modului lor de reprezentare.

Aceast activitate const de fapt din desemnarea unei structuri de date concrete care s materializeze n situaia respectiv tipul de date abstract graf.

n cadrul paragrafului de fa se prezint mai multe posibiliti, alegerea depinznd, ca i pentru marea majoritate a tipurilor de date deja studiate:

(1) De natura grafurilor de implementat

(1) De natura i frecvena operaiilor care se execut asupra lor.

n esen se cunosc dou modaliti majore de implementare a grafurilor: una bazat pe matrici de adiacene iar celalat pe structuri de adiacene.

10.3.1. Implementarea grafurilor cu ajutorul matricilor de adiacene.

Cel mai direct mod de reprezentare al unui tip de date abstract graf l constituie matricea de adiacene (adjacency matrix).

Dac se consider graful G=(N,A) cu mulimea nodurilor N={1,2,...,n},atunci matricea de adiacene asociat grafului G, este o matrice A[n,n] de elemente booleene, unde A[x,y] este adevrat dac i numai dac n graf exist un arc de la nodul x la nodul y.

Adesea elementelor booleene ale matricii sunt nlocuite cu ntregii 1 (adevrat), respectiv 0 (fals).

Primul pas n reprezentarea unui graf printr-o matrice de adiacene const n stabilirea unei corespondene ntre numele nodurilor i mulimea indicilor matricei.

Aceast coresponden poate fi realizat:

(1) n mod implicit prin alegerea corespunztoare a tipului de baz al mulimii N

(2) n mod explicit prin precizarea unei asocieri definite pe mulimea nodurilor cu valori n mulimea indicilor matricei.

n cazul corespondenei implicite cel mai simplu mod de implementare const n a denumi nodurile cu numere ntregi care coincid cu indicii de acces n matricea de adiacene.

Numele nodurilor pot fi de asemenea litere consecutive ale alfabetului care pot fi convertite simplu n valori ntregi

n cazul corespondenei explicite, pentru implementarea asocierii pot fi utilizate:

(1) Tehnici specifice simple cum ar fi cele bazate pe tablouri sau liste

(2) Tehnici avansate bazate spre exemplu pe arbori binari ordonai sau pe metoda dispersiei.

Pentru o urmrire facil a algoritmilor, n cadrul capitolului de fa, se va utiliza o metod implicit conform creia nodurile vor avea numele format dintr-o singur liter.

n figura 10.3.1.a. apare reprezentarea bazat pe matrice de adiacene (b) a grafului (a).

a b c d e

a b c d e

1 0 1 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1

a e

b

c d

(a)

(b)

Fig.10.3.1.a. Graf (a) reprezentat prin matrice de adiacene (b).

Se observ faptul c reprezentarea are un caracter simetric ntruct fiind vorba despre un graf neorientat, arcul care conecteaz nodul x cu nodul y este reprezentat prin dou valori n matrice: A[x,y] respectiv A[y,x].

n prelucrarea grafurilor se poate face presupunerea c un nod este conectat cu el nsui, element care se reflect n valoarea adevrat memorat n toate elementele situate pe diagonala principal a matricei de adiacene.

Acest lucru nu este ns obligatoriu i poate fi reconsiderat de la caz la caz.

n continuare se prezint dou studii de caz pentru implementarea TDA graf cu ajutorul matricilor de adiacene.

10.3.1.1. Studiu de caz 1.

Dup cum s-a precizat, un graf este definit prin mulimea nodurilor i prin mulimea arcelor sale.

n vederea prelucrrii, un astfel de graf trebuie furnizat drept dat de intrare algoritmului care realizeaz aceast activitate.

n acest scop, este necesar a se preciza modul n care se vor introduce n memoria sistemului de calcul elementele celor dou mulimi.

(1) O posibilitate n acest sens o reprezint citirea direct, ca dat de intrare a matricii de adiacene, metod care nu convine n cazul matricilor rare.

(2) O alt posibilitate o reprezint urmtoarea:

n prima etap se citesc numele nodurilor n vederea asocierii acestora cu indicii matricei de adiacene

n etapa urmtoare, se citesc perechile de nume de noduri care definesc arce n cadrul grafului.

Pornind de la aceste perechi se genereaz matricea de adiacene.

Se face precizarea c prima etap poate s lipseasc dac n implementarea asocierii se utilizeaz o metod implicit.

n secvena [10.3.1.1.a] apare un exemplu de program pentru crearea unei matrice de adiacene.

Corespondena nume nod-indice este realizat implicit prin funcia index, care are drept parametru numele nodului i returneaz indicele acestuia.

Din acest motiv, prima etap se reduce la citirea valorilor n i a care reprezint numrul de noduri, respectiv numrul de arce ale grafului.

Ordinea n care se furnizeaz perechile de noduri n etapa a doua nu este relevant, ntruct matricea de adiacene nu este n nici un mod influenat de aceast ordine.

------------------------------------------------------{Cazul 1. Implementarea TDA Graf utiliznd matrici de adiacene}

------

const maxN = 50; var j,x,y,N,A: integer; n1,n2: TipNod; graf: array[1..maxN,1..maxN] of boolean; {N = nr.de noduri, A = nr.de arce} begin readln(N,A); [10.3.1.1.a] for x := 1 to N do for y := 1 to N do graf[x,y]:= false; for x := 1 to N do graf[x,x]:= true; for j := 1 to A do begin readln(n1,n2); x:= index(n1); y := index(n2); graf[x,y]:= true; graf[y,x]:= true end end. {Creare matrice de adiacente} ------------------------------------------------------------

Dup cum se observ n cadrul secvenei, tipul variabilelor n1 i n2 este TipNod care nu este precizat

De asemenea nu este precizat nici codul aferent funciei index, acestea depinznd direct de maniera de reprezentare a nodurilor.

Spre exemplu n1 i n2 pot fi de tip caracter iar funcia index o expresie de forma n1`a respectiv n2-`a

10.3.1.2. Studiu de caz 2

Studiul de caz 2 prezint o metod mai elaborat de implementare a unui TDA graf, utiliznd drept suport limbajul PASCAL.

Reprezentarea presupune definirea tipurilor i structurilor de date n conformitate cu secvena [10.3.1.2.a].

------------------------------------------------------{Cazul 2. Implementarea TDA Graf utiliznd matrici de adiacene}

------

const NumarNoduri = .......; type TipCheie = .......; TipInfo = .......; TipElement = record Cheie: TipCheie; Info : TipInfo end; TipContor = 0..NumarNoduri; TipIndex = 1..NumarNoduri; TipTablouElem = array[TipIndex] of TipElement; TipMatrAdj = array[TipIndex,TipIndex] of boolean; TipGraf = record contor : TipContor; [10.3.1.2.a] noduri : TipTablouElem; arce : TipMatrAdj end; TipArc = record linie, coloana : TipIndex end; var g : TipGraf; k,k1,k2 : TipCheie; e : TipElement; indicNod : TipIndex; indicArc : TipArc; ------------------------------------------------------------

n accepiunea acestei reprezentri, graful din fig. 10.3.1.2.a.(a) va fi implementat prin urmtoarele elemente:

(1) contor care precizeaz numrul de noduri,

(2) noduri tabloul care pstreaz nodurile propriu-zise

(3) arce matricea de adiacene a grafului (fig.10.3.1.2.a.(b)).

1 2 3 4 noduri = [ a c d e ]

arce =

contor = 4

1 2 3 4

1 2 3 4

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

(b)

a e

c d

(a)

Fig.10.3.1.2.a. Reprezentarea elaborat a unui graf utiliznd matrice de adiacene

n anumite situaii, pentru simplificare, nodurile nu conin alte informaii n afara cheii, caz n care TipElement = TipCheie.

Alteori nodurile nu conin nici un fel de informaii (nici mcar cheia) situaie n care intereseaz numai numele nodurilor n vederea identificrii lor n cadrul reprezentrii.

n continuare se fac unele consideraii referitoare la implementarea n acest context a setului de operatori extins (Varianta 1, (Shiflet)).

(1) Operatorii InitGraf, GrafVid, GrafPlin, mpreun cu InserNod i SuprimNod se refer n regim de consultare sau modificare la contorul care pstreaz numrul nodurilor grafului: g.contor. (2) Informaia coninut de tabloul noduri poate fi ordonat sau neordonat.

Dac tabloul noduri este ordonat, localizarea unei chei n cadrul operatorilor CautCheieGraf sau IndicaNod se poate realiza prin tehnic cutrii binare

Dac tabloul noduri este neordonat localizarea unei chei se poate realiza prin tehnica cutrii liniar.

Operatorul CautCheieGraf indic numai dac cheia este prezent sau nu

Operatorul IndicaNod(g:TipGraf; k:TipCheie; var indicNod:TipIndicNod) asigneaz lui IndicNod indexul nodului din graful g, care are cheiea egal cu k.

Operatorul IndicaArc(g: TipGraf; k1,k2:TipCheie; var indicArc:TipArc) se comport ntr-o manier similar, returnnd

indexul nodului k1 n variabila de ieire indicArc.linie i indexul nodului k2 n indicArc.coloan.

(3) Inseria unui nod depinde de asemenea de maniera de organizarea datelor n cadrul tabloului noduri.

(a) Dac noduri este un tablou neordonat, se incrementeaz g.contor i se memoreaz nodul de inserat n g.noduri[g.contor].

Dup cum rezult din fig.10.3.1.2.b, care reprezint inseria nodului b n graful din figura 10.3.1.2.a, nodul nou introdus este izolat, adic n matricea de adiacene se introduce valoarea fals pe linia g.contor i pe coloana g.contor.

1 2 3 4 5 noduri = [ a c d e b ]

arce =

contor = 5

1 2 3 4 5

1 2 3 4 5

0 1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0

(b)

a e

c d

(a)

b

Fig.10.3.1.2.b. Inseria unui nod ntr-un graf

Procedura efectiv de inserie a unui nod nou n acest context apare n secvena [10.3.1.2.b].

------------------------------------------------------------ {Inseria unui nod. (Tabloul noduri neordonat)} procedure InserNod(var g: graf; e: TipElement); var i,j: TipIndex; begin [10.3.1.2.b] g.contor:= g.contor + 1; g.noduri[g.contor]:= e; {se plaseaz nodul nou} for i:= 1 to g.contor do g.arce[i,g.contor]:= false; {se iniializeaz matricea for j:= 1 to g.contor do de adiacente pt. nodul g.arce[g.contor,j]:= false nou} end; {InserNod} ------------------------------------------------------------

(b) Dac n tabloul noduri informaiile sunt ordonate, atunci:

n prealabil trebuie determinat locul n care se va realiza inseria

Se mut elementele tabloului g.noduri pentru a crea loc noului nod

Se mut liniile i coloanele matricei de adiacene g.arce pentru a crea loc liniei i coloanei corespunztoare noului nod

n final se realizeaz inseria propriu-zis prin completarea tabloului noduri i a matricei de adiacene.

(4) ntr-o manier similar, la suprimarea nodului cu indexul indicNod, trebuiesc efectuate micri n tablourile g.noduri i g.arce.

Figura 10.3.1.2.c ilustreaz suprimarea nodului c din structura de graf din figura 10.3.1.2.b.

n vederea suprimrii, indicNod are valoarea 2 preciznd nodul c, iar suprimarea propriu-zis presupune tergerea nodului din g.Noduri i modificarea matricei de adiacene prin excluderea arcelor conexe nodului c.

a e

b d

(a)

1 2 3 4 noduri = [ a b d e ]

arce =

contor = 4

1 2 3 4

1 2 3 4

0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0

(b)

Fig.10.3.1.2.c. Suprimarea unui nod dintr-o structur graf

(a) Dac tabloul noduri este neordonat, stergerea lui c se poate realiza prin mutarea ultimului element al tabloului n locul su.

Pentru pstrarea corectitudinii reprezentrii, este necesar tergerea arcelor conexe lui c din matricea de adiacene,

Pentru aceasta se copiaz linia i coloana corespunztoare ultimului nod din matricea g.arce,adic nodul b peste linia i coloana nodului care a fost suprimat.

n final se decrementeaz variabila g.contor.

Procedura care implementeaz aceste activiti se numete SuprimNod i apare n secvena [10.3.1.2.c].

--------------------------------------------------{Suprimarea unui nod. (Tabloul noduri neordonat)}

----------

procedure SuprimNod(var g: Graf; indicNod: TipIndex); var i,j: TipIndex; begin g.noduri[indicNod]:= g.noduri[g.contor]; [10.3.1.2.c] for j:= 1 to g.contor do g.arce[indicNod,j]:= g.arce[g.contor,j]; for i:= 1 to g.contor do g.arce[i,indicNod] := g.arce[i,g.contor];

g.contor := g.contor - 1 end; {SuprimNod} ------------------------------------------------------------

(b) Dac tabloul noduri este sortat, atunci suprimarea presupune:

Mutarea cu o poziie a tuturor nodurilor care au indexul mai mare ca indicNod din tabloul noduri

Mutarea liniilor i coloanelor corespunztoare lor din matricea de adiacene.

Dup cum se observ suprimarea unui nod presupune implicit i suprimarea arcelor conexe lui.

Exist ns posibilitatea de a terge arce fr a modifica mulimea nodurilor.

n acest scop se utilizeaz procedura SuprimArc(g: TipGraf; indicArc: TipArc) secvena [10.3.1.2.d].

Datorit simetriei reprezentrii stergerea unui arc presupune dou modificri n matricea de adiacene.

------------------------------------------------------------ {Suprimarea unui arc} [10.3.1.2.d] procedure SuprimArc(var g: Graf; indicArc: TipArc); begin g.Arc[indicArc.linie,indicArc.coloana]:= false; g.Arc[indicArc.coloana,indicArc.linie]:= false end; {SuprimArc} ------------------------------------------------------------

n concluzie n studiul de caz 2, crearea unei structuri pentru un TDA graf presupune dou etape:

(1) Precizarea nodurilor grafului, implementat printr-o suit de apeluri ale procedurii InserNod (cte un apel pentru fiecare nod al grafului);

(2) Conectarea nodurilor grafului, implementat printr-o suit de apeluri ale procedurii InserArc (cte un apel pentru fiecare arc al grafului).

n general reprezentarea bazat pe matrice de adiacene este eficient n cazul grafurilor dense.

Din punctul de vedere al spaiului de memorie necesar reprezentrii, matricea de adiacene necesit n2 locaii de memorie pentru un graf cu n noduri.

n plus mai sunt necesare locaii de memorie pentru memorarea informaiilor aferente celor n noduri.

Crearea grafului necesit un efort proporional cu O(n) pentru noduri i aproximativ O(n2) pai pentru arce, mai precis O(a).

n consecin de regul, utilizarea reprezentrii bazate pe matrice de adiacene conduce la algoritmi care necesit un efort de calcul de ordinul O(n2).

10.3.2. Implementarea grafurilor cu ajutorul structurilor de adiacene

O alt manier de reprezentare a TDA graf o constituie structurile de adiacene (adjacency-structures).

n cadrul acestei reprezentri, fiecrui nod al grafului i se asociaz o list de adiacene n care sunt nlnuite toate nodurile cu care acesta este conectat.

n continuare se prezint dou studii de caz pentru implementarea grafurilor cu ajutorul structurilor de adiacen.

10.3.2.1. Studiu de caz 1

Implementarea structurii de adiacene se bazeaz n Cazul 1 de studiu pe liste nlnuite simple.

nceputurile listelor de adiacene sunt pstrate ntr-un tablou Stradj indexat prin intermediul nodurilor.

Iniial n acest tablou se introduc nlnuiri vide, urmnd ca inseriile n liste s fie de tipul la nceputul listei.

Adugarea unui arc care conecteaz nodul x cu nodul y n cadrul acestui mod de reprezentare presupune n cazul grafurilor neorientate:

(1) Inseria nodului x n lista de adiacene a lui y

(2) Inseria nodului y n lista de adiacene a nodului x.

Un exemplu de program care construiete o astfel de structur apare n secvena [10.3.2.1.a]

------------------------------------------------------------ {Cazul 1. Construcia unui graf utiliznd structuri de adiacene implementate cu ajutorul listelor nlnuite simple} const maxN = 100; type RefTipNod = ^TipNod; TipNod = recod nume: integer; urm: RefTipNod end; {TipNod} var j,x,y,N,A: integer; v: RefTipNod; StrAdj: array[1..maxN] of RefTipNod; begin

readln(N,A); [10.3.2.1.a] for j:= 1 to N do StrAdj[j]:= nil; for j:= 1 to A do begin readln(n1,n2); x:= index(n1); y:= index(n2); NEW(v); v^.nume:= x; v^.urm:= StrAdj[y]; StrAdj[y]:= v; {inserie n fa} NEW(v); v^.nume:= y; v^.urm:= StrAdj[x]; StrAdj[x]:= v {inserie n fa} end end; ------------------------------------------------------------

n figura 10.3.2.1.a se prezint reprezentarea grafic a structurii construite pornind de la graful (a) din aceeai figur.

Se face precizarea c datele de intrare (arcele) au fost furnizate n urmtoarea ordine: (a,c), (a,d), (c,e), (c,d) i (d,e).

a e

c d

(a)

b

urm nume

a b c d e

d c

e c a

d c

StrAdj

TipNod

d e a

Fig.10.3.2.1.a. Graf i structura sa de adiacene

Se observ c un arc oarecare (x,y) este evideniat n dou locuri n cadrul structurii, att n lista de adiacene a lui x, ct i n cea a lui y.

Acest mod redundant de evideniere i dovedete utilitatea n situaia n care se cere s se determine ntr-o manier eficient care sunt nodurile conectate la un anumit nod x.

Pentru acest mod de reprezentare, conteaz ordinea n care sunt prezentate arcele respectiv perechile de noduri, la intrare.

Astfel, un acelai graf poate fi reprezentat ca structur de adiacene n moduri diferite.

Ordinea n care apar arcele n lista de adiacene, afecteaz la rndul ei ordinea n care sunt prelucrate arcele de ctre algoritm.

Funcie de natura algoritmilor utilizai n prelucrare aceast ordine poate s influeneze sau nu rezultatul prelucrrii.

10.3.2.2. Studiu de caz 2

n acest cazul 2 de studiu, implementarea structurilor de adiacene se bazeaz pe structuri

multilist.

Astfel, o structur de adiacene este de fapt o list nlnuit a nodurilor grafului.

Pentru fiecare nod al acestei liste se pstreaz o list a arcelor, adic o list nlnuit a cheilor nodurilor adiacente.

Cu alte cuvinte, o structur de adiacene n acest context este o list de liste.

n consecin, fiecare nod al listei nodurilor va conine dou nlnuiri, una indicnd nodul urmtor, cealalt, lista nodurilor adiacente.

n figura 10.3.2.2.a apare structura de adiacene (b) a grafului (a).

Fig.10.3.2.2.a. Reprezentarea unui graf ca i o structur de adiacene utiliznd structuri multilist

a e

c d

(a)

b

g

TipAdj cheieAdj urmAdj

TipNod elem urmNod incepAdj

v1 v2 e d a

a

b

c

d

e

e c a

d c

d c

indicArc

indicNod

(b)

Implementarea PASCAL a structurii multilist apare n secvena [10.3.2.2.a]. ------------------------------------------------------------ {Cazul 2. Implementarea grafurilor utiliznd structuri de adiacene implementate cu ajutorul structurilor multilist} type TipCheie = .....; TipInfo = .....; TipElement = record cheie: TipCheie; info : TipInfo end; RefTipAdj = ^TipAdj;

TipAdj = record cheieAdj: TipCheie; urmAdj : RefTipAdj end; RefTipNod = ^TipNod; TipGraf = RefTipNod; TipNod = record elem : TipElement; urmNod : RefTipNod; incepAdj: RefTipAdj [10.3.2.2.a] end; TipArc = record v1,v2: RefTipNod end; var g: TipGraf; indicNod: RefTipNod; indicArc: TipArc; k,k1,k2: TipCheie; e: TipElement; -------------------------------------------------------------

Se face precizarea c valorile aferente nodurilor sunt pstrate integral n lista de noduri, n lista de arce aprnd numai cheile.

Este posibil ca cmpul info s lipseasc i deci TipElement=TipCheie.

n figura 10.3.2.2.a apare reprezentarea unei structuri de adiacene implementate cu multiliste cu precizarea cmpurilor aferente.

De asemenea sunt prezentate ca exemplu variabilele g, indicNod i indicArc, evideniindu-se structura fiecreia.

n cadrul acestei structuri de date:

Operatorii CautCheieGraf, IndicNod i IndicArc aparinnd setului de operatori extins (varianta 1) utilizeaz tehnica cutrii liniare n determinarea unui nod a crui cheie este cunoscut.

Inseria unui nod nou se realizeaz simplu la nceputul listei nodurilor.

Operatorul InserArc(g: TipGraf; k1, k2 : TipCheie) presupune inseria lui k1 n lista de adiacene a lui k2 i reciproc.

i n acest caz inseria se realizeaz cel mai simplu la nceputul listei.

Suprimarea unui arc precizat spre exemplu de indicatorul indicArc presupune extragerea a dou noduri din dou liste de adiacene diferite.

Astfel n figura 10.3.2.2.a, variabila indicArc conine doi pointeri v1 i v2, care indic cele dou noduri conectate din lista de noduri.

n vederea suprimrii arcului care le conecteaz este necesar ca fiecare nod n parte s fie suprimat din lista de adiacene a celuilalt.

n cazul ilustrat, pentru a suprima arcul (a,c)=(c,a) se scoate a din lista lui c, respectiv c din lista lui a.

Procedura care realizeaz suprimarea n aceast manier a unui arc apare n secvena [10.3.2.2.b]

Se face precizarea c procedura SuprimArc este redactat n termenii setului de operatori aplicabili obiectelor aparinnd lui TDA List [Vol 1. &6.2.1].

----------------------------------------------------{Suprimarea unui arc. n implementare se utilizeaz operatorii definii pentru TDA Lista nlnuit simpl}

--------

procedure SuprimArc(g: TipGraf; indicArc: TipArc); var ik1,ik2: RefTipAdj; begin ik1:= Cauta(indicArc.v1^.elem.cheie, indicArc.v2^.incepAdj); ik2:= Cauta(indicArc.v2^.elem.cheie, indicArc.v1^.incepAdj); [10.3.2.2.b] Suprima(ik1,indicArc.v2^.incepAdj); Suprima(ik2,indicArc.v1^.incepAdj) end; {SuprimArc} ------------------------------------------------------------

n figura 10.3.2.2.b apare structura de adiacene aferent grafului din figura 10.3.2.2.a(a) dup suprimarea arcului (a,c).

Fig.10.3.2.2.b. Structur de adiacene dup suprimarea unui arc (a,c)

a e

c d

(a)

b

e c a

g

e d

a

b

c

d

e d c

d

indicArc

(b)

Suprimarea unui nod dintr-o structur de graf, presupune nu numai suprimarea propriu-zis a nodului respectiv ci n plus suprimarea tuturor arcelor incidente acestui nod.

n acest scop, se determin cheia k1 a nodului de suprimat.

n continuare, att timp ct mai exist elemente n lista sa de adiacente se realizeaz urmtoarea secven de operaii:

(1) Se determin cheia k2 a primului element din lista de adiacene a lui k1;

(2) Se suprim arcul (k1,k2) suprimnd pe k2 din lista lui k1 i pe k1 din lista lui k2;

n final se suprim nodul k1 din lista nodurilor grafului.

Procedura care realizeaz suprimarea unui nod apare n secvena [10.3.2.2.c]

Se face de asemenea precizarea c procedura SuprimNod este redactat n termenii setului de operatori aplicabili obiectelor aparinnd lui TDA List [Vol 1. &6.2.1].

------------------------------------------------------------ {Suprimarea unui nod. n implementare se utilizeaz operatorii definii pentru TDA List nlanuit simpl} procedure SuprimNod(g: TipGraf; indicNod: RefTipNod); var k1,k2 : TipCheie; indicNod2 : REfTipNod; ik1,curent: PtrAdj; [10.3.2.2.c] begin k1:= indicNod^.elem.cheie; curent:= indicNod^.incepAdj; WHILE not Fin(curent) do begin k2:= (Primul(curent))^.cheieAdj; Suprima(Primul(curent),curent); {Se presupune ca operatorul Suprima actualizeaz n mod corespunzator valoarea variabilei "curent" nemaifiind necesar trecerea explicit la elementul urmator al listei indicate de "curent". Se precizeaz faptul ca n aceast situaie este vorba despre o suprimare a primului element al listei} indicNod2 := Cauta(k2,g); ik1:= Cauta(k1,indicNod2^.incepAdj); Suprima(ik1,indicNod2^.incepAdj); end Suprima(indicNod,g) end; {SuprimNod} ------------------------------------------------------------

n fig.10.3.2.2.c apare reprezentat structura de adiacene rezultat n urma suprimrii nodului d din graful din figura 10.3.2.2.b.

Fig.10.3.2.2.c. Structur de adiacene dup suprimarea unui nod (d). 10.4. Tehnici fundamentale de traversare a grafurilor

c

g

e a

a

b

c

e

c

(b)

a e

c

(a)

b

Rezolvarea eficient a problemelor curente referitoare la grafuri, presupune de regul, traversarea (vizitarea sau parcurgerea) nodurilor i arcelor acestora ntr-o manier sistematic.

n acest scop s-au dezvoltat dou tehnici fundamentale, una bazat pe cutarea n adncime, cealalt bazat pe cutarea prin cuprindere.

10.4.1. Traversarea grafurilor prin tehnica cutrii n adncime (Depth- First Search)

Cutarea n adncime este una dintre tehnicile fundamentale de traversare a grafurilor.

Aceast tehnic este similar traversrii n preordine a arborilor i ea constituie nucleul n jurul cruia pot fi dezvoltai numeroi algoritmi eficieni de prelucrare a grafurilor.

Principiul cutrii n adncime ntr-un graf G este urmtorul:

Se marcheaz iniial toate nodurile grafului G cu marca nevizitat.

Cutarea debuteaz cu selecia unui nod n a lui G pe post de nod de pornire i cu marcarea acestuia cu vizitat.

n continuare, fiecare nod nevizitat adiacent lui n este cutat la rndul su, aplicnd n mod recursiv aceeai cutare n adncime.

Odat ce toate nodurile la care se poate ajunge pornind de la n au fost vizitate n maniera mai sus precizat, cercetarea lui n este terminat.

Dac n graf au rmas noduri nevizitate, se selecteaz unul dintre ele drept nod nou de pornire i procesul se repet pn cnd toate nodurile grafului au fost vizitate.

Aceast tehnic se numete cutare n adncime ("depth-first") deoarece parcurgerea grafului se realizeaz naintnd n adncime pe o direcie aleas atta timp ct acest lucru este posibil.

Spre exemplu, presupunnd c x este ultimul nod vizitat, cutarea n adncime selecteaz un arc neexplorat conectat la nodul x.

Fie y nodul corespunztor acestui arc.

Dac nodul y a fost deja vizitat, se caut un alt arc neexplorat conectat la x.

Dac y nu a fost vizitat anterior, el este marcat vizitat i se iniiaz o nou cutare ncepnd cu nodul y.

n momentul n care se epuizeaz cutarea pe toate drumurile posibile pornind de la y, se revine la nodul x, (principiul recursivitii) i se continu n aceeai manier selecia arcelor neexplorate ale acestui nod, pn cnd sunt epuizate toate posibilitile care deriv din x.

Se observ clar tendina iniial de adncire, de ndeprtare fa de surs, urmat de o revenire pe msura epuizrii tuturor posibilitilor de traversare.

Considernd o structur graf ntr-o reprezentare, oarecare i un tablou marc ale crui elemente corespunznd nodurilor grafului, marcheaz faptul c un nod a fost sau nu vizitat, schia de principiu a algoritmului de cutare n adncime apare n secvena [10.4.1.a].

------------------------------------------------------------ {Cautarea "n adancime". Schia de principiu a algoritmului. Varianta 1} procedure CautaInAdincime(x: TipNod); var y: TipNod; begin marc[x] := vizitat; [10.4.1.a] for fiecare nod y adiacent lui x do if marc[y] = nevizitat then CautaInAdincime(y) end; {CautaInAdincime} ------------------------------------------------------------ 10.4.1.1. Cutarea "n adncime", varianta CLR

O variant mai elaborat a traversrii n adncime este cea propus de Cormen, Leiserson i Rivest numit i cutare n adncime varianta CLR [CLR92].

Conform acestei variante, pe parcursul traversrii, nodurile sunt colorate pentru a marca strile prin care trec.

Din aceste motive traversarea grafurilor este cunoscut i sub denumirea de "colorare a grafurilor".

Culorile utilizate sunt alb, gri i negru.

Toate nodurile sunt iniial colorate n alb, n timpul traversrii devin gri iar la terminarea traversrii sunt colorate n negru.

Un nod alb care este descoperit prima dat n traversare este colorat.

n consecin, nodurile gri i negre au fost deja ntlnite n procesul de traversare, ele marcnd modul n care avanseaz traversarea.

Un nod este colorat n negru cnd toate nodurile adiacente lui au fost descoperite.

Un nod colorat n gri poate avea i noduri adiacente albe.

Nodurile gri marcheaz frontiera ntre nodurile descoperite i cele nedescoperite i ele se pstreaz de regul n structura de date asociat procesului de traversare.

n procesul de traversare se poate construi un subgraf asociat traversrii, subgraf care include arcele parcurse n traversare i care este de fapt un graf de precedene.

Acest subgraf este un graf conex aciclic, adic un arbore, care poate fi simplu reprezentat prin tehnica "indicator spre printe".

Tehnica de construcie a subgrafului este urmtoarea:

Atunci cnd n procesul de cutare se ajunge de la nodul u la nodul v, acest lucru se marcheaz n subgraful asociat s prin s[v]=u.

Graful de precedene este descris formal conform urmtoarelor relaii [10.4.1.1.a].

------------------------------------------------------------ Gpred = (N,Apred) Apred = {(s[v],v): vA & s[v]nil} [10.4.1.1.a] ------------------------------------------------------------

Subgraful predecesorilor asociat cutrii n adncime ntr-un graf precizat, formeaz o pdure de arbori de cutare n adncime.

Pe lng crearea propriu-zis a subgrafului predecesorilor fiecrui nod i se pot asocia dou mrci de timp ("timestamps"):

(1) i[v] memoreaz momentul descoperirii nodului v (colorarea sa n gri),

(2) f[v] memoreaz momentul terminrii explorrii nodurilor adiacente lui v (colorarea se in negru).

Mrcile de timp sunt utilizate n muli algoritmi referitori la grafuri i ele ofer indicii despre comportamentul n timp al algoritmilor

n cazul de fa, pentru simplitate, timpul este conceput ca un ntreg care ia valori ntre 1 i 2|N|, ntruct este incrementat cu 1 la fiecare descoperire respectiv terminare de examinare a fiecruia din cele |N| noduri ale grafului.

Varianta de cutare n adncime propus de Cormen, Lesiserson i Rivest apare n secvena [10.4.1.1.b]

------------------------------------------------------------ {Cautarea "n adancime". Schia de principiu a algoritmului. Varianta 2 (Cormen, Leiserson, Rivest} procedure TraversareInAdincime(G: TipGraf); [1] fie begin

for care nod u N(G) do [2] culoare[u]

n continuare se detaliaz aceast tehnic de cutare pentru diferite modaliti de implementare a grafurilor.

10.4.1.2. Cutare n adncime n grafuri reprezentate prin structuri de adiacene

Procedura care implementeaz cutarea n adncime n grafuri reprezentate prin structuri de adiacene apare n secvena [10.4.1.2.a].

Procedura Traversare1 completeaz tabloul marc[1..maxN] pe msur ce sunt traversate (vizitate) nodurile grafului.

Tabloul marc este poziionat iniial pe zero, astfel nct marc[x]=0 indic faptul c nodul x nu a fost nc vizitat.

Pe parcursul traversrii cmpul marc corespunztor unui nod x se completeaz n momentul nceperii vizitrii cu valoarea id, valoare care se incrementeaz la fiecare nod vizitat i care indic faptul c nodul x este cel de-al id-lea vizitat.

Procedura de traversare utilizeaz procedura recursiv CautaInAdncime care realizeaz vizitarea tuturor nodurilor aparintoare acelei componente conexe a grafului, creia i aparine nodul furnizat ca parametru.

Se face precizarea c procedura Traversare1 din secvena [10.4.1.2.a] se refer la reprezentarea TDA graf bazat pe structuri de adiacen implementate cu ajutorul listelor nlnuite simple.

------------------------------------------------------------ {Traversarea "n adancime" a grafurilor reprezentate prin structuri de adiacene implementate cu ajutorul listelor nlnuite simple.} procedure Traversare1; var id,x: integer; marc: array[1..maxN] of integer; procedure CautaInAdincime(x: integer); var t: RefTipNod; begin id:= id + 1; marc[x]:= id; write(t^.nume); t:= Stradj[x]; while t nil do [10.4.1.2.a] begin if marc[t^.nume] = 0 then CautaInAdincime(t^.nume); t:= t^.urm end end; {CautaInAdincime} begin { Traversare1 } id:= 0; for x:= 1 to N do marc[x]:= 0;

for x:= 1 to N do if marc[x] = 0 then begin utaInAdincime(x); writeln Ca end end; { Travesare1 } ------------------------------------------------------------

Vizitarea unui nod presupune parcurgerea tuturor arcelor conexe lui, adic parcurgerea listei sale de adiacene i verificarea pentru fiecare arc n parte, dac el conduce la un nod care a fost sau nu vizitat.

n caz c nodul este nevizitat procedura se apeleaz recursiv pentru acel nod.

Procedura Traversare1, parcurge tabloul marc i apeleaz procedura de CautaInAdancime pentru componentele nevizitate ale grafului, pn la traversarea sa integral.

Trebuie observat faptul c fiecare apel al procedurii CautaInAdncime realizat din cadrul procedurii Traversare1 asigur parcurgerea unei componente conexe a grafului i anume a componentei conexe care conine nodul selectat.

n figura 10.4.1.2.a apare urma execuiei algoritmului de cutare n adncime pentru graful (a) din figur.

Structura de adiacene aferent grafului apare n aceeai figur (b)

Evoluia coninutului stivei apare n n aceeai figur (c).

Se menioneaz faptul c nodurile structurii de adiacene au ataat un exponent fracionar care:

La numrtor precizeaz momentul la care este descoperit nodul, adic momentul n care este introdus n stiv

La numitor, momentul terminrii explorrii nodului, adic momentul n care este scos din stiv.

Fig.10.4.1.2.a. Urma execuiei algoritmului recursiv de cutare n adncime

A G

F

B C

E

D

(a)

1/14A 2/ F 10/ C 12/ B G 12/13B A 10/11C A 6/7D F E 3/8E 4/ G F 6/ D 2/9F A 3/ E D 4/5G E A

(b)

(c)

A A A A A A A A A A A A A

F F F F F F F C B

1 2 3 4 5 6 7 8 9 10 11 12 13 14 A F E G D C B

E E E E E

G D

Graful este traversat drept consecin a apelului CautInAdncime(A), efectuat n ciclul for al procedurii Traversare1.

Procesul de traversare pentru graful din fig. 10.4.1.2.a (a) se desfoar dup cum urmeaz:

Iniial nodul A este introdus n stiv la momentul 1.

Pentru nodul A se parcurge lista sa de adiacene, primul arc traversat fiind AF, deoarece F este primul nod din lista de adicene a lui A.

n continuare se apeleaz procedura CautInAdncime pentru nodul F, n consecin nodul F este introdus n stiv la momentul 2 i se traverseaz arcul FA, A fiind primul nod din lista de adiacene a lui F.

ntruct nodul A a fost deja descoperit (intrarea sa n tabloul marc conine o valoare nenul), se alege n continuare arcul FE, E fiind nodul urmtor n lista de adiacene a lui F.

Nodul E se introduce n stiv la momentul 3.

Se traverseaz n continuare arcul EG (G se introduce n stiv la momentul 4) G fiind primul nod din lista de adiacene a lui E.

n continuare se traverseaz arcul GE respectiv GA (nodurile E respectiv A fiind deja descoperite), moment n care se termin parcurgerea listei de adiacene a lui G, fapt realizat la timpul 5.

Se elimin G din stiv, se revine n lista nodului E i se continu parcurgerea listei sale de adiacene traversnd arcele EF (nodul F a fost deja vizitat) i ED.

Ca atare nodul D este descoperit la momentul 6 i n continuare vizita lui D presupune traversarea arcelor DE i DF care niciunul nu conduce la un nod nou.

Terminarea parcurgerii listei de adiacene a lui D are drept consecuin finalizarea vizitrii lui i scoaterea din stiv la momentul 7.

Se revine n lista de adiacene a lui E. Deoarece D a fost ultimul nod din lista de adiacene a lui E, vizita lui E se ncheie la momentul 8 i revine n nodul F a crui vizitare se ncheie prin parcurgerea arcului FD (D deja vizitat).

Se elimin F din stiv la momentul 9, se revine n lista lui A i se gsete nodul C nevizitat nc.

C se introduce n stiv la momentul 10, i se parcurge lista care l conine doar pe A deja vizitat i este extras din stiv la momentul 11.

Se continu parcurgerea listei de adiacene a nodului A i se gsete nodul B care sufer un tratament similar lui C, la momentele 12 respectiv 13.

n final se ajunge la sfritul listei lui A, A se scoate din stiv la momentul 14 i procesul de traversare se ncheie.

Un alt mod de a urmri desfurarea operaiei de cutare n adncime este acela de a redesena graful traversat pornind de la apelurile recursive ale procedurii CautInAdncime, ca n figura 10.4.2.1.b.

Fig.10.4.2.1.b. Arbori de cutare n adncime

A G

F

B C

E

D

H I

J K

L

M

(a)

A

F C B

E

G D

H

J I

K

M

L

(b)

n figura 10.4.2.1.b:

O linie continu indic faptul c nodul aflat la extremitatea sa inferioar, a fost gsit n procesul de cutare n lista de adiacene a nodului aflat la extremitatea sa superioar i nefiind vizitat la momentul considerat, s-a realizat pentru el un apel recursiv al procedurii de cutare.

O linie punctat indic un nod descoperit n lista de adiacene a nodului surs, pentru care apelul recursiv nu se realizeaz, deoarece nodul a fost deja vizitat sau este in curs de vizitare adic este memorat n stiva asociat prelucrrii.

Ca atare condiia din instrucia if a procedurii CautInAdncime nu este ndeplinit nodul fiind marcat cu vizitat n tabloul marc i n consecin pentru acest nod nu se realizeaz un apel recursiv al procedurii.

Aplicnd aceast tehnic, pentru fiecare component conex a unui graf se obine un arbore de acoperire ("spanning tree") numit i arbore de cutare n adncime al componentei.

La traversarea acestui arbore n preordine se obin nodurile n ordinea n care sunt prima dat ntlnite n procesul de cutare

La traversarea sa n postordine furnizeaz nodurile n ordinea n care cercetarea lor se ncheie.

Este important de subliniat faptul c ntruct ramurile arborilor de acoperire, materializeaz arcele grafului, mulimea (pdurea) arborilor de cutare n adncime asociai unui graf reprezint o alt metod de reprezentare grafic a grafului.

O proprietate esenial a arborilor de cutare n adncime pentru grafuri neorientate este aceea c liniile punctate indic ntotdeauna un strmo al nodului n cauz.

n orice moment al execuiei algoritmului, nodurile grafului se mpart n trei clase:

(1) Clasa I - conine nodurile pentru care procesul de vizitare s-a terminat (colorate n negru)

(2) Clasa II - conine nodurile care sunt n curs de vizitare (colorate n gri)

(3) Clasa III - conine nodurile la care nu s-a ajuns nc (colorate n alb).

(1) n ceea ce privete prima clas de noduri, datorit modului de implementare a procedurii de cutare, nu va mai fi selectat nici un arc care indic vreun astfel de nod.

(2) n ceea ce privete clasa a III-a de noduri, aceasta cuprinde nodurile pentru care se vor realiza apeluri recursive i arcele care conduc la ele vor fi marcate cu linie continu n arbore.

(3) Mai rmn nodurile din cea de-a doua clas: acestea sunt nodurile care au aprut cu siguran n drumul de la nodul curent la rdcina arborelui, sunt colorate n gri i sunt memorate n stiva asociat cutarii.

Ca atare, orice arc procesat care indic vreunul din aceste noduri apare reprezentat cu linie punctat n arborele de cutare n adncime.

n concluzie:

Arcele marcate continuu n figura 10.4.1.2.b se numesc arce de arbore

Arcele marcate punctat se numesc arce de retur

10.4.1.3. Cutare n adncime n grafuri reprezentate prin matrici de adiacene

Procedura care implementeaz cutarea n adncime n grafuri reprezentate prin matrici de adiacene apare n secvena [10.4.1.3.a].

Traversarea listei de adiacene a unui nod din cazul anterior, se transform n parcurgerea liniei corespunztoare nodului din matricea de adiacene, cutnd valori adevrate (care marcheaz arce).

Ca i n cazul anterior, selecia unui arc care conduce la un nod nevizitat este urmat de un apel recursiv al procedurii de cutare pentru nodul respectiv.

Datorit modului diferit de reprezentare a grafului, arcele conectate la noduri sunt examinate ntr-o alt ordine, motiv pentru care arborii de cutare n adncime care alctuiesc pdurea corespunztoare grafului difer ca form.

------------------------------------------------------------ {Cutare "n adncime" n grafuri reprezentate prin matrici de adiacene} procedure CautaInAdincime1(x: integer); var t: integer; begin id:= id + 1; marc[x]:= id; write(x); [10.4.1.3.a] for t:= 1 to N do if A[x,t] then if marc[t] = 0 then CautaInAdincime1(t) end; { CautaInAdincime1 } ------------------------------------------------------------

Pentru graful din figura 10.4.1.3.a (a), a crui matrice de adiacene apare n aceeai figur (b), evoluia stivei asociate traversrii apare n (c) i (d) iar arborii de cutare n adncime corespunztori apar n fig. 10.4.1.3.b.

Fig.10.4.1.3.a.Cutare n adncime n grafuri reprezentate prin matrice de adiacene

Fig.10.4.1.3.b. Pdure de arbori de cutare n adncime n grafuri reprezentate prin matrice de adiacene

A G

F

B C

E

D

H I

J K

L

M

(a)

(d)

H H H H H H H L L L

I J J J M

15 16 17 18 19 20 21 22 23 24 25 26 H I J K L M

K(c)

A A A A A A A A A A A A A

B C F F F F F

1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C F D E G

D D

E

F F

D D D

E E

G

A B C D E F G H I J K L M A 0 1 1 0 0 1 1 B 1 0 0 0 0 0 0 C 1 0 0 0 0 0 0 D 0 0 0 0 1 1 0 E 0 0 0 1 0 1 1 F 1 0 0 1 1 0 0 G 1 0 0 0 1 0 0 H 0 1 1 1 I 1 0 0 0 J 1 0 0 1 K 1 0 0 1 L 0 1 M 1 0

(b)

H

J I

K

M

L A

B C F

E

G

D

Se observ unele diferene fa de pdurea de arbori reprezentat n fig. 10.4.2.1.b, corespunztoare aceluiai graf.

Prin aceasta se subliniaz faptul c o pdure de arbori de cutare n adncime nu este altceva dect o alt manier de reprezentare a unui graf, a crei alctuire particular depinde att de metoda de traversare a grafului ct i de reprezentarea intern utilizat.

Din punct de vedere al eficienei, cutarea n adncime n grafuri reprezentate prin matrice de adiacene necesit un timp proporional cu O(n2).

Acest lucru este evident ntruct n procesul de traversare este verificat fiecare element al matricei de adiacene.

Cutarea n adncime rezolv unele probleme fundamentale ale prelucrrii grafurilor.

Astfel, deoarece procedura de parcurgere a unui graf se bazeaz pe traversarea pe rnd a componentelor sale conexe, numrul componentelor conexe ale unui graf poate fi determinat simplu contoriznd numrul de apeluri ale procedurii CautInAdncime efectuat din ultima linie a procedurii Traversare1.

Cutarea n adncime permite de asemenea verificarea simpl a existenei ciclurilor ntr-un graf.

Astfel, un graf conine un ciclu, dac i numai dac procedura CautInAdncime descoper o valoare diferit de zero n tabloul marc.

Aceast nseamn c se parcurge un arc care conduce la un nod care a mai fost vizitat, deci graful conine un ciclu.

n cazul grafurilor neorientate trebuie ns s se in cont de reprezentarea dubl a fiecrui arc, care poate produce confuzii.

Pentru reprezentarea grafurilor prin pdure de arbori de cutare, liniile punctate sunt acelea care nchid ciclurile.

10.4.2. Traversarea grafurilor prin tehnica cutrii prin cuprindere (Breadth-First Search)

O alt manier sistematic de traversare a nodurilor unui graf o reprezint cutarea prin cuprindere (breadth first search).

Cutarea prin cuprindere se bazeaz pe urmtoarea tehnic:

Pentru fiecare nod vizitat x, se caut n imediata sa vecintate cuprinznd n vederea vizitrii toate nodurile adiacente lui.

Pentru implementarea acestei tehnici de parcurgere, n locul stivei din metoda de cutare anterioar, pentru reinerea nodurilor vizate se poate utiliza o structur de date coad.

Schia de principiu a algoritmului de parcurgere apare n secvena [10.4.2.a].

Se precizeaz faptul c s-a utilizat o structur de date coad (Q) asupra creia acioneaz operatori specifici [Vol.1,&6.5.4.1, Cr00].

------------------------------------------------------------ {Cutare prin cuprindere. Schia de principiu. Varianta 1} procedure CautaPrinCuprindere(x: TipNod; T: TipMultime); {se parcurg toate nodurile adiacente lui x prin cutare prin cuprindere} var Q: CoadaDeNoduri; x,y: TipNod; marc: array[1..maxN] of integer; begin marc[x] := vizitat; Adauga(x,Q); while not Vid(Q) do [10.4.2.a] begin x := Cap(Q); Scoate(Q); for fiecare nod y adiacent lui x do if marc[y] = nevizitat then begin marc[y] := vizitat; Adauga(y,Q); INSERTIE((x,y),T) end end end; {CautaPrinCuprindere} ------------------------------------------------------------

Algoritmul din secvena [10.4.2.a] insereaz arcele parcurse ale grafului ntr-o mulime T despre care se presupune c este iniial vid, cu ajutorul operatorului INSERTIE.

Se presupune de asemenea c tabloul marc este iniializat integral cu marca nevizitat.

Procedura lucreaz pentru o singur component conex.

Dac graful nu este conex, procedura CautPrinCuprindere trebuie apelat pentru fiecare component conex n parte.

Se atrage atenia asupra faptului c n cazul cutrii prin cuprindere, un nod trebuie marcat cu vizitat naintea ntroducerii sale n coad pentru a se evita plasarea sa de mai multe ori n aceast structur.

10.4.2.1. Cutarea "prin cuprindere", varianta CLR

Cutarea prin cuprindere este una dintre cele mai cunoscute metode de cutare, utilizate printre alii de ctre Djikstra i Prim n celebrii lor algoritmi [CLR92].

Ca i n cazul cutrii n adncime, pentru a ine evidena procesului de cutare nodurile sunt colorate n alb, gri i negru.

Toate nodurile sunt colorate iniial alb i ele devin mai trziu gri, apoi negre.

La prima descoperire a unui nod, acesta este colorat n gri.

Nodurile gri i negre sunt noduri deja descoperite n procesul de cutare, dar ele sunt difereniate pentru a se asigura funcionarea corect a cutrii.

Dac arcul(n,v) A iar n este un nod negru, v este colorat fie n gri fie n negru.

n ultimul caz toate nodurile adiacente lui v au fost deja vizitate.

Nodurile gri mai pot avea ca adiaceni i noduri albe, ele marcheaz de fapt frontiera dintre nodurile vizitate i cele nevizitate.

i n cazul cutrii prin cuprindere se poate construi un subgraf sp al predecesorilor nodurilor vizitate.

Ori de cte ori un nod v este descoperit pentru prima oar n procesul de cutare la parcurgerea listei de adiacene a nodului u, acest lucru se marcheaz prin sp[v]=u.

Dup cum s-a mai precizat subgraful predecesorilor este de fapt un arbore liber, reprezentat printr-un tablou liniar cu n baza relaiei indicator spre printe.

Procedura TraversarePrinCurpindere din secvena [10.4.2.1.a] presupune graful G=(N,A) reprezentat prin structuri de adiacene.

Culoarea curent a fiecrui nod u N este memorat n tabloul culoare[u]

Predecesorul nodului u adic nodul n lista cruia a fost descoperit, este nregistrat n tabloul sp[u].

Dac u nu are predecesor (adic este nodul de pornire) se marcheaz acest lucru prin sp[u]=nil.

n cadrul procesului de traversare a grafului, se calculeaz i distana de la nodul de start la fiecare din nodurile grafului.

Distana de la surs la nodul curent u calculat de ctre algoritmi este memorat n tabloul d[u].

Algoritmul de traversare utilizeaz o coad FIFO notat cu Q pentru a gestiona nodurile implicate n procesul de cutare, scop n care face uz de operatorii consacrai pentru aceast structur de date.

------------------------------------------------------------ {Cutarea prin cuprindere. Schia de principiu. Varianta 2. (Cormen, Leiserson, Rivest)}

CautaPrin Cuprindere(G:TipGraf,s:TipNod); [1] for fiecare nod uN(G) do begin [2] culoare[u]

Linia 10 furnizeaz nodul gri u aflat n capul cozii Q.

Bucla for (liniile 11-16) parcurge fiecare nod v al listei de adiacene a lui u.

Dac v este alb, el nu a fost nc descoperit, ca atare algoritmul l descoper executnd liniile 13-16 adic:

Nodul v este colorat n gri

Distana d[v] este setat pe d[u]+1 indicnd creterea acesteia cu o unitate n raport cu printele nodului

u este marcat ca i printe al lui v

n final v este adugat n coada Q la sfritul acesteia.

Dup ce toate nodurile listei de adiacene a lui u au fost examinate, u este extras din coada Q i colorat n negru (liniile 17-18).

Analiza performanei.

Se analizeaz timpul de execuie al algoritmului pentru un graf G=(N,A).

Dup iniializare nici un nod nu mai este ulterior colorat n alb, ca atare testul din linia 12 asigur faptul c fiecare nod este adugat cozii cel mult odat i este scos din coad cel mult odat.

Operaiile Adauga i Scoate din coad consum un timp O(1), ca atare timpul total dedicat operrii cozii Q este O(N).

Deoarece lista fiecrui nod este scanat exact naintea scoaterii nodului din coad aceast operaie se realizeaz cel mult odat pentru fiecare nod.

Deoarece suma lungimilor tuturor listelor de adiacen este O(A), timpul total necesar pentru scanarea listelor de adiacene este cel mult O(A).

Regia iniializrii este O(N) deci timpul total de execuie al procedurii CautPrinCurpindere este O(N+A).

n concluzie, cutarea prin cuprindere necesit un timp de execuie liniar cu mrimea listelor de adiacene ale reprezentrii grafului G.

10.4.2.2. Cutare prin cuprindere n grafuri reprezentate prin structuri de adiacene

n secvena [10.4.2.2.a] apare un exemplu de procedur care parcurge un graf n baza tehnicii de parcurgere prin cuprindere, utiliznd o structur de date coad.

Graful de consider reprezentat cu ajutorul structurilor de adiacene implementate cu liste nlnuite simple.

------------------------------------------------------------ {Traversarea prin cuprindere a grafurilor reprezentate prin SA implementate cu ajutorul listelor nlnuite simple} procedure ParcurgerePrinCuprindere; var id,x: integer; mark: array[1..maxN] of integer; procedure CautaPrinCuprindere(x: integer); var t: RefTipNod; begin Adauga(x,Q); repeat x:= Cap(Q); Scoate(Q); id:= id + 1; marc[x]:= id; write(x); tradj[ t:= S x]; while t nil do begin if marc[t^.nume]=0 then [10.4.2.2.a] begin Adauga(t^.nume,Q); marc[t^.nume]:=-1 end t:= t^.urm end until Vid(Q) end; {CautaPrinCuprindere} begin {ParcurgerePrinCuprindere} id:= 0; Initializeaza(Q); for x:= 1 to N do marc[x]:= 0; for x:= 1 to N do if marc[x]=0 then begin CautaPrinCuprindere(x); writeln end end; {ParcurgerePrinCuprindere} ------------------------------------------------------------- n figura 10.4.4.2.a se prezint un exemplu de traversare prin cuprindere a unui graf

reprezentat prin structuri de adiacene.

Fig.10.4.2.2.a. Traversarea prin cuprindere a unui graf

A F C B G B A C A D F E E G F D F A E D G E A H I J K I H J H K K H J L M M L

(b)

(c)

A

C

B

G

B

G G

D

H

K K

M

L

F

E

D D

E

J J

I

K

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 A F C B G E D H I J K L M

C

G

E

D D

B

E

A G

F

B C

E

D

H I

J K

L

M

(a)

L

M

A

G F B C

E D

H

I J K

(d)

Se consider graful din figura 10.4.2.2.a (a) reprezentat prin structura de adiacene din aceeai figur (b),

Ordinea de parcurgere a arcelor va fi urmtoarea: AF,AC,AB,AG,FA,FE,FD,CA, BA,GE,GA,DF,DE,EG,EF,ED,HI,HJ,HK,IH,JH,JK,KH,KJ,IM,MI.

Evoluia coninutului cozii pe parcursul traversrii i ordinea n care sunt traversate nodurile apar n fig. 10.4.2.2.a (c).

n mod similar cu traversarea bazat pe cutarea n adncime, se poate construi o pdure de arbori de acoperire ("spanning trees") specific cutrii prin cuprindere.

n acest caz, un arc (x,y) se consider ramur a arborelui de cutare, dac n bucla for a secvenei [10.4.2.a], respectiv while a secvenei [10.4.2.2.a] nodul y, respectiv t^.urm este vizitat ntia dat venind dinspre nodul x.

n cazul cutrii prin cuprindere n grafuri neorientate, fiecare arc care nu este o ramur a arborelui de cuprindere, este un arc de trecere care conecteaz dou noduri dintre care niciunul nu este strmoul celuilalt.

Arborii de cutare afereni parcurgerii grafului (a) din figura fig. 10.4.2.2.a apar n aceeai figur (d).

Dup cum s-a precizat, aceti arbori cuprind acele arce care conduc ntia dat la un anumit nod.

Utiliznd arbori de cutare prin cuprindere, verificarea existenei ciclurilor n cadrul unui graf, poate fi realizat n O(n) uniti de timp, indiferent de numrul de arce.

Dup cum s-a precizat n 10.1, un graf cu n noduri i n sau mai multe arce, trebuie s aib cel puin un ciclu.

Cu toate acestea i un graf cu n noduri i n-1 sau mai puin arce poate avea cicluri, dac conine dou sau mai multe componente conexe.

O modalitate sigur de a determina ciclurile unui graf este aceea de a-i construi pdurea arborilor de cutare prin cuprindere.

Fiecare arc de trecere, reprezentat punctat n figur, nchide un ciclu simplu care cuprinde arcele arborelui care conecteaz cele dou noduri, prin cel mai apropiat strmo comun al lor.

10.4.2.3. Analiza cutrii prin cuprindere

Din punctul de vedere al timpului de execuie, complexitatea algoritmului de traversare (cutare) prin cuprindere este aceeai ca i la cutarea n adncime.

Fiecare nod al grafului este plasat n coad o singur dat, astfel corpul buclei while (secvena [10.4.2.2.a]) se execut o singur dat pentru fiecare nod.

Fiecare arc (x,y) este examinat de dou ori, odat pentru x i odat pentru y.

Astfel, dac graful are n noduri i a arce, timpul de execuie al algoritmului de cutare prin cuprindere este O(max (n,a)) dac utilizm reprezentarea prin structuri de adiacen.

Deoarece n general an, de regul se va considera timpul de execuie al cutrii prin cuprindere O(a), ca i n cazul cutrii n adncime.

10.4.3. Comparaie ntre tehnicile fundamentale de traversare a grafurilor

Traversarea unui graf, indiferent de metoda utilizat, are principial un caracter unitar, particularizarea rezultnd din structura de date utilizat n implementare. Astfel, n ambele tehnici de traversare, nodurile pot fi divizate n trei clase:

(1) Clasa "arbore" care cuprinde nodurile care au fost extrase din structura de date utilizat n traversare, adic nodurile deja vizitate colorate n negru;

(2) Clasa "vecintate" care cuprinde nodurile adiacente nodurilor traversate sau n curs de traversare.

Aceste noduri au fost luate n considerare dar nu au fost nc vizitate i se gsesc introduse n structura de date utilizat n traversare.

Sunt nodurile colorate n gri;

(3) Clasa "nentlnite" - care cuprinde nodurile la care nu s-a ajuns pn la momentul considerat, adic cele colorate n alb.

Un arbore de cutare ia natere conectnd fiecare nod din clasa arbore cu nodul care a cauzat introducerea sa n structura de date utilizat n parcurgere.

Pentru a parcurge n mod sistematic o component conex a unui graf (deci pentru a implementa o procedur parcurge) se introduce un nod oarecare al componentei n clasa vecintate i toate celelalte noduri n clasa nentlnite.

n continuare, pn la vizitarea tuturor nodurilor se aplic urmtorul procedeu:

(1) Se mut un nod fie acesta x din clasa vecintate n clasa arbore

(2) Se trec n clasa vecintate toate nodurile din clasa nentlnite care sunt adiacente lui x.

Metodele de parcurgere a grafurilor se difereniaz dup maniera n care sunt alese nodurile care se trec din clasa vecintate n clasa arbore.

(1) La parcurgerea n adncime se alege din vecintate nodul cel mai recent ntlnit (ultimul ntlnit) ceea ce corespunde cu utilizarea unei stive pentru pstrarea nodurilor din vecintate.

(2) La parcurgerea prin cuprindere se alege nodul cel mai devreme ntlnit (primul ntlnit) ceea ce presupune pstrarea ntr-o coad a nodurilor din clasa vecintate.

Se pot utiliza n acest scop i alte structuri de date, spre exemplu cozi bazate pe prioritate [Cr 87] n cazul grafurilor ponderate.

Contrastul dintre cele dou metode de parcurgere este i mai evident n cazul grafurilor de mari dimensiuni.

Cutarea n adncime se avnt n profunzime de-a lungul arcelor grafului, memornd ntr-o stiv punctele de ramificaie.

Cutarea prin cuprindere mtur prin extindere radial graful, memornd ntr-o coad frontiera locurilor deja vizitate.

La cutarea n adncime graful este explorat cutnd noi noduri, ct mai departe de punctul de plecare i lund n considerare noduri mai apropiate numai n situaia n care nu se poate nainta mai departe

Cutarea prin cuprindere acoper complet zona din jurul punctului de plecare mergnd mai departe numai cnd tot ceea ce este n imediatat sa apropiere a fost parcurs.

Este ns evident faptul c n ambele situaii, ordinea efectiv de parcurgere a nodurilor depinde:

(1) Pe de o parte de structura de date utilizat pentru implementarea grafului

(2) Pe alt parte de ordinea n care sunt introduse iniial nodurile n aceast structur.

n afara diferenelor rezultate din manierele de operare ale celor dou metode, se remarc diferene fundamentale n ceea ce privete implementarea.

Cutarea n adncime poate fi foarte simplu exprimat n manier recursiv ea bazndu-se pe o structur de date stiv

Cutarea prin cuprindere admite o implementare foarte simpl nerecursiv fiind bazat pe o structur de date coad.

Acesta este nc un exemplu care evideniaz cu pregnan legtura strns care exist ntre o anume structur de date i algoritmul care o prelucreaz.

10.5. Aplicaii ale traversrii grafurilor

n cadrul paragrafului de fa se prezint cteva dintre aplicaiile tehnicilor de traversare a grafurilor.

Se au n vedere n acest context:

Unele aspecte legate de conexitate

Punctele de articulaie ale unui graf

Componentele biconexe ale unui graf.

10.5.2. Grafuri i conexiuni

n cadrul grafurilor, noiunea de conexiune joac un rol central i ea este strns legat de noiunea de arc, respectiv de noiunea de drum.

Astfel n paragraful 10.1. se definesc pornind de la aceste elemente noiunile de graf conex, respectiv de component conex a unui graf.

Se reamintete c un graf conex este acela n care pentru fiecare nod al su exist un drum spre oricare alt nod al grafului.

Un graf care nu este conex este format din componente conexe.

Deoarece n anumite situaii prelucrarea grafurilor este simplificat dac grafurile sunt partajate n componentele lor conexe, n continuare se vor prezenta unele tehnici de determinare a componentelor conexe ale unui graf.

De asemenea sunt prezentate noiunile de graf biconex i punct de articulaie precum i tehnicile determinrii acestora.

10.5.2.1. Determinarea componenetelor conexe ale unui graf

Oricare dintre metodele de traversare a grafurilor prezentate n paragraful anterior poate fi utilizat pentru determinarea componentelor conexe ale unui graf.

Acest lucru este posibil deoarece toate metodele de traversare se bazeaz pe aceeai strategie general a vizitrii tuturor nodurilor dintr-o component conex nainte de a trece la o alt component.

O manier simpl de a vizualiza componentele conexe este aceea de a modifica procedura recursiv de traversare prin cutare n adncime spre exemplu aa cum se sugereaz n procedura ComponenteConexe secvena [10.5.2.1.a].

------------------------------------------------------------ {Determinarea componentelor conexe ale unui graf reprezentat prin SA implementate cu ajutorul listelor nlnuite simple} procedure Componente Conexe; var id,x: integer; marc: array[1.maxN] of integer; procedure Componenta(x: integer); var t: RefTipNod; begin id:= id+1; marc[x]:= id; write(t^.nume); rAd ]t:= St j[x ; while tnil do begin if marc[t^.nume]=0 then Componenta(t^.nume); t:= t^.urm end end; {Componenta} [10.5.2.1.a] begin 0; id:= for x:= 1 to N do marc[x]:= 0; for x:= 1 to N do if marc[x]=0 then

begin Componenta(x); writeln end end; {ComponenteConexe} ------------------------------------------------------------

Alte variante ale procedurii de cutare n adncime cum ar fi cea aplicat grafurilor reprezentate prin matrice de adiacene sau cea nerecursiv, precum i cutarea prin cuprindere, modificate n aceeai manier, vor evidenia aceleai componente conexe, dar nodurile vor fi vizualizate n alt ordine.

Funcie de natura prelucrrilor ulterioare ale grafului pot fi utilizate i alte metode.

Astfel spre exemplu, se poate introduce tabloul invmarc (inversul tabloului marc) care se completeaz ori de cte ori se completeaz tabloul marc, respectiv cnd marc[x]:= id se asigneaz i invmarc[id]:= x.

n tabloul invmarc intrarea id conine indexul celui de-al id-lea nod vizitat. n consecin, nodurile aparinnd aceleeai componente conexe sunt contigue n tabloul invmarc adic ocup poziii alturate.

n tabloul invmarc, indexul care precizeaz o nou component conex, este dat de valoarea lui id din momentul n care procedura Componenta este apelat din procedura ComponenteConexe.

Aceste valori pot fi memorate separat sau pot fi marcate n tabloul invmarc, spre exemplu primind valori negative (opuse).

n fig.10.5.2.1.a (c) se prezint valorile pe care le conin aceste tablouri, n urma execuiei procedurii ComponenteConexe asupra grafului (a), reprezentat prin structura de adiacene din aceeai figur (b).

x 1 2 3 4 5 6 7 8 9 10 11 12 13 nume[x] A B C D E F G H I J K L M marc[x] 1 7 6 5 3 2 4 8 9 10 11 12 13 invmarc[x] -1 6 5 7 4 3 2 -8 9 10 11 -12 13

A F C B G B A C A D F E E G F D F A E D G E A H I J K I H J H K K H J L M M L

A G

B C

D

F E

(b)

H I

J K

L

M

(a)

Fig. 10.5.2.1.a. Evidenierea componentelor conexe ale unui graf

n activitatea practic, este deosebit de avantajoas utilizarea unor astfel de tehnici de partajare a grafurilor n componente conexe n vederea prelucrrii ulterioare a acestor componente n cadrul unor algoritmi compleci.

Astfel, algoritmii de complexitate mai ridicat sunt eliberai de detaliile prelucrrii unor grafuri care nu sunt conexe i n consecin devin mai simpli.

10.5.2.2. Puncte de articulaie i componente biconexe

n anumite situaii este util a se prevedea mai mult dect un drum ntre nodurile unui graf cu scopul de a rezolva posibile cderi ale unor puncte de contact (noduri).

Astfel, spre exemplu n reeaua feroviar exist mai multe posibiliti de a ajunge ntr-un anumit loc.

De asemenea ntr-un circuit integrat liniile principale de comunicaie sunt adesea dublate astfel nct circuitul rmne nc n funciune dac vreo component cade.

Un punct de articulaie al unui graf conex este un nod, care dac este suprimat, graful se rupe n dou sau mai multe buci.

Un graf care nu conine puncte de articulaie se numete graf biconex.

ntr-un graf biconex, fiecare pereche de noduri este conectat prin cel puin dou drumuri distincte.

Un graf care nu este biconex se divide n componente biconexe, acestea fiind mulimi de noduri mutual accesibile via dou drumuri distincte.

n fig. 10.5.2.2.a apare un graf conex care ns nu este biconex.

Fig.10.5.2.2.a. Graf care nu este biconex

A G

F

B C

E

D

H I

J K

L M

Punctele de articulaie ale acestui graf sunt:

A care leag pe B de restul grafului

H care leag pe I de restul grafului,

L care leag pe M de restul grafului

G prin a crui suprimare graful se divide n trei pri.

n concluzie n cadrul grafului din figur exist ase componente biconexe:

(1) Grupul de noduri{A,C,G,D,E,F}

(2) {G,J,H,K}

(3) Nodul individual B

(4) Nodul individual I

(5) Nodul individual L

(6) Nodul individual M.

n acest context una din problemele care se ridic este aceea a determinrii punctelor de articulaie ale unui graf.

Se face precizarea c aceasta este una din mulimea de probleme deosebit de importante referitoare la conexitatea grafurilor.

Astfel, ca i un exemplu de aplicaie al conexitii grafurilor poate fi prezentat o reea care este de fapt un graf n care nodurile comunic unele cu altele.

n legatur cu aceast reea se ridic urmtoarea ntrebare fundamental: Care este capacitatea de supravieuire a reelei atunci cnd unele dintre nodurile sale cad?

Cu alte cuvinte n ce condiii, n urma cderii unor noduri reeaua rmne nc funcional?

Un graf are conexitatea k sau altfel spus are numrul de conexitate egal cu k dac prin suprimarea a oricare k-1 noduri ale sale graful rmne conex [FK69].

Spre exemplu, un graf are conexitatea doi, dac i numai dac nu are puncte de articulaie, cu alte cuvinte, dac i numai dac este biconex.

Cu ct numrul de conexitate al unui graf este mai mare, cu att capacitatea de supravieuire a grafului la cderea unora din nodurile sale este mai mare.

10.5.2.3. Determinarea punctelor de articulaie ale unui graf

n vederea determinrii punctelor de articulaie ale unui graf conex, poate fi utilizat, printr-o extensie simpl, traversarea grafurilor prin tehnica cutrii n adncime.

Absena punctelor de articulaie precizeaz un graf biconex.

Se consider spre exemplu, graful din figura 10.5.2.2.a i un arbore de cutare n adncime asociat, ca i cel din fig.10.5.2.3.a.

Fig.10.5.2.3.a. Arbore de cutare n adncime pentru determinarea punctelor de articulaie ale unui graf conex

Se observ c suprimarea nodului E nu conduce la dezmembrarea grafului deoarece ambii fii ai acestuia, G respectiv D sunt conectai prin arce de retur (linii punctate) cu noduri situate deasupra n arbore.

Pe de alt parte suprimarea lui G conduce la scindarea grafului deoarece nu exist astfel de alternative pentru nodurile L sau J.

Un nod oarecare x al unui graf nu este un punct de articulaie dac fiecare fiu y al su are printre descendeni vreun nod conectat (printr-o linie punctat) cu un nod situat n arbore deasupra lui x, cu alte cuvinte, dac exist o conexiune alternativ de la x la y.

Aceast verificare nu este valabil pentru rdcina arborelui de cutare n adncime deoarece nu exist noduri situate deasupra acesteia.

Rdcina este un punct de articulaie dac are doi sau mai muli fii deoarece singurul drum care conecteaz fii rdcinii trece prin rdcina nsi.

Determinarea punctelor de articulaie poate fi implementat pornind de la cutarea n adncime, prin transformarea procedurii de cutare ntr-o funcie care returneaz pentru nodul furnizat ca parametru, cel mai nalt punct din cadrul arborelui de cutare ntlnit n timpul cutrii, adic nodul cu cea mai mic valoare memorat n tabloul marc.

Algoritmul implementat n forma funciei Articulaie apare n secvena [10.5.2.3.a]

------------------------------------------------------------

G

L J C

H

I K

F

D

E

M

B

A

A G

F

B C

E

D

H I