UNIVERSITATEA “DUNĂREA DE JOS” GALAŢI

FACULTATEA TRANSFRONTALIERĂ DE ŞTIINŢE UMANISTE,

ECONOMICE ŞI INGINEREŞTI
SPECIALIZAREA: MATEMATICĂ INFORMATICĂ

LUCRARE DE LICENŢĂ

Structuri de date în limbajul java

Indrumător ştiinţific,

asist. Veronica Jâşcanu

Absolvent,

GALAŢI - 2008

1
 Cuprins

MOTIVAŢIA LUCRARII.............................................................................................................4
CAPITOLUL I
Concepţia structurii de grafuri.............................................................................5
1.1 Noţiuni generale .......................................................................................................................5
1.2 Noţiunea de graf........................................................................................................................5
1.2.1 Definiţia grafului neorientat şi orientat...................................................................................6
1.2.2 Moduri de reprezentare ale unui graf......................................................................................6
1.3 Noţiuni de baza în teoria grafurilor...........................................................................................8
1.3.1 Proprietăţi................................................................................................................................8
1.3.2 Ordinul unui graf.....................................................................................................................9
1.3.3 Gradul unui nod dintr-un graf................................................................................................10
1.3.4 Drumuri şi cicluri într-un graf...............................................................................................11
1.3.5 Conexiuni într-un graf...........................................................................................................13
CAPITOLUL II
Concepţia structurii de arbore.............................................................................16
2.1 Noţiuni generale......................................................................................................................16
2.1.1 Noţiunea de arbore, proprietăţi.............................................................................................16
2.1.2 Arbori cu rădăcină................................................................................................................20
2.2 Arbori binari…………………………………………………………………………………23
2.2.1 Definiţie…………………………………………………………………………………....24
2.2.2 Proprietăţile unui arbore binar……………………………………………………………..25
CAPITOLUL III
Algoritmul şi reprezentarea unui graf în limbajul java.........................................26
3.1 Probleme de drumuri minime intr-un
graf..............................................................................26
3.1.1 Întroducere.............................................................................................................................27
3.1.2 Algoritmul lui Dijkstra..........................................................................................................27
3.2 Structuri de date utilizate în reprezentarea grafurilor..............................................................30
3.2.1 Matricea de adiacenţă............................................................................................................30
3.2.2 Liste de adiacenţă (vecinilor)................................................................................................31

2
3.3 Adăugarea vârfurilor şi a muchiilor într-un graf.....................................................................32
3.4 Reprezentarea stivelor şi cozilor în limbajul java....................................................................34
3.4.1 Stiva.......................................................................................................................................34
3.4.2 Coada....................................................................................................................................36
3.5 Algoritmul Depth-First Search (DFS) –parcurgerea în adâncime...........................................42
3.6 Algoritmul Breadth-First Search (BFS) – parcurgerea în lăţime............................................48
3.7 Algoritmul de căutare a unui arbore de acoperire de lungime minimă...................................52
3.7.1 Reprezentarea algoritmului...................................................................................................52
3.7.2 Întroducerea datelor de la tastatură.Importarea claselor.......................................................55
CAPITLUL IV
Interfeţe grafice. Reprezentarea aplicaţiei în limbajul java................................57
4.1 Interfeţe grafice.....................................................................................................................58
4.1.1. Componente grafice...........................................................................................................58
4.1.2. Peer....................................................................................................................................60
4.1.3 Afişarea componentelor......................................................................................................61
4.1.4 Organizarea componentelor................................................................................................61
4.2 Pachete AWT şi SWING.......................................................................................................63
4.2.1 Noţiuni generale..................................................................................................................63
4.2.2 Ferestre................................................................................................................................64
4.3 Elemente de control (widgets)................................................................................................65
4.3.1 Butoane................................................................................................................................65
[Link] RadioButton......................................................................................................................66
[Link] ListBox..............................................................................................................................66
4.4 REPREZENTAREA APLICAŢIEI........................................................................................67
CONCLUZII..................................................................................................................................74
BIBLIOGRAFIE............................................................................................................................75

3
 Motivaţia lucrării
Structurile de date reprezintă modalitatea în care datele sunt dispuse în memoria
calculatorului(sau păstrate pe disc).
Algoritmul reprezinta procedura pe care programele le efectuiaza pentru a manipula datele din
aceste structuri.
Lucrarea trateaza subiectul structurilor de date şi al algoritmilor utilizaţi în programarea la
calculator.În lucrare, voi trece în revistă, principalele structuri de date despre care vor fi analizate.
Printre alte structuri de date, se găsesc şi liste înlănţuite , arbori [Link] pot manipula
datele din aceste structuri în mai multe moduri, căutând un anumit element sau sortând datele.
Activitatea programului devine odata cu eliminările restricţiilor impuse de sistemele de calcul o
activitate de alocare si nivelare a resurselor [Link]-o multitudine de limbaje, medii de
programare si biblioteci de programe trebuie alese si asamblate acele componente care conduc la
produse program performante. Pentru efectuarea unei alegeri corespunzatoare, resursele trebuie
cunoscute în cele mai mici detalii.

Într-un context mai larg, structurile de date se constituie ca resurse la dispoziţia programatorilor,
care prin diversitate influenţeaza hotarâtor calitatea programelor. Diferenţa dintr-o aplicţie care
este conceputa pentru a nu utiliza fişiere şi aceeasi aplicaţie care utilizeaza fişiere se reflecta la
nivelul costurilor prin câştig sau pierdere, dupa cum soluţia aleasă este sau nu adecvată.

Rezolvarea unei probleme începe cu definirea structurilor de date, continua cu utilizarea acestora
si se încheie cu stocarea rezultatelor prelucrării, tot sub forma unor structuri de [Link]
structurilor de date revine la clasificarea datelor, a operaţiilor posibile cu fiecare tip de date, în
aşa fel încât realizarea si dezvoltarea programelor să devina avantajoasă atât pentru programator
cât şi pentru utilizator. Există două modalitati distincte de a analiza structurile de date: abordarea
logică, filozofia de realizare, formalizare si de transformare si construirea efectiva a structurilor
utilizând resursa memorie calculator împreuna cu algoritmii de încărcare si de adresare.

Dezvoltările teoretice au menirea de a oferi modele pentru fiecare structură de date si pentru a
permite considerarea unora mai simple dintre ele drept cazuri particulare ale altor structuri.
Generalizările conduc la includerea însăşi a programului în categoria structurilor de date.

4
Capitolul 1 – Concepţia structurii de grafuri

1.1. Noţiuni generale

În general, pentru situaţiile care necesită la rezolvare un oarecare efort mintal, se caută, în

primul rând, o metodă de reprezentare a lor care să permită receptarea întregii probleme dintr-o

privire şi prin care să se evidenţieze cât mai clar toate aspectele acesteia.

În acest scop se folosesc imagini grafice gen diagrame, schiţe, grafice etc. O reprezentare dintre

cele mai utilizate este cea prin grafuri. Acestea sunt utilizate în special pentru vizualizarea

sistemelor şi situaţiilor complexe. În general, vom reprezenta componentele acestora prin puncte

în plan iar relaţiile (legăturile, dependenţele, influenţele etc.) dintre componente prin arce de

curbă cu extremităţile în punctele corespunzătoare. Între două puncte pot exista unul sau mai

multe segmente (în funcţie de câte relaţii dintre acestea, care ne interesează, există),iar

segmentelor li se pot asocia sau nu orientări (după cum se influenţează cele două componente

între ele), numere care să exprime intensitatea relaţiilor dintre componente etc.

Este evident, totuşi, că această metodă are limite, atât din punct de vedere uman (prea multe

puncte şi segmente vor face desenul atât de complicat încât se va pierde chiar scopul pentru care

a fost creat – claritatea şi simplitatea reprezentării, aceasta devenind neinteligibilă) cât şi din

punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).

Din acest motiv, alături de expunerea naiv-intuitivă a ceea ce este un graf, dată mai sus, se

impune atât o definiţie riguroasă cât şi alte modalităţi de reprezentare a acestora, adecvate în

general rezolvărilor matematice.

Grafurile sunt una dintre cele mai multilaterale structuri in [Link] rezolvarea unor

probleme folosirea grafurilor este indispensabila.

1.2. Noţiunea de graf

5
 1.2.1. Definiţia grafului neorientat şi orientat
Se numeşte graf neorientat o pereche ordonata de mulţimi,notată G=(V,E) care satisface
condiţia E  [V ] 2 ,unde V este o muţime finita şi nevidă de elemente numite noduri (sau
vârfuri), iar E este o mulţime de perechi (neordonate) de elemente distincte din V numite
muchii.O muchie având vârfurile i şi j (numite extremitaţile sale) este notată cu [i,j] sau [j,i].
Un exemplu de graf orientat este: reţeaua de străzi a unui oraş. Străzile sunt muchii în
graf, iar intersecţiile reprezintă vârfurile grafului. Întrucât mergând pe jos ne putem deplasa pe
orice stradă în ambele sensuri, vom spune că din punctul de vedere al pietonilor, „graful unui
oraş” este neorientat.
Cu totul altfel stau lucrurile în ceea ce priveşte conducătorii auto, pentru că în orice oraş există
străzi cu sens unic. Pentru un şofer străzile trebuie să primească în graf o anumită orientare.
Desigur că acele străzi pe care se poate circula în ambele sensuri vor primi orientare dublă. Am
ajuns astfel la noţiunea de graf orientat.
Un graf orientat este o pereche ordonată G=(V,E),unde V este o mulţime finită şi nevidă
de elemente numite noduri (sau vârfuri),iar E este o mulţime de perechi ordonate de elemente
distincte ale lui V,numite arce. Un arc având vârfurile i si j (numite extremitaţile sale) se notează
prin (i,j).Deci, deosebirea faţa de grafurile neorientate constă în faptul că fiecare arc (i,j) are un
sens de parcurgere şi anume de la extremitatea sa iniţială la extremitatea sa finală.
Pentru a evita ambiguitatea în notaţie,specificăm că V  E = 0.

1.2.2. Moduri de reprezentare ale unui graf

A. O primă modalitate de reprezentare este listarea efectivă a tuturor nodurilor şi a

arcelor sale.
B. Un graf poate fi reprezentat într-un plan sub forma unei figuri geometrice alcătuite
din cerculeţe (noduri) şi segmente de curbă (muchii) care au ca extremitaţi
nodurile arcului şi pe care sunt trecute câte o sageată orientată de la nodul iniţial
spre cel final.
C. Putem folosi o reprezentare geometrică în care nodurile sunt reprezentate de două
ori, în două şiruri paralele, de la fiecare nod din unul din şiruri plecând săgeţi spre

6
 nodurile cu care formează arce în care el este pe prima poziţie, de pe al doilea şir
(reprezentarea prin corespondenţă).

D. Putem reprezenta graful dând pentru fiecare nod mulţimea nodurilor cu care
formează arce în care el este pe prima poziţie.
E. De asemenea,printr-un graf se poate reprezenta o hartă rutieră. Sa presupunem că
nodurile unui graf reprezintă localităţile şi muchiile - drumuri între aceste
localităţ[Link] graf nu asigură reprezentarea geografică a unei hărţi,ci relaţiile sau
conexiunile ce există între localităţi (noduri) şi drumuri (muchii).
F. Un graf poate fi reprezentat printr-o matrice pătratică booleană, de dimensiune
egală cu numărul de noduri, în care o poziţie aij va fi 1 dacă există arcul (xi,xj) şi 0
în caz contrar, numită matricea adiacenţelor directe.
G. Un graf poate fi reprezentat printr-o matrice pătratică latină, de dimensiune egală
cu numărul de noduri, în care pe o poziţie a ij va fi xixj dacă există arcul (xi,xj) şi 0
în caz contrar.

Exemplu: Dacă în reprezentarea A avem graful G = (V,E), unde V = {x 1, x2, x3, x4, x5, x6}
şi E = {(x1,x1), (x1,x2), (x1,x4), (x1,x5), (x2,x3), (x2,x4), (x2,x6), (x3,x1), (x3,x2), (x4,x5), (x5,x2),
(x6,x4)}, atunci în celelalte reprezentări vom avea:

B C(reprezentarea prin corespondenţă)

7
D
x2  {x3, x4, x6}
x3  {x1, x2}
x4  {x5}
x5  {x2}
x6  {x4}

a) Harta rutieră b) Reprezentarea grafică a hărţii rutiere

F x1 x2 x3 x4 x5 x6 G x1 x2 x3 x4 x5 x6
x1 1 1 0 1 1 0 x1 x1x x1x 0 x1x x1x 0
x2 0 0 1 1 0 1 1 2 4 5

x3 1 1 0 0 0 0 x2 0 0 x2x x2x 0 x2x

3 4 6
x4 0 0 0 0 1 0 x3 x3x x3x 0 0 0 0
x5 0 1 0 0 0 0 1 2

x6 0 0 0 1 0 0 x4 0 0 0 0 x4x 0
5
Desenarea şi reprezentarea vârfurilor şi segmentelor de curbă în sine este mai puţin
relevantă/importanţa,ceea ce ne interesează este care dintre perechile de vârfuri formează o
muchie şi care nu.
Vârfurile unui graf se notează cu V(G) şi muchiile cu E(G). Dar pentru comoditate se
intrebuinţează şi notaţia simplificată : v  G şi e  G.

1.3. Noţiuni de bază în teoria grafurilor

1.3.1. Proprietăţi

8
 a) Vom spune că un graf este simplu dacă el nu are nici muchii multiple şi nici bucle.
b) Un graf cu un număr de V-vârfuri poate avea cel mult V(V-1)/2 muchii.
Demonstraţie: Să presupunem că avem un graf cu V numărul de noduri,atunci vom avea V2
perechi de noduri posibile,respectiv muchii:
11 21 31 41 ... V!
12 22 32 42 ... V2
13 23 33 43 ... V3
... ... ... ... ... ...
1V 2V 3V 4V ... VV

Dacă excludem mulţimile de perechi de vârfuri {11,22,33,...,VV} şi {12,21,13,31,...,(V-

1)V,V(V-1)} ce formează muchii bucle şi muchii multiple,obţinem un număr maxim de muchii
posibile într-un graf simplu: (V2 – V)/2 = V(V – 1)/2.

1.3.2. Ordinul unui graf

Numim ordinul unui graf,numărul de noduri al grafului,deci cardinalul mulţimii V(G),şi

notăm această valoare cu |G|.Numărul de muchii se notează cu ||G||.
Graful null este graful cu 0 muchii şi 0 vârfuri - G(0,0) şi se notează cu (0).
Vom spune că un nod v este incident cu o muchie e dacă v  e;atunci e este o muchie a
vârfului [Link]ă vârfuri incidente cu o muchie formează marginile muchiei.O muchie {x,y}de
obicei se notează xy (sau yx).Dacă x  X şi y  Y,atunci xy este o muchie X-Y.
Mulţimea tuturor muchiilor X-Y dintr-o mulţime E este notată E(X,Y);în locul lui E({x},Y) şi
E(X,{y}) noi scriem simplu E(x,Y) şi E(X,y).Mulţimea tuturor muchiilor E a vârfului v se
notează E(v).
Două vârfuri x şi y se numesc adiacente sau vecine,dacă există o muchie care le uneşte
(cu care amandouă vârfurile sunt incidente).
Vom nota N G (x)={y  V;xy  E} vecinătatea vârfului x din graful G.
Două muchii e  f sunt adiacente dacă au o extremitate comună.
Un graf pentru care oricare 2 vârfuri sunt adiacente,se numeşte graf [Link] graf complet cu
n numărul de vârfuri se notează K n ; un graf format din trei vârfuri adiacente- K 3 se numeşte
triunghi.O mulţime de vârfuri şi muchii se numesc independente dacă nu conţin perechi de
elemente adiacente.
Considerăm G  G | := (V  V | , E  E | ) şi G  G | := ( V  V | , E  E | ).

9
Dacă G  G | = 0, atunci G şi G | sunt grafuri disjuncte.
Dacă V |  V şi E |  E,atunci G | este un subgraf al lui G (şi G este supergraf al lui G | )şi
vom scrie G |  G.
Fie G |  G ,vom spune că G | este un subgraf al lui G,dacă acesta conţine o parte din
vârfurile lui G şi numai acele muchii care le conectează ( G | conţine muchiile xy  E cu x,y
 V | ),
V | induce G | în G şi vom scrie G | = G[ V | ].
Astfel,dacă U  V o mulţime de vârfuri,atunci G[U] induce un graf U ale carui muchii aparţin
grafului G cu extremităţile sale.
Dacă H este un subgraf a lui G,nu neapărat indus,vom uşura notaţia acestuia din G[V(H)] în
G[H]. În final, G |  G este un subgraf indus de G dacă V | = V .
Dacă U este o mulţime de vârfuri ale unui graf G,prin G - U vom înţelege G[V-U].Cu alte
cuvinte,G - U este obţinut din graful G prin stergerea vârfurilor U  V şi muchiilor pe care le
formează.Dacă mulţimea U conţine un singur element (U = {v}) vom scrie G-v în loc de G-{v}.
În locul lui G-V( G | ) vom scrie simplu G- G | .
Pentru o submulţime F din [V ]2 scriem G-F =(V,E - F) şi G+F = (V,E  F);
La fel,G-{e} şi G+{e} este abreviat cu G-e şi G+e.
Dacă G şi G | sunt disjuncte,vom nota prin G* G | un graf obţinut din G  G | prin
reuniunea tuturor vârfurilor din grafurile G şi G | .De exemplu, K 2 * K 3 = K 5 .

1.3.3. Gradul unui nod dintr-un graf

Numim gradul unui nod particular x (x  V(G)),numărul de arce care sunt conectate la
acel nod şi se notează cu rG (x) =| N G (x)| ,unde N G (x) numărul vărfurilor adiacente cu vărful
x.
De exemplu,dacă rG (x)=0, x este un vărf izolat şi dacă rG (y)=1,y este un vărf suspendat.
Vom nota cu  (G) = min {r(v)| v  V} gradul minim al lui G şi ∆(G) :=max {r(v)|v  V}
gradul maxim a lui G.
Vom spune că un graf G este trivial dacă acesta are gradul 0 sau 1.
Dacă toate vârfurile unui graf G au grade egale (r(x)=k),vom spune că G este k-regulat,sau
simplu - graf [Link] exemplu,dacă toate vârfurile unui graf au gradul 3 vom spune că avem
un graf regulat de gradul 3 sau un graf cubic.
Notăm prin r(G) gradul unui graf G,care este media aritmetică gradelor tuturor nodurilor
din G.

10
  r(G)*|V |=  r (v) . Evident vom avea:  (G) ≤ r(G) ≤
1
r(G) =  r (v )
| V | vV vV

∆(G).
Dacă adunăm gradele tuturor nodurilor din graful G,obţinem de două ori numarul de muchii:

 r (v)  2 | E (G ) | .Faptul
vV ( G )
că membrul drept al ecuaţiei va fi mereu par,implică aceeaşi

proprietate în membrul stâng,pentru ca egalitatea să fie satisfacută. Suma tuturor termenilor r(v)
impari trebuie să fie o sumă al unui număr par de termeni, pentru a fi pară. Astfel deducem că
orice graf are un număr par de noduri al căror grad este impar.
|E|
Pentru a evita dublarea numărului de muchii considerăm următorul raţionament: fie ε(G) 
|V |
1 1
,vom demonstra că r(G) şi ε(G) sunt valori apropiate. Avem |E| =  r (v) = 2 r(G)*|V| 
2 vV
1
ε(G)  *r(G).Deci,gradul lui G este r(G)= 2*ε(G).
2
Propoziţia [Link] graf G care conţine cel puţin o muchie,are un subgraf H astfel încât 
(H)>ε(H)  ε(G).Orice graf G are un subgraf G | a cărui grad mediu nu e mai mic decat gradul lui
G: r | (v)  r(v) şi al cărui grad minim este mai mare decat jumătate din gradul său.

1.3.4. Drumuri şi cicluri într-un graf

Se numeşte drum simplu o succesiune de muchii adiacente şi distincte care conectează

două vârfuri dintr-un graf (numite capetele drumului).
Vom nota un drum cu P=(V,E) unde V={ x0 , x1 ,..., xk } şi E ={ x 0 x1 , x1 x 2 ,..., x k 1 x k },cu xi
noduri distincte.
Vârfurile x0 şi xk se numesc capetele drumului,iar x1 , x2 ,..., xk 1 sunt vârfurile interne ale
lui P.
Numărul muchiilor într-un graf determina lungimea drumului şi un drum de lungimea k vom
nota cu P k .De exemplu dacă lungimea unui drum este 0 atunci graful conţine un singur vârf:

P 0 = K 1 .Vom spune că avem un drum de la x0 la xk şi vom scrie P= x0 , x1 ... xk .

Pentru 0 ≤ i ≤ j ≤ k vom folosi urmatoarele notatii pentru drumuri şi subdrumuri ale unui graf:
P xi = x0 x1 ... xi 1 xi = x0 ... xi
xi P = xi xi 1 ... xk = xi ... xk
xi P x j = xi xi 1 ... x j 1 x j = xi ... x j
P = x1 ... xk 1
P xi = x0 x1 ... xi 1
xi P = xi 1 ... xk
xi P x j = xi 1 ... x j 1

11
 Vom folosi aceste notaţii pentru reprezentarea şi concatenarea [Link] exemplu,dacă
avem trei drumuri Px,xQy şi yR distincte,concatenarea lor este tot un drum,astfel,vom scrie Px 
xQy  yR  PxQyR.
Fig.1

Fig.1

Fie A şi B doua mulţimi de noduri ale lui G,vom spune ca P = x0 x1 ... xk este un
drum A-B dacă V(P)  A = { x0 }si V(P)  B = { xk }.
Un drum în care fiecare nod apare o singură dată se numeşte drum elementar.
Un drum în care fiecare arc apare o singură dată se numeşte drum simplu.
Două sau mai multe drumuri se numesc independente dacă nu conţin noduri interioare comune.
De exemplu,două drumuri a-b sunt independente,dacă şi numai dacă conţin numai a şi b noduri
comune.
Se numeşte drum hamiltonian un drum elementar care trece prin toate nodurile grafului şi drum
eulerian un drum simplu care conţine toate arcele grafului.
Definiţia 1. Fie G=(V,E) un graf [Link] subgraf al lui G este definit ca fiind graful
G'=(V',E') unde V'  V şi E'(xi) = E(xi)  V' pentru orice xi  V',adică E' este formată din toate
arcele lui E care au drept extremitaţi nodurile din V'.

12
Un graf parţial al lui G este graful (V,E') în care E'  [Link] spus,un graf parţial al lui G ,este
chiar G,sau se obţine din G păstrând toate vârfurile şi suprimând nişte [Link] parţial se
mai numeşte şi subgraf de acoperire al lui G.
Fie G=(V,E) un graf şi V'  V o submulţime nevidă al lui [Link] subgraf al lui G
indus de V' şi îl notăm <V'> acel subgraf care are ca noduri mulţimea V' şi oricare două noduri
din V' sunt adiacente în <V'> dacă şi numai dacă sunt adiacente în G.

1.3.5. Conexiuni într-un graf

Spunem că un graf este conex dacă între oricare doua vârfuri ale acestuia exista cel puţin
un drum sau dacă oricare două vârfuri v1 şi v2 sunt unite printr-un lanţ.
De exemplu grafurile din figurile a) şi b) nu sunt conexe, în timp ce graful din figura c) este un
graf conex. Graful trivial este considerat conex.

a) Graf neorientat b) Graf orientat c)Graf complex şi conex

Fig.2

Complementul unui graf G este graful G (V, V 2 \E),care conţine o muchie între vârfurile x şi y
dacă şi numai dacă G nu conţine o astfel de muchie. Complementarul unui graf care nu este
conex, este un graf conex.
Un graf în care între oricare două noduri există cel puţin un drum se numeste graf tare conex şi
un graf în care între oricare două noduri există cel puţin un lanţ se numeste graf simplu conex.
Observaţie: Pentru grafuri neorientate noţiunile de tare conex şi simplu conex sunt echivalente,
graful numindu-se doar conex;

13
 Daca un graf nu este conex se pune problema determinării componentelor sale conexe.O
componentă conexa fiind subgraf conex maximal,adică un subgraf conex în care un vârf din
subgraf nu este unit cu unul din afară printr-o muchie din primul graf.O componentă fiind
conexă,este întotdeauna nenulă.Respectiv,grafuri nule nu au componente conexe.
Se numeşte componentă tare conexă a unui graf G = (V,U) un subgraf al lui G care este
tare conex şi nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, între oricare
două noduri din componentă există cel puţin un drum şi nu mai există nici un nod în afara
componentei legat printr-un drum de un nod al componentei).
Determinarea componentelor conexe se poate realiza pentru ca relaţia "u este conectat cu
v" unde u,v  V,este o relaţie de echivalentă.Ea va determina partiţionarea lui V în clase de
echivalenţa V1 ,..., Vk ,iar gafurile induse < Vi > i= 1, n sunt [Link] vor fi componentele
conexe ale lui G.
Fig7
În cazul unui ciclu hamiltonian putem considera că vârfurile şi muchiile din ciclul
hamiltonian formează un subgraf de acoperire al grafului iniţ[Link] care conţine un ciclu
hamiltonian poartă numele de graf hamiltonian.
Dacă A,B  V şi X  V  E astfel încât fiecare A-B drum din G conţine un vârf sau o
muchie din [Link] spune că X separă mulţimile A şi B din [Link] implică în particular ca A
 B  X. Vom spune că X separă G şi vom numi X o mulţime de separare în G,dacă X separă
două vârfuri din G-X în [Link] vârf ce separă alte două vârfuri ale aceleiaşi componente,se
numeşte vârf de separare (cutvertex),şi o muchie ce separă prin extremitaţile sale se numeşte
punte (bridge).Astfel punţile unui graf sunt acele muchii care nu aparţin unui ciclu din graf.

Fig.3 Un graf cu v,x,y,w vârfuri de separare şi e=xy o punte

Vom spune că G este k-conex (pentru k  N) dacă |G| > k şi G-X este conex pentru fiecare
mulţime X  V cu |X|<[Link] alte cuvinte,Nu există două noduri ale lui G să fie separate de mai

14
puţin de k alte [Link] graf nenul este cel puţin 0-conex,şi 1-conex este graful conex non-
[Link] k  N cel mai mare număr întreg şi fie G un k-conex graf,vom spune că k(G) este
conexiunea lui G. k(G) = 0 dacă şi numai dacă G nu este conex sau un K 1 (graful cu un singur
vârf).Astfel vom avea k( K n )=n-1 pentru oricare n  1.
Dacă |G| > 1 şi G - F este conex pentru oricare F  E de cel puţin l muchii,atunci vom
spune că G este l-muchii-conex (l-edge-connected).Fie l cel mai mare număr întreg,dacă G este l-
muchii-conex vom spune că λ(G) este conexiune de muchii a lui g (edge-connectivity).În
particular,vom avea λ(G) = 0 dacă G nu este conex.
Pentru orice non-trivial graf G vom avea k(G) ≤ λ(G) ≤ δ(G).Astfel pentru conexiuni cât
mai mari avem grade cât mai [Link],în general,nu este adevă[Link] grad cât mai mic nu
implică să avem conexiuni cât mai mari.
Teorema 1. Orice graf cu gradul de cel puţin 4k va conţine un k-subgraf conex.
Demostraţie:
Pentru k  {0,1}demonstraţia este absurdă,de aceea vom considera k  [Link] G = (V,E)
un graf cu |V|=n şi |E|=m numărul de noduri şi muchii din [Link] inducţie vom demonstra cu
usurinţă afirmaţia teoremei.
Graful G are un k-subgraf conex dacă
(i) n  2k -1 si
(ii) m  (2k - 3)(n - k + 1) +1.
Din ipoteza ştim că r(G)  4k unde r(G) este gradul lui G.
Astfel,vom avea n >∆(G)  r(G)  4k  n  2k-1 (i)
1 1 
m = n(n - 1)  m = r(G)n si
 m  2kn  m  (2k-3)(n-
2 2 

Stim că r(G)  4k 
1
r(G)n  2kn.


2 


k+1)+1 (ii)
1 1
Vom folosi inducţia după [Link]ă n = 2k-1,atunci k = (n+1), şi de aici avem m  n(n-1)
2 2

din relaţia (ii). Astfel G = K n  K k 1 şi n  2k .Daca v este un nod cu r(v)  2k-3, putem aplica
ipoteza inductivă pentru [Link] avea δ(G)  [Link]ă G este k-conex,nu avem ce demonstra .
Considerăm că G are urmatoarea formă: G = G1  G2 cu | G1  G2 | < k şi | G1 |,| G2 | < [Link]
încât fiecare muchie aparţine grafului G1 sau G2 ,adică G nu conţine muchii între G1  G2 şi
G2  G1 .Cât timp oricare nod din aceste subgrafuri are cel puţin δ(G)  2k-2 noduri vecine,vom

avea | G1 |,| G2 | ≥ 2k-1. Dar cel puţin unul din subgrafuri trebuie să satisfacă ipoteza inductivă de
mai [Link]ă nici un subgraf nu satisface această ipoteză,vom avea

15
 || Gi || ≤ (2k -3)(| Gi |- k+1)
pentru i = 1,2 avem
m  || G1 || + || G2 ||
 (2k-3)(| G1 | - k + 1) + (2k-3)(| G2 | - k +1)
 (2k-3)(| G1 | + | G2 | - 2k +2)
 (2k-3)(n - k + 1) (dar | G1  G2 | ≤ k-1)
contradicţie cu (ii).

Capitolul 2-Concepţia structurii de arbore

2.1. Noţiuni generale

2.1.1. Noţiunea de arbore, proprietăţi

Arborii sunt una dintre cele mai importante structuri neliniare care apar în algoritmii
pentru calculatoare. Structura arborescentă implică o relaţie de ramificare între noduri, foarte
asemănătoare celei întâlnite la crengile unui arbore din natură.
Există mai multe moduri echivalente de definire a [Link] punct de vedere al teoriei
grafurilor numim arbore un graf neorientat conex şi fara cicluri. Dacă graful este aciclic, dar nu
este conex îl vom numi pădure. Astfel o pădure este un graf ale cărui componente sunt arbori.

a)Arbore b)Padure(nu e conex)

Fig.1

Proprietăţi ale arborilor :

- Există un nod în care nu intră nici un arc, numit rădăcina arborelui

16
 - Cu excepţia rădăcinii,fiecare nod are proprietatea că în el intră un singur arc. Acesta
leagă nodul respectiv de un alt nod numit predecesor sau părinte.
- Dintr-un nod pot ieşi unul sau mai multe arce. Fiecare astfel de arc, leagă nodul
respectiv de un alt nod numit sucessor sau fiu al nodului.
- Nodurile sunt organizate pe nivele, primul nivel fiind ocupat de nodul rădăcină.
Nodurile de pe ultimul nivel se caracterizează prin faptul că din ele nu mai iese nici un
arc, şi se numesc noduri terminale sau frunze şi acestea vor avea întotdeauna gradul
nodului rA (x) = 1.
- Nodurile pot conţine o aşa numită informaţie utilă, care poate fi de orice [Link]ă
informaţie,numită cheie (value key) este folosită pentru căutarea elementelor de date
sau alte operaţii. Grafic cheia unui nod este afişată în interiorul nodului sau lângă
acesta.
Oricare arbore non-trivial are cel puţin două noduri terminale, de exemplu capetele celui mai
mare [Link]ă vom şterge o frunză dintr-un arbore,vom obţine tot un arbore.

Studiul arborilor este justificat de existenţa în practică a unui număr mare de probleme
care pot fi modelate prin arbori. Dintre acestea amintim:

1. construirea unor reţele de aprovizionare cu apă potabilă (sau cu energie electrică sau
termică etc) a unor puncte de consum, de la un punct central;
2. construirea unor căi de acces între mai multe puncte izolate;
3. desfăşurarea unui joc strategic;
4. luarea deciziilor în mai multe etape (arbori decizionali);
5. evoluţii posibile ale unui sistem pornind de la o stare iniţială;
6. construirea unei reţele telefonice radiale, a unei reţele de relee electrice;
7. legarea într-o reţea a unui număr mare de calculatoare;
8. organigramele întreprinderilor;
9. studiul circuitelor electrice în electrotehnică (grafe de fluenţă etc);
10. schemele bloc ale programelor pentru calculatoare etc.

În toate problemele de mai sus se doreşte ca, dintre muchiile unui graf neorientat, să se
extragă arborele optim din mulţimea tuturor arborilor care pot fi extraşi din graful dat.

17
 Deoarece definiţia arborelui este dificil de aplicat pentru deciderea faptului că un graf este
arbore sau nu (şi în special sunt greu de verificat conexitatea şi mai ales existenţa ciclurilor)
există mai multe caracterizări posibile ale unui arbore, acestea fiind date de teorema de mai jos:

Teorema 1
Fie H = (V,E) un graf [Link]ătoarele afirmaţii sunt echivalente:
1. H este un arbore;
2. Oricare două vârfuri din H sunt unite printr-un lanţ simplu unic.
3. H este conex minimal,adică dacă i se suprimă o muchie se creează două componete
conexe şi H-e va fi neconex pentru oricare e  E.
4. H este conex şi are |V| - 1 muchii.
5. H este aciclic şi are |V| - 1 muchii.
6. H este aciclic maximal,adică dacă adaugăm o muchie,graful obţinut va conţine cicluri
(H+xy este ciclic pentru oricare două vârfuri nediacente x,y  V).
Demonstraţie:
12
Dacă H este arbore, atunci H este conex, deci oricare ar fi două vârfuri din graf, acestea
sunt unite prin cel puţin un lanţ simplu şi vom nota acest lanţ cu xHy. Presupunem prin reducere
la absurd că există x şi y două vârfuri unite prin două lanţuri simple distincte l1 şi l2 .

18
 Fig.2.

Fie z primul vârf de la care cele două lanţuri se despart, iar t primul vârf în care cele două
lanţuri se întâlnesc din nou. Dacă notăm l'1 porţiunea de pe lanţul l1 între z şi t, iar cu l'2 porţiunea
de pe lanţul l2 între z şi t, atunci l' 1 şi l'2 nu au vârfuri comune, cu excepţia vârfurilor z şi t.
Concatenând l'1 şi l'2, obţinem un ciclu- contradicţie cu ipoteza că H este arbore. Deci, oricare
două vârfuri din graf sunt unite printr-un lanţ simplu unic.
23
Dacă oricare două vârfuri x, yV sunt unite printr-un lanţ simplu unic, atunci orice
muchie x, yE reprezintă unicul lanţ dintre x şi y. Suprimând muchia x, y, între x şi y nu va
mai exista lanţ, deci graful obţinut nu va mai fi conex.
34
Notăm cu n numărul de vârfuri şi cu m numărul de muchii din graf.
Pentru a demonstra că orice graf conex minimal are n-1 muchii vom demonstra prin
inducţie completă după n că m  n-1. Cum în orice graf conex m  n-1, deducem m  n-1.
P(1) Dacă n  1, atunci m  0  m  n-1.
P(2) Dacă n  2, atunci m 1  m  n-1.
P(n) Presupunem că într-un graf conex minimal cu cel mult n vârfuri numărul de
muchii este strict mai mic decât numărul de vârfuri.
P(n1) Demonstrăm că într-un graf conex minimal cu n1 vârfuri, numărul de muchii
este cel mult egal cu n.
Fie H conex minimal cu n1 vârfuri şi m muchii. Eliminând o muchie oarecare din graf
obţinem un graf H' cu m-1 muchii şi două componente conexe H 1 şi H2 cu n1, respectiv n2 vârfuri
(n1n2  n1) şi m1, respectiv m2 muchii (m1m2  m-1). Subgrafurile H1 şi H2 sunt conexe
minimale, altfel graful H nu ar fi conex minimal. Din ipoteza inductivă rezultă că m1  n1-1, m2 
n2-1; dar m1m2  m-1  n1n2  n-2  m  n-1. Deci H conex minimal implică H conex cu n-1
muchii.

45
Fie H un graf conex cu n-1 muchii. Să demonstrăm că H este aciclic.
Presupunem prin reducere la absurd, că graful H conţine un ciclu C format din vârfurile
v1, v2, ..., vk.

19
 Să considerăm subgraful parţial Hk  (Vk, Ek) constând din ciclul C. Deci Vk  v1, v2 ,...,
vk, iar Ek  v1,v2, v2,v3,...,vk-1,vk, [vk,v1 (VkEk k). Dacă Vk<V, atunci
viVk şi vk1V-Vk astfel încât vi, vk1E, graful E fiind conex.
Construim Hk1  (Vk1, Ek1) astfel :Vk1  Vk vk1; Ek1Ekvi,vk1 şi
Ek1Vk1k1.
Cât timp k1 < n, aplicăm acelaşi procedeu până când obţinem un graf Hn  (V, En), cu
En n, En  E; deci E  n, contradicţie cu ipoteza E n-1.
56
Presupunem că graful H este aciclic cu n-1 muchii, să demonstrăm că H este aciclic
maximal.
Fie C1, C2,..., Cp cele p componentele conexe ale grafului H, având respectiv n1, n2,..., np
vârfuri şi m1, m2,..., mp muchii fiecare. Evident că n1n2...np  n şi m1m2...mp  n-1.
Cum graful H este aciclic, deducem că fiecare componentă conexă este un arbore. Deoarece am
demonstrat că 1  5, rezultă că m i ni-1, i1, 2, ..., p. Înlocuind în relaţia de mai sus,
obţinem n-p  n-1  p  1, deci H conex. Dacă H este conex şi aciclic, conform definiţiei H
este arbore. Dar am demonstrat că 1  2, deci oricare două vârfuri din H sunt unite printr-un lanţ
simplu. Astfel, adăugând orice muchie obţinem un ciclu.
61
Presupunem că graful H este aciclic, dar dacă am mai adăuga o muchie s-ar obţine un
ciclu. Să demonstrăm că H este conex.
Fie u şi v două vârfuri neadiacente din graf, arbitrar alese. Deoarece adăugând muchia u,
v se obţine un ciclu, rezultă că u şi v sunt unite printr-un lanţ ale cărui muchii aparţin grafului H.
Cum u,v au fost alese arbitrar, deducem că graful H este conex.
Q.E.D.
Corolar1:Vârfurile unui arbore pot fi oricând enumerate cu v1, v2,...,vn astfel incât oricare vi cu i
≥ 2 va avea un singur vecin in multimea { v1,...,vi-1 }.
Corolar2:Daca H este un arbore si G este un graf oarecare cu gradul minim δ(G) ≥ |H| -[Link]
H  G si G va conţine un subgraf isomorfic cu H.
Demonstratie:Putem gasi in graful G o copie a arborelui H dupa principiul de numerotare
inductivă a vârfurilor acestuia demonstrat in Colorar1.
Fie G = (V,E) un graf [Link] graf parţial H al lui G,cu proprietatea ca H este
arbore,se numeste arbore parţial al lui G.

20
 Un graf neorientat G conţine un arbore parţial dacă şi numai dacă G este conex.

2.1.2. Arbori cu rădăcină

Pentru problemele în care se impune o ierarhizare a informaţiilor ce corespund vârfurilor

arborelui, astfel încât anumite vârfuri să fie subordonate altora, este utilă introducerea unei noi
noţiuni- arbore cu rădăcină. Arborii cu rădăcină sunt o prezenţă cotidiană. Fiecare şi-a reconstituit
la un moment dat arborele genealogic şi, după cum vom vedea, cea mai mare parte a termenilor
folosiţi în limbajul informatic derivă de aici. Un alt exemplu este modul de organizare a
competiţiilor sportive sau organigrama unei întreprinderi.
De regula,intr-un arbore un vârf este considerat radacina [Link] spune ca avem un
arbore cu radacina (rooted tree),daca radacina acestuia este fixa.
Definiţie:
Un arbore cu rădăcină este o mulţime finită de noduri care fie este vidă fie
- există un nod special numit rădăcina arborelui;
- toate celelalte noduri sunt partiţionate în n  0 clase A1, A2, ..., An, fiecare clasă fiind un
arbore cu rădăcină. Rădăcina arborelui este unită prin muchii de rădăcinile arborilor A 1, A2, ...,
An.
Definiţia este recursivă, orice nod al unui arbore fiind rădăcina unui subarbore.

Fig.3

21
 Să observăm că alegând într-un mod arbitrar un vârf drept rădăcină, orice graf neorientat
conex şi fără cicluri este un arbore cu rădăcină în sensul definiţiei de mai sus. Arborii A 1, A2, ...,
An se numesc subarborii rădăcinii, numărul de subarbori nevizi ai unui nod fiind numit gradul
nodului respectiv.
De exemplu:

Fig.4
Să observăm că definiţia conduce la o ierarhizare a nodurilor arborelui,acest lucru are
urmatoare consecinţe:
 Putem aseza arborele pe nivele astfel:
 Se plasează radacina r pe nivelul 1;
 Dacă notam cu r1, r2, ..., rn respectiv rădăcinile arborilor A1, A2, ..., An, nodurile r1,
r2, ..., rn vor constitui nivelul 2 în arbore, ş.a.m.d. Se plaseaza pe fiecare nivel i ≥ 2
vârfurile pentru care lungimea lanţurilor care le leaga de radacina este i-1;
 Se trasează muchiile grafului.
 Arborele devine graf orientat,stabilindu-se pentru fiecare muchie un sens de parcurgere şi
anume de la nivelul superior (cu număr de ordine mai mic) la nivelul imediat inferior(cu
numărul de ordine mai mic cu o unitate)....(cap9)
Nodurile r1, r2, ..., rn, se numesc fiii nodului rădăcină, iar rădăcina r reprezintă părintele nodurilor
r1, r2, ..., rn, rădăcina fiind singurul nod din arbore care nu are părinte. Fiecărei muchii din arbore

22
îi putem asocia o orientare de la părinte spre fiu. În plus, fiii nodurilor de pe nivelul i0, vor
constitui nivelul i1.
Nivelul maxim din arbore va constitui înălţimea (adâncimea) arborelui respectiv. Să
observăm că orice nod x poate fi atins din rădăcină pe un drum unic. Orice nod y care se găseşte
pe drumul unic de la r la x se numeşte ascendent (strămoş) al lui x. Dacă y este un ascendent al
lui x, atunci x se numeşte descendent al lui y. Mai exact, toţi descendenţii unui nod x sunt
nodurile din subarborele cu rădăcină x. Dacă un nod nu are descendenţi el se numeşte nod
terminal sau frunză. Două noduri care au acelaşi părinte se numesc fraţi.
În exemplul din fig.4, 2 este un ascendent al lui 6. Nodurile 5, 6, 7, 9, 10 sunt noduri
terminale. Nodurile 9,10 sunt fraţi, iar descendenţii nodului 4 sunt nodurile 8, 9,10.
Daca notam cu r radacina unui arbore H,celelalte varfuri V(H) le vom nota intr-o anumita
ordine astfel incat x ≤ y daca x  rTy şi vom spune ca avem un arbore-ordonat (tree-order) cu
multimea de vârfuri V(H) si radacina r (ultimul element).Extremitaţile oricarei muchii din H pot
fi [Link] pentru care oricare element x are proprietatea {x | x ≤ y}(unde y este
vârf fix oarecare)se numeste un lant (chain),o multime de perechi de elemente comparabile.

Teorema 2. Numerele întregi 0 < r1  r2  ... rn (n  2) sunt gradele vârfurilor unui arbore dacă şi
numai dacă r1r2...rn  2n-2.
Demonstraţie:
Necesitatea Condiţia este necesară, deoarece orice arbore cu n vârfuri are n-1 muchii, iar suma
gradelor vârfurilor oricărui graf este de două ori numărul de muchii. Deci r1r2...rn  2n-2.
Suficienţa Fie 0 < r1  r2 ... rn astfel încât r1r2...rn  2n-2.
Să demonstrăm că există un arbore cu gradele vârfurilor r1, r2,..., rn. Vom proceda prin inducţie.
P(n) Presupunem acum că proprietatea este adevărată pentru orice secvenţă de n numere
naturale 0 < r1  r2  ... rn, astfel încât r1r2...rn  2n-2.
P(n1) Să demonstrăm că pentru orice secvenţă 0 < r' 1  r'2 ... r'n  r'n1 astfel încât r'1r'2...r'n1
 2n, există un arbore cu n1 vârfuri cu secvenţa gradelor r'1, r'2, ..., r'n1.
Observăm că există măcar un nod terminal x1 cu gradul r'11, altfel dacă ri  2,i1,
2,..., n1  r'1r'2...r'n1  2(n1), ceea ce contrazice ipoteza. În mod analog, observăm că
există măcar un nod neterminal xn1, cu gradul r'n1 > 1, altfel dacă r'i  1,i1, 2, ..., n1 
r'1r'2...r'n1  n1 < 2n .

23
 Să considerăm următoarea secvenţă de n numere întregi r'2,..., r'n, r'n1-1 cu proprietatea că
r'2...r'nr'n1  2n-2. Din ipoteza inductivă există un arbore An cu n vârfuri şi secvenţa gradelor
r'2,..., r'n, r'n1-1. Adăugăm la arborele An un vârf pe care îl unim printr-o muchie cu vârful având
gradul r'n1-1. Obţinem un arbore An1 cu gradele vârfurilor r'1, r'2,..., r'n1.

2.2. Arbori binari

2.2.1. Definiţie

Exista mai multe tipuri de [Link] intr-un arbore un nod are mai mult de doi fii vom
spune ca avem un arbore multidrum (multiway tree).Un exemplu de acest tip de arbore putem
vedea in fig.1. Dar,daca fiecare nod al unui arbore va avea cel mult doi descendenţi(succesori),cu
excepţia frunzelor,vom spune ca avem un arbore [Link] binar constituie o clasă foarte
importantă de arbori cu rădăcină.

Fig.5

Observaţii :

24
1. Orientarea de la arborii cu rădacină (generată de plasarea vârfurilor pe niveluri) se menţine si
in cazul arborilor binari.
2. Reprezentarea pe niveluri determină sa nu mai fie necesar sensul arcelor.
3. Fiecare vârf poate fi considerat radacina pentru un [Link],pentru fiecare vârf vom
avea subarborele stâng si subarborele drept,eventual unul din ei sau amândoi putând fi arbori
vizi (fară nici un varf).

2.2.2. Proprietaţile unui arbore binar

Proprietatea 1.
Numărul maxim de noduri de pe nivelul i al unui arbore binar este 2i.
Demonstraţie:
Vom proceda prin inducţie după numărul nivelului.
P(0) Pe nivelul i  0 se găseşte un singur nod (radăcina).
P(k) Presupunem că numărul maxim de noduri de pe nivelul k este
2k.
P(k1) Vom demonstra că pe nivelul k1 sunt cel mult 2k1 noduri.
Pe nivelul k1 se găsesc fiii nodurilor de pe nivelul k. Din ipoteza inductivă, pe nivelul k se
găsesc cel mult 2k noduri, iar fiecare nod poate avea cel mult doi fii, deci pe nivelul k1 se găsesc
cel mult 2*2k  2k1 noduri.
Q.E.D.
Proprietatea 2.
Numărul maxim de noduri într-un arbore cu înălţimea h este 2h1-1.
Demonstraţie:
Numărul maxim de noduri într-un arbore cu înălţimea h se obţine atunci când fiecare
nivel i este plin, deci, conform propoziţiei anterioare, conţine 2 i noduri. Numărul maxim de
noduri într-un arbore cu înălţimea h va fi:
h
i h1
2  2 1
i0
Q.E.D.
Proprietatea 3.
În orice arbore binar nevid cu n0 noduri terminale există n0-1 noduri de grad 2.
Demonstraţie:

25
 Notăm cu n0 numărul de noduri terminale, cu n1 numărul de noduri de grad 1 si cu n2
numărul de noduri de grad 2. Deci, numărul total de noduri nn0n1n2.
Dacă numărăm muchiile dintr-un arbore binar, observăm că fiecare nod, cu excepţia
rădăcinii, are o singură muchie orientată spre el. Notând m numărul de muchii obţinem n  m1.
Dar orice muchie provine de la un nod de grad 1 sau 2, rezultă că m  n12n2.
n0  n1  n2  n n  n1  n2  n0
Din 
n1  2 n2  n  1
 
n  n1  2 n2  1
 n2 + n0 = 2n2 + 1  n2  n0-1.
Q.E.D.
Proprietatea 4.
Un arbore cu n vârfuri are înălţimea cel puţin egală cu log2n.
Demonstraţie:
În cazul cel mai favorabil, nodurile sunt dispuse pe niveluri astfel încât fiecare nivel să fie
plin, cu excepţia, eventuală, a ultimului nivel. Deci arborele binar cu n noduri de înălţime minimă
este arborele binar complet cu n vârfuri, care, din modul de construcţie, are înălţimea log2n.
Q.E.D.
Proprietatea 5.
Definim lungimea drumurilor interne (I) ca fiind suma lungimilor drumurilor de la rădăcină la
noduri neterminale (interne) şi lungimea drumurilor externe (E) ca fiind suma lungimilor
drumurilor de la rădăcină la noduri terminale (frunză sau externe). Într-un arbore binar cu n
noduri interne, E  I2n.
Demonstraţie:
Vom proceda prin inducţie după n, numărul nodurilor interne.
P(0) Într-un arbore cu 0 noduri interne (vid sau format numai din rădăcină) E  I  0.
P(n-1) Presupunem că într-un arbore binar An-1, cu n-1 noduri interne, are loc relaţia En-1  In-
12(n-1).
P(n). Vom demonstra că într-un arbore binar An, cu n noduri interne, are loc relaţia En  In2n.
Fie An un arbore binar cu n noduri interne. Există în An un nod intern x care are drept fii
două noduri terminale. Îndepărtând din An fiii nodului x, nodul x se transformă în nod terminal,
deci obţinem un arbore An-1 cu n-1 noduri interne. Din propoziţia inductivă rezultă că în arborele
A n-1, En-1  In-12(n-1). Dacă notăm cu d, lungimea drumului de la rădăcină la nodurile eliminate,
obţinem relaţiile :
En  En-12d-(d-1) (în An nodurile eliminate sunt terminale, dar nodul x nu, lungimea drumului de
la rădăcină la x fiind d-1).

26
 In  In-1(d-1) (în An nodul x este intern).
Deci En  In-12(n-1)d1  In-d12n-2d1  In2n.
Q.E.D.

Capitolul 3-Algoritmul si reprezentarea unui graf in limbajul java

3.1. Probleme de drumuri minime intr-un graf

3.1.1. Întroducere
Definiţia 1 :Se numeste graf ponderat sau valuat şi se notează G=(V,E,l) un graf (V,E) căruia i
se asociază o funcţie l:E → R+ numită ponderea arcelor.
Exemple:
a) l(x,y) = lungimea tronsonului de drum,(x,y) care uneste localitatile x si y;
b) l(x,y) = capacitatea tronsonului de drum (x,y).
Definiţia 2: Se numeste reţea de transport un graf orientat,G=(V,E), fără bucle, cu următoarele
proprietăţi:
 exista un nod x0 unic,numit originea reţelei,si care nu are ascendenti;
 exista un nod xf unic,numit destinaţia reţelei,si care nu are descendenti;
 fiecărui arc eE ii este asociat un număr l(u) ≥ 0 numit capacitatea arcului e.

Fie G = (X,U,l) un graf conex (ipoteza necesară pentru a asigura existenţa cel puţin a unui
arbore) ponderat [Link] pune problema găsirii arborelui de acoperire de lungime
minima,adica,folosind arce ale grafului să se lege intre ele toate nodurile astfel incat lungimea
totală a arcelor folosite (suma ponerilor) să fie minima.O astfel de problemă apare in proiectarea
reţelelor de comunicaţii,unde obiectivul este să se minimizeze lungimea cablului necesar
conectării tuturor nodurilor care trebuie să comunice intre ele,in proiectarea retelelor de
drumuri,benzi rulante,sisteme de canalizare etc.În continuare sunt prezentaţi doi algoritmi care
rezolva aceasta problema.

3.1.1 Algoritmul lui Dijkstra

Se pune problema determinării unui plan de transport printr-o reţea rutieră (de transport)
astfel incât cheltuielile de transport sau duratele de transport să fie [Link] necesar să se
determine drumul cel mai "scurt" dintre două noduri oarecare ale reţelei [Link] tip de

27
problemă se intalneşte si in proiectarea reţelelor de calculatoare,in stabilirea treaseelor
mijloacelor de transport in comun etc.(Henry-Labordere,1995)
Algoritmul lui Dijkstra permite calcularea lungimilor celor mai scurte drumuri de la un
vârf s la toate vârfurile x ale unui graf conex G = (X,U,l),dacă lungimile tuturor arcelor sunt
nenegative.
Fie (x) lungimea celui mai scurt drum de la s la [Link] S multimea vârfurilor pentru care
def
se calculează .Atunci, (x)  {lungimea celui mai scurt drum de la s la x,care are toate

vârfurile in S cu excepţia lui x }.Se notează cu   (x) = {mulţimea arcelor care pornesc din
nodul x},iar cu   (x) = {mulţimea arcelor care intra in nodul x}.Dacă graful este neorientat

  (x) =   (x) = (x) = mulţimea arcelor incidente in nodul x.

AlgoritmulDijkstra
Pas 1. {Iniţializări}
S := {s}; s nodul de start, (s) :=0;
Pentru orice x  X  S dacă x  (s) atunci (x) := l(s,x) altfel
(x) := + ;
Pas 2. {Iteraţia curentă}
Repetă
Determină y  X  S astfel încât (y) = min
zS (z);

Dacă (y) <  atunci S := S  {y};

Pentru z    (y) (z) := min {(z), (y)+ l(z,y)};
pâna când S = X sau (y) = .
Pas 3. Stop.
Se observă că valorile (z) rămân nemodificate pentru z  S,lucru ce poate fi exploatat în
transpunerea pe calculator a algoritmului.

[Link] Figura 1 sunt date 7 localitaţi numerotate de la 1 la 7 şi timpul (în ore) necesar
parcurgerii distanţei pe arterele care le leaga.Să se determine ruta pe care se realizează timpul
minim între localitaţile 1 şi 7.
[Link] aplică algoritmul Dijkstra grafului reprezentat de Figura 1.

28
 Fig.1
Pas 1. s=1, S = {1}, (1) = {2,4},

y 1 2 3 4 5 6 7
(y) 0 1  4   

Pas 2.

Iteraţia I. {(y)} = zmin

X  S {(z)}= min{(2), (3), (4), (5), (6), (7)}= (2),

y = 2, S = {1,2}, (2) = {1,3,4}.

(2) = l([1,2]) = 1

(3) = min{(3), (2) + l([2,3])} = min{ ,1+4} = 5

(4) = min{(4), (2) + l([2,4])} = min{ 4,1+2} = 3

y 1 2 3 4 5 6 7
(y) 0 1 5 3   
Iteraţia a II-a.

{(y)} = zmin
X  S {(z)}= min{(3), (4), (5), (6), (7)}= (4), y = 4, S = {1,2,4},

(4) = {1,2,3,5,6}.

(3) = min{(3), (4) + l([3,4])} = min{ 5,3+5} = 5

(5) = min{(5), (4) + l([4,5])} = min{,3+2} = 5

(6) = min{(6), (4) + l([4,6])} = min{,3+9} = 12

y 1 2 3 4 5 6 7
(y) 0 1 5 3 5 12 
Iteraţia a III-a.

29
{(y)} = zmin
X  S {(z)}= min{(3), (5), (6), (7)}= (3), y = 3, S = {1,2,3,4},

(3) = {2,4,5,6}.

(5) = min{(5), (3) + l([3,5])} = min{5,5+2} = 5

(6) = min{(6), (3) + l([3,6])} = min{12,5+3} = 8

y 1 2 3 4 5 6 7
(y) 0 1 5 3 5 8 
Iteraţia a IV-a.

{(y)} = zmin
X  S {(z)}= min{(5), (6), (7)}= (5), y = 5, S = {1,2,3,4,5},

(5) = {3,4,6,7}.

(6) = min{(6), (5) + l([5,6])} = min{8,5+6} = 8

(7) = min{(7), (5) + l([5,7])} = min{,5+7} = 12

y 1 2 3 4 5 6 7
(y) 0 1 5 3 5 8 12
Iteraţia a V-a.

{(y)} = zmin
X  S {(z)}= min{(6), (7)}= (6), y = 6, S = {1,2,3,4,5,6},

(6) = {3,4,5,7}.

(7) = min{(7), (6) + l([6,7])} = min{12,8+1} = 9

y 1 2 3 4 5 6 7
(y) 0 1 5 3 5 8 9
Iteraţia a VI-a.

{(y)} = zmin
X  S {(z)}= min{(7)}= (7), y = 7, S = {1,2,3,4,5,6,7},

Pentru nodurile din mulţimea S  (y) nu s-au mai evaluat (y).

Algoritmul se opreşte deoarece S=X. Vectorul (y) conţine cele mai mici distanţe de la
nodul 1 la celelalte [Link] cel mai scurt între nodurile 1 si 7 se obţine din muchiile
(marcate cu litrere îngroşate ) D = {[1,2],[2,3],[3,6],[6,7]} şi este de 9 ore.
În Management Scientist modulul Shortest Route determina cel mai scurt drum dintre
doua noduri ale reţelei şi precizează muchiile care realizează acest drum.

3.2 Structuri de date utilizate în reprezentarea grafurilor

30
 Graful are o organizare variabilă.Spre deosebire de un arbore binar,
in care fiecare vârf are cel mult doi fii, vârful unui graf poate fi adiacent cu
un numar arbitrar de alte vârfuri.
Exemplu: In Figura 2 avem un graf conex in care vârful A este
adiacent cu alte trei vârfuri,in timp ce vârful C este adiacent
numai cu un singur vârf .
Exista două metode uzuale de reprezentare a grafurilor: matricea
de adiacentă si lista de adiacentă.
Fig.2
3.2.1. Matricea de adiacentă

O matrice de adiacentă este un tablou bidimensional in care fiecare element indică dacaă există o
muchie între două noduri sau [Link] un graf are N numărul de noduri, matricea de adiacentă va
fi un tablou cu N linii si N coloane.
Definiţie: Fie G=(V,E) un graf si n=|V|,m=|E|.Se numeste matricea de adiacenţă a grafului G,
matricea Ann =( aij ) cu n linii şi n coloane,ale carei elementele satisfac relatia:

1, daca ()arcul ( xi x j )  E , cu i j

aij  
0, altfel daca ( xi x j )  E

unde V={ x1 , x2 , , xn } si unde s-a ales o ordine pe mulţimea vărfurilor.

Observaţii:
[Link] putem folosi şi valori booleene true/false petru reprezentarea elementelor matricii.
2.În functie de ordinea aleasă pe multimea vârfurilor matricea de adiacenţă este unic determinată.
3 În cazul grafului neorientat matricea de adiacenţă este simetrică (in raport cu diagonala
principală.
4.În cazul grafului orientat,deoarece arcul ( xi x j ) nu este totuna cu arcul ( x j xi ),matricea
de adiacenţă nu mai este simetrica faţă de diagonala principală.
Exemplu: Mai jos avem matricea de adiacentă pentru graful neorientat din Figura 2. Observăm ca
0 1 1 1 A este adiacent cu toate cele trei vârfuri, B este adiacent cu A si D, C
 
1 0 0 1
A este adiacent numai cu A, si D este adiacent cu A si B. Conexiunea
1 0 0 0
 
1 1 0 0  varfului la el insusi este notată cu 0, astfel diagonala principală a

matricii are valoarea 0. Triungiul deasupra diagonalei principale este simetric cu cel de desuput.
Intr-un graf neorientat aceste triunghiuri conţin aceeasi informţtie.

31
 3.2.2. Liste de adiacenţa (vecinilor)

Este a doua metoda de reprezentare a grafurilor.O listă de adiacentă este un tablou de liste
(sau o listă de liste).Fiecare listă individuală arată care vârfuri sunt adiacente cu un varf dat.
Exemplu: In Tabelul 1 avem liste de adiacentă pentru graful din Figura 2.

Varful Lista cu varfuri adiacente

A B →C→D
B A→D
C A
D A→B
Tabelul 1. Liste de adiacentă
Simbolul → indică legătura intr-o lista . In fiecare listă varfurile sunt aranjate intr-o
ordine alfabetică.De regulă, acesta nu este obligatoriu.
Într-un graf orintat pentru fiecare nod x , cu x  {1,2,..., n} , se construiesc două liste ale
vecinilor săi :
- L+(x) – lista vecinilor succesori; conţine nodurile ce sunt extremităţi finale ale arcelor
care ies din nodul x
- L-(x) – lista vecinilor predecesori; conţine nodurile ce sunt extremităţi iniţiale ale
arcelor care intră în nodul x
Reprezentăm graful orientat din Figura 3 prin cele două metode:

nodul L ( x ) L ( x )
0 0 0 0
1 vida 2
 
1 0 1 1 2 1,3,4 4
A
0 0 0 1 3 4 2
 
2 0 1 0 0 
3  4 2 2,4

Matricea de adiaceţă Liste de adiacenţă

Mai tarziu vom explica in ce situaţii se intrebuinţeaza fiecare metodă de reprezentare a unui graf.
1
De regulă se foloseşte matricea 4de adiacentă ,dar in unele situaţii liste de adiacentă sunt mai
eficiente.
Fig. 3
3.3. Adăugarea vârfurilor şi a muchiilor intr-un graf

Pentru adăugarea unui vârf in graf vom crea cu new un obiect nou listaVarfuri in clasa
Vertex.În programe complexe un vârf poate conţine mai multe elemente de date,dar pentru

32
comodiate vom presupune că vârfurile grafului nostru conţine un singur tip de [Link], pentru
crearea unui vârf vom folosi urmatoarea secveţta de cod:
listaVarfuri[nVarfuri++] = new Vertex ('F');
aceasta inserează un vărf F, unde nVarfuri este numărul curent al vârfurilor din graf. Modul de
adaugarea a unei muchii in graf depinde de tipul structurii de date pe care o folosim pentru
reprezentarea grafului. Să presupunem ca lucrăm cu matricea de adiacenţă si vrem sa introducem
o muchie intre vârfurile 1 si [Link] numere corespund cu indicii tabelului listaVarfuri
unde sunt stocate vârfurile.Când creem o matrice de adiacentă matAdiacenta , inţtial
elementele matricei vor fi [Link] a insera o muchie,vom scrie:
matAdiacenta[1][3] = 1;
matAdiacenta[3][1] = 1;
Dar dacă vom folosi o lista de adiacenta,vom adauga 1 la lista lui 3, si 3 la lista lui 1.

 Clasa Graf

Considerăm următorul program in care avem o clasa Graf ce contine metodele addVertex

addEdge si displayVertex pentru adăugarea vârfurilor şi muchiilor intr-un graf si vizualizarea

acestora:

{
private class Graf
final int V_MAX = 20; // numarul constant maxim de varfuri
private Varf listaVarfuri[]; // lista de varfuri
private int matAdiacenta[][]; // matricea de adiacenta
private int nVarfuri; // numarul curent de varfuri
private StivaX stiva;
// ------------------
public Graf() // constructorul clasei Graf
{
listaVarfuri = new Varf[V_MAX]; //initializam obiectul
listaVarfuri
matAdiacenta = new int[V_MAX][V_MAX]; //initializam Matricea de
adiacenta
nVarfuri = 0;
for(int i=0; i<V_MAX; i++) //initial setam elementele
matricii cu 0
for(int j=0; j<V_MAX; j++)
matAdiacenta[i][j] = 0;
stiva = new StivaX();
} // se incheie constructorul
// ------------------
public void addVertex(char lab) // metoda de adaugare a
unui varf
{
listaVarfuri[nVarfuri++] = new Varf(lab);

33
 }
// ------------------
public void addEdge(int start, int end) //metoda de adaugare a
unei muchii
{
matAdiacenta[start][end] = 1;
matAdiacenta[end][start] = 1;
}
// ------------------
public void displayVertex(int v) //metoda de vizualizare a
varfurilor
{
[Link](listaVarfuri[v].label);
}
} // se incheie clasa Graf
In cadrul clasei Graf vârfurile sunt indentificate prin numărul indicilor din lista de vârfuri
listaVarfuri. Prin constructia [Link](listaVarfuri[v].label) am
tiparit eticheta vârfului nou creat ,pentru vizualizarea. Matricea de adiacentă (sau lista de
adiacentă) furnizează informaţii generale despre vârfuri create,cum ar fi adiacentţa lui cu alte
vârfuri,etc.

3.4. Reprezentarea stivelor şi cozilor in limbajul java

Înainte de a elabora un algoritm, trebuie să ne gandim la modul in care reprezentam datele. În
acest subcapitol vom trece in revistă structurile fundamentale de date cu care vom opera: stive si
cozi. Reprezentarea pe care o vom folosi şi care este cea mai comodă pentru aceste structuri este
cea secvenţiala, bazată pe tablouri.

3.4.1. Stiva
O stivă (stack) este o listă liniara cu proprietatea ca operaţiile de inserare/extragere a
nodurilor se fac în/din coada listei. Dacă nodurile A, B, C, D sunt inserate intr-o stivă in această
ordine, atunci primul nod care poate fi extras este D. In mod echivalent, spunem ca ultimul nod
inserat va fi si primul şters. Din acest motiv, stivele se mai numesc si liste LIFO (Last In First
Out),sauliste pushdown.
Asupra tipului abstract de date stiva sunt definiţi următorii cinci operatori:
1) iniţializare(st) - face stiva st vida ( iniţializarea obiectului se face cu ajutorul unui
constructor)
2) peek(st) - furnizează elementul din virful stivei ( deci primul nod al listei )
3) pop(st) - suprimă elementul din vîrful stivei

34
4) push(i,st) - inserează elementul x in virful stivei pe care il actualizează
5) isEmpty(st) - funcţie booleană ce e adevarată daca stiva este vidă.
Push si pop sunt două operaţii de bază ale stivei. Dar,cateodată este util să fie posibil să
citim valoarea din vârful stivei fară ca s-o extragem. Operatia peek ne permite să efectuam acest
lucru.
Cel mai natural mod de reprezentare pentru o stiva este implementarea secventială intr-un
tablou st [0..dimMax-1], unde n este numărul maxim de noduri. Primul nod va fi memorat in
st[0], al doilea in st[1], iar ultimul in st[top], unde top este o variabilă care conţine
adresa (indicele) ultimului nod [Link]ţial, cand stiva este vidă, avem top = -1.

 Clasa Stiva

In continuare prezentăm un program ce implementează înserarea şi extragerea

elementelor dintr-o stiva.

//[Link] implementeaza o stiva

class StivaX
{
private int dimMax; // dimensiunea listei tip stiva
private int[] st;
private int top; // varful stivei
//--------------------------------------------------------------
public StivaX(int s) // constructorul clasei StivaX
{
dimMax = s; // setam dimensiunea
st = new int[dimMax]; // initializarea stivei (obiectului st)
top = -1; // initial stiva este vida
}
//--------------------------------------------------------------
public void push(int i) // inseram un nod in stiva
{
st[++top] = i; // top se incrementeaza,inseram nodul
}
//--------------------------------------------------------------
public int pop() // extragem un nod din varful stivei
{
return st[top--]; // top se decrementeaza si se extrage nodul
}
//--------------------------------------------------------------
public int peek() // furnizam nodul din varful stivei
{
return st[top];
}
//--------------------------------------------------------------
public boolean isEmpty() // adevarat daca stiva este vida

35
 {
return (top == -1);
}
//--------------------------------------------------------------
public boolean isFull() // adevarat daca stiva este plina
{
return (top == dimMax-1);
}
//--------------------------------------------------------------
} // starsitul clasei StivaX
////////////////////////////////////////////////////////////////
public class Stiva {
public static void main(String[] args) //metoda principala
{
StivaX stiva = new StivaX(10);// crearea obiectului stiva
[Link](10); // inserarea elementelor in stiva
[Link](15);
[Link](23);
[Link](37);
[Link](25);

while( ![Link]() ) // cat timp stiva nu este vida

{ // se extragem elementele din stiva
int value = [Link]();
[Link](value); // vizualizam elementul extras
[Link](" ");
} // se incheie bucla while
[Link](" ");
} // se incheie metoda main()
} // se incheie clasa Stiva

Metoda principală main() crează o stivă ce poate conţine cel mult 10 elemente, inserează
5 elemente in stivă si apoi, vizualizează acestea in ordinea extragerii lor din stivă pană când stiva
va fi goala. La execuţia programului vom obţine următorul rezultat:
25 37 23 15 10
Observăm ca ordinea elementelor este inversă. Deoarece ultimul element inserat este primul
element extras.

Metodele clasei StivaX

► Constructorul StivaX crează o stiva nouă.Dimensiunea stivei este specificată de argumentul s.
Câmpurile constructorului conţin o variabilă ce determină lungimea maximă a stivei
(dimensiunea tabelului), insuşi tabelul, si o variabilă top, care stochează indicele ultimului
element din stiva.
► Metoda push() incrementează variabila top si inserează un element in stivă.Observăm ca
top se incrementează inainte ca elementul sa fie inserat.

36
► Metoda pop() returneazaăultimul element din stivă, si apoi decremeneazaă variabila top.
► Metoda peek()returnează ultimul element din stiăa, nemodificând stiva.
► Metodele isEmpty() si isFull()returnează true daca stiva este goală, respectiv plina.
Atunci cand variabila top are valoarea 1, stiva este goală, si cand are dimMax-1 - stiva este
plină.

3.4.2. Coada

O coadă (queue) este o listă liniară in care elementele sunt inserate la un capăt si sunt
suprimate la celălalt . Cozile se numesc şi liste FIFO (First In First Out), adică de tip primul
venit, primul servit.
Asupra tipului abstract de date coada sunt definiţi urmatorii cinci operatori:
1) iniţializare(cd) - face coada cd vidă (iniţializarea obiectului se face cu ajutorul unui
constructor).
2) peek(cd) - funcţie ce returnează primul element din capul cozii (primul nod al listei).
3) insert(i,cd) - inserează elementul i în coadă.
4) remove(cd) - suprimă primul element inserat in coadă.
5) isEmpty(cd) - funcţie ce e adevarata daca coada este vidă.
Observăm că în cazul unei cozi funcţiile membre puch() si pop() sunt inlocuite cu
insert(), respectiv remove(). În locul variabilei top, vom avea două date membre, si anume
variabilele head si tail.
O reprezentare secventială interesantă pentru coadă se obtine prin utilizarea unui tablou
cd [0..dimMax-1], pe care il tratam ca si cum ar fi circular: dupa locatia cd [dimMax-1]
urmeaza locatia cd [0].
Să presupunem ca avem o coada cu un numar oarecare de locaţii numerotate de la 0 la
dimMax-1. Iniţial coada este goală. Pe masură ce inserăm elemente in coadă acestea ocupa
locaţiile cd [0],cd [1],..., cd [i].Variabila tail va conţine indicele ultimei locaţii
inserate (tail = i). Elementele vor fi extrase din coadă in ordinea in care au fost inserate.
Astfel, cand se va extrage primul element inserat, locatia cd [0] va ramane [Link]
head va conţine indicele locţiei ce urmează sa fie eliberată.De aceea, cand coada este goală si nu
s-a efectuat inca nici o inserare vom avea tail =-1 si head = 0. In timp ce se fac inserări intr-
37
un capăt al cozii si extrageri din celălalt, primele locaţii din coadă se eliberează si ultimele se
ocupaă. Daca ultima locatie din coadă este ocupată ( tail = dimMax-1), inserările se vor face
din nou in primele locaţii (tail = -1). Şi, daca ultima locaţie din coaăa este eliberată ( head =
dimMax), vom incepe să extragem elementele din primele locatii ( head = 0).Observăm ca, spre
deosebire de o stivă, elementele unei cozi nu intotdeauna ocupă primele locaţii din tabel. Odată
ce un element este extras, valoarea lui head va fi indexul urmatoarei locaţii [Link] exemplu,
in figurile date avem o coadă ce contine 10 locatii. Pe masura ce se fac inserări in coadă,
observăm ca se ocupă si ultima locaţie o cozii cd [9]=44. Atunci, următorul element pe care
dorim sa-l inserăm (63), va ocupa prima locaţie liberă din coada - cd s[0]=[Link] java vom
scrie acest lucru prin metoda insert() sub urmatoarea secventa de cod:

public void insert(int i) // inseram un element in coada

{
if(tail == dimMax-1) // daca ultima locatie este inserata
tail = -1;//atunci indicele ultimei locatii inserate devine -1;
cd[++tail] = i;//incrementam variabila tail si inseram un element
}
si in metoda main() vom face apelul la metoda insert()din clasa coadaX in felul următor:

CoadaX coada = new CoadaX(10);// coada va avea 10 locatii

[Link](37); // se insereaza in prima locatie cd[0]=37
... ... ... // se insereaza in urmatoarele locatii
[Link](44); // se insereaza in ultima locatie cd[9]=44
[Link]();// se extrage primul element inserat cd[0]=37
... ... ... // se fac extrageri din urmatoarele locatii
[Link](63);// se insereaza in prima locatie cd[0]=63

 Clasa Coada

În continuare prezentăm un program ce implementează înserarea si extragerea

elementelor dintr-o coadă.

//[Link] implementeaza o coada

class CoadaX
{
private int dimMax; // dimensiunea listei tip coada
private int[] cd;
private int head;
private int tail;
//---------------------------------------------------------------------
public CoadaY(int s) // constructor

38
{
dimMax = s+1; // tabelul este mai mare cu o locatie
cd = new int[dimMax]; // decat se pretinde a fi
head = 0; // initial coada este goala
tail = -1;
}
//---------------------------------------------------------------------
public void insert(int i) // inseram un element in coada
{
if(tail == dimMax-1) // daca ultima locatie a cozii este
ocupata
tail = -1; // inseram elementul in prima locatie
libera
cd[++tail] = i; // tail se incrementeaza si se insereaza
elementul
}
//---------------------------------------------------------------------
public int remove() // extragem un element din coada
{
int temp = cd[head++]; // head se incrementeaza (indicele locatiei din
// care se va extrage
if (head == dimMax)
head = 0;
return temp;
}
//---------------------------------------------------------------------
public int peek() // furnizam nodul din varful cozii
{
return cd[head];
}
//---------------------------------------------------------------------
public boolean isEmpty() // adevarat daca coada este goala
{
return ( tail+1==head || (head+dimMax-1==tail) );
}
//---------------------------------------------------------------------
public boolean isFull() // adevarat daca coada este plina
{
return ( tail +2==head || (head+dimMax-2==tail) );
}
//---------------------------------------------------------------------
public int size() // (ne asiguram daca coada nu este goala)
{
if(tail >= head) // contiguous sequence
return tail-head+1;
else
return (dimMax-head) + (tail+1);
}
//---------------------------------------------------------------------
} // se incheie clasa CoadaX

class Coada {
public static void main(String[] args)
{

39
 CoadaX coada = new CoadaX(5); // coada va avea 5 locatii

[Link](10); // inseram 4 elemente

[Link](20);
[Link](30);
[Link](40);

[Link](); // extragem 3 (10)

[Link](); //(20)
[Link](); //(30)

[Link](50); // inseram 4 elemente

[Link](60); // (facem circuit)
[Link](70);
[Link](80);

while( ![Link]() ) // extragem si vizualizam

{ // elemntele existente in coada
int n = [Link](); // (40, 50, 60, 90, 80)
[Link](n);
[Link](" ");
}
[Link]("");
} // se incheie metoda main()

Programul [Link] constă din două clase CoadaX si Coada. Prima clasă conţine un
constructor prin care se iniţializeaza coada si metodele insert(int i),remove(),peek(),
isEmpty(),isFull()si size().
Metoda principală main()din a doua clasaă crează o coadă cu 5 locatii, inserează 4
elemente (10,20,30,40), extrage primele 3 elemente inserate (10,20,30) si inserează din nou 4
elemente (50,60,70,80). La a sasea inserare se obţine un circuit. Apoi, in bucla while se extrag
elementele existente din coadă si sunt vizualizate in ordinea extragerii lor. La execuţia
programului vom obţine următorul rezultat:
40 50 60 70 80

Metodele clasei CoadaX

► Metoda insert().
Înainte de a insera un element, trebuie sa ne asigurăm ca nu avem o coadă [Link] lucru se
poate verifica prin douaă metode:

40
  In metoda principală se apelează metoda insert()dupa metoda isFull(). Dacă prima
metodă returnează valoarea false , atunci avem locaţii libere in care putem insera si
apelăm metoda insert().
 Se poate verifica daca coada este plină printr-o rutina din metoda insert().In timp ce se
incearcă sa se insereze intr-o coadă plina se va genera o excepţie.
 În metoda insert() se incrementează variabila tail si se inserează un element in
locatia cd[tail].Daca tail contine indicele ultimei locatii din lista, atunci ne
deplasăm la inceputul tabelului inainte de inserare (tail=−1).Astfel, cand se va
incrementa variabila, tail va fi indicele primei locaţii din coadă.
► Metoda remove().
Inainte de a extrage un element, trebuie să ne asigurăm ca existaăelemente in coadaăce pot fi
extrase. Similar cu metoda insert(), avem două posibilitaţti de verificare:
 In metoda principală se apeleaza metoda isEmpty() inaintea metodei remove().Dacă
valoarea returnată a metodei isEmpty()este false, atunci avem elemente in coadă si
le putem extrage.
 Putem construi o eroare de verificare in metoda remove().Daca se va incerca să se
extraga un element dintr-o coada goala, la compilare va aparea un mesaj de eroare.
► Metoda peek()
Aceasta metodă este asemenea cu cea din stivă. Returnează primul element din capul listei
cd[head].

► Metodele isEmpty(),isFull() si size().

Dacă as avea o variabilă de tip intreg ce indica numarul de elemente din coada ( int
nElemente), atunci reprezentarea acestor metode ar fi foarte simplă:

 O coadă este goală cand nu contine nici un element ( nElemente = 0 ).

 O coadă este plina cand toate locaţiile sunt ocupate ( nElemente = dimMax-1 ).

 Pentru a vedea numarul de elemente dintr-o coada la un moment dat, vom returna
variabila nElemente (return nElemente).
Programul [Link] a fost implementat fară aceasta variabila, de aceea s-a determinat dacă
o coadă este goală, respectiv plina si câte elemente contine cu ajutorul variabilelor membre head
si tail.

41
  Vom avea o coadă goală daca locatia în care urmeaza sa se insereze (tail+1) este egala
cu locatia din care urmează să se extraga (head). Astfel tail+1=head sau
head+dimMax-1=tail.

 Să presupunem ca avem o coada plină: s-au inserat elemente in toate locaţiile si nu s-a
extras nici unul diontre ele. Atunci, vom avea head=0 indicele locaţiei din care urmează
 sa se extragă si tail=dimMax-1 indicele locaţie in care s-a facut ultima inserare. Deci,
o coada este plina daca: dimMax-1 +1 = 0  tail+1 = [Link]ăm ca coada
pare a fi plină si goală in acelasi timp. Pentru a evita aceasta constradictie am construit un
tabel cu o celula mai mult fată de numarul maxim de elemente ce pot fi plasate in el
(dimMax = s+1). Astfel, vom avea o coadă plina când tail+2=head sau
head+dimMax-2=tail.

 Pe masur ce se inserează şi se extrag elementele in/din coadă putem avea două situţtii:
 Dacă tail >= head, atunci nElemente = tail-head+1.
 Dacă s-a produs un circuit si head > tail, atunci
nElemente = (dimMax-head) + (tail+1).

3.5 Algoritmul  Depth-First Search (DFS) - parcurgerea in adâncime

Depth-First-Search este tehnica de parcurgere (explorare) a grafurilor in adâncime.
Dat fiind G = (V,E) un graf conex şi nodul sursa s. Vizităm mai intâi nodul s, apoi primul
nod nevizitat adiacent cu s, mergând in adâncime cat este posibil. Când un nod x nu mai are
vecini nevizitati ne intoarcem să cercetam dacă nodul din care a fost atins x mai are sau nu vecini
nevizitaţi si continuam [Link] metoda Depth-First-Search vom folosi stiva pentru ca sa
ştim unde trebuie să mergem după ce am atins ultimul vârf.
Exemplu: Să realizam parcurgerea DFS pentru graful din Figura 8 :
Fixăm nodul de start s = A. Conform algoritmul DFS vizităm acest nod, marcand-ul, ca să stim ca
a fost deja vizitat şi il introducem in stiva, astfel incât sa-l tinem minte. Apoi, alegem un nod
oarecare adiacent cu A, din cele care nu au fost inca vizitate. Daca avem mai multe noduri ce
satisfac aceeasi conditţie (in cazul nostru nodurile B,C,D,E), pentru a ne fi mai usor le vom aşeza
în ordinea alfabetica. Deci, B va fi urmatorul nod vizitat. Il marcam si îl plasăm in stiva. Acum
repetăm acelasi rationament cu nodul B: alegem un nod adiacent cu B, care nu a fost incă
[Link], ajungem la nodurile F si H.
Definim prima regula de parcurgere:

42
 Regula 1: Dacă este posibil,se vizitează un nod adiacent si nevizitat, se marcheazaăsi se
introduce in stiva.
Aplicând regula 1 ajungem la nodul [Link]ăm ca aceasta regula nu mai are aplicabilitate,
deoarece H nu are vârfuri adiacente si nevizitate. În această situatie aplicăm regula a 2-a:
Regula 2: Dacă nu se poate urma regula 1, si este posibil, se scoate un vârf din stivă.
Conform acestei reguli, in exemplul nostru scoatem H din stivă, si ajungem inapoi la F. Acesta
din urma nu are varfuri adiacente nevizitate. Il scoatem din stiva. La fel procedam cu B. Acum
doar A mai este in stiva. A are trei varfuri adiacente nevizitate C,D,E dintre care alegem C,etc.
Repetăm rationamentul, pană când vom reveni din nou la vârful A si vom descoperi ca A nu mai
are vârfuri adiacente nevizitate. Îl scoatem din stivă.Si aplicăm regula 3.
Regula 3: Dacă nu se poate urma nici una din regulile precedente,graful este parcurs si
algoritmul este incheiat.

Fig.4
 Codul java
Scopul algoritmului DFS este de a gasi vârfurile ce nu au fost vizitate şi sunt adiacente cu
un vârf specificat. Pentru a reprezenta acest lucru vom folosi o matrice de adiacentă. Să

43
 presupunem că avem un graf simplu conex ca in Figura 5. Matricea de adiacentă pentru acest
graf este M5×5. Graful nu este orientat, de aceea matricea de adiacentă asociată lui va fi simetrică
fata de diagonala principala. Să presupunem ca incepem parcurgerea grafului de la varful A
(pozitia 0×0 din matrice).
Cautăm vârfurile adiacente cu A, adica elementele de pe prima linie a matricii cu valoarea
1. După ce am gasit vârfurile adiacente cu A, verificăm daca ele nu au fost vizitate. Daca da,
vărful găsit este urmatorul vârf ce va fi vizitat. Daca nu, vom scrie ca nu există pe prima linie
vârfuri adiacente cu A si nevizitate in acelasi timp.
Repetăm rationamentul pentru toate liniile din matrice i= 0,4 .

A B C D E
A 0 1 0 1 0
 
B 1 0 1 0 0
M 55  C 0 1 0 0 0
 
D 1 0 0 0 1
E  0 0 0 1 0 

Fig.5

În java vom reprezenta acest mecanism in metoda

obtineVarfAdiacentNevizitat() prin urmatoare secventă de cod:

//returneaza un varf nevizitat adiacent cu v

public int obtineVarfAdiacentNevizitat(int v)
{
for(int i=0; i<nVarfuri; i++)
if(matAdiacenta[v][i]==1 &&
listaVarfuri[i].aFostVizitat==false)
return i;
return -1;
}

44
 Acum suntem gata pentru metoda dfs() a clasei Graf care practic duce la bun sfârsit
parcurgerea in adâncime (Deph-First-Search). Putem observa ca codul ce urmează va cuprinde
cele trei reguli relatate mai [Link] folosi un ciclu in care se vor efectua anumite operaţii cât
timp stiva nu este goală:
while( ![Link]() )
În cadrul ciclului se vor efectua patru operaţii de bază:
 Se va examina nodul din vârful stivei,folosind metoda peek().
 Se va cauta un vecin nevizitat al acestui vârf.
 Dacă nu se va gasi,vârful nostru se va scoate din stivă
 Dacă se va găsi asemnenea vârf, îl vom vizia si il vom plasa in stivă
Codul pentru metoda dfs() va arăta in felul următor:

public void dfs() // parcurgerea in adancime

{ // vom incepe cu primul varf,cu indicele 0
listaVarfuri[0].aFostVizitat = true; // il marcam
displayVertex(0); // il vizualizam
[Link](0); // inseram in stiva
while( ![Link]() ) // pana cand stiva este goala,
{
// obtinem un varf nevizitat adiacent cu cel din varful stivei
int v = obtineVarfAdiacentNevizitat( [Link]() );
if(v == -1) // daca nu exista asemenea varf,
[Link](); // extragem un varf din stiva
else // daca exista asemenea varf,
{
listaVarfuri[v].aFostVizitat = true; // il marcam
displayVertex(v); // il vizualizam
[Link](v); // il plasam in stiva
}
} //se incheie bucla while
// stiva este goala,am terminat
for(int i=0; i<nVarfuri; i++) // resetam flagurile
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda dfs()

La sfărsitul metodei dfs() am resetat toate flagurile care au fost vizitate astfel incât să
putem rula metoda din nou.În timp ce stiva este goală din nou si nu necesita sa fie
resetată.Deci, avem toate componentele necesare unei clase Graf.În continuare vom crea graful
din Figura 5 (un obiect al clasei Graf), vom adăuga vârfurile si muchiile acestuia, si vom realiza
o parcurgere in adâncime:

Graph unGraf = new Graph();

[Link]('A'); // 0 varful de start in parcurgerea
dfs

45
 [Link]('B'); // 1
[Link]('C'); // 2
[Link]('D'); // 3
[Link]('E'); // 4

[Link](0, 1); // AB
[Link](1, 2); // BC
[Link](0, 3); // AD
[Link](3, 4); // DE

[Link]("Ordinea de parcurgere in adancime a varfurilor

este:");
[Link](); //apelam metoda dfs()
[Link]();

La execuţia programului vom obţine următorul rezultat:

Ordinea de parcurgere in adancime a varfurilor este: ABCDE
Astfel, putem reprezenta oricare alt graf si urmări cum se desfasoara parcurgerea lui in
adâncime.
Pentru a finisa reprezentarea algoritmului Depth-First-Search prezentăm programul
[Link], ce reuneşte clasele StivaX,Varf,Graf si DFS. Programul crează graful din Figura
5 şi efectueazaăparcurgerea lui in adâncime:

package Grafuri;
class StivaX
{
private final int SIZE = 20;
private int[] st;
private int top;
public StivaX() // constructor
{
st = new int[SIZE]; // initializam stiva,cream un tablou
top = -1;
}
public void push(int j) // inseram elementul in stiva
{ st[++top] = j; }
public int pop() // extragem elementul din stiva
{ return st[top--]; }
public int peek() // furnizam nodul din varful stivei
{ return st[top]; }
public boolean isEmpty() // adevarat daca stiva este vida
{ return (top == -1); }
} // starsitul clasei StivaX
////////////////////////////////////////////////////////////////
class Varf
{
public char label; // eticheta varfului,'A' de exemplu
public boolean aFostVizitat;
// ------------------

46
public Varf(char lab) // constructor
{
label = lab;
aFostVizitat = false;
}
// ------------------
} // se incheie clasa Varf
////////////////////////////////////////////////////////////////
class Graf
{
private final int V_MAX = 20;
private Varf listaVarfuri[]; // lista de varfuri
private int matAdiacenta[][]; // matricea de adiacenta
private int nVarfuri; // numarul curent de varfuri
private StivaX stiva;
// ------------------
public Graf() // constructorul clasei Graf
{
listaVarfuri = new Varf[V_MAX];
// matricea de adiacenta
matAdiacenta = new int[V_MAX][V_MAX];
nVarfuri = 0;
for(int i=0; i<V_MAX; i++)//setam matricea de adiacenta cu 0 initial
for(int j=0; j<V_MAX; j++)
matAdiacenta[i][j] = 0;
stiva = new StivaX();
} // se incheie constructorul
// ------------------
public void addVertex(char lab)
{
listaVarfuri[nVarfuri++] = new Varf(lab);
}
// ------------------
public void addEdge(int start, int end)
{
matAdiacenta[start][end] = 1;
matAdiacenta[end][start] = 1;
}
// ------------------
public void displayVertex(int v)
{
[Link](listaVarfuri[v].label);
}
// ------------------
public void dfs() //parcurgerea in adancime
{ // vom incepe cu primul varf,cu indicele 0
listaVarfuri[0].aFostVizitat = true; // il marcam
displayVertex(0); // il vizualizam
[Link](0); // inseram in stiva
while( ![Link]() ) // pana cand stiva este goala,
{
// obtinem un varf nevizitat adiacent cu cel din varful stivei
int v = obtineVarfAdiacentNevizitat( [Link]() );
if(v == -1) // daca nu exista asemenea varf,

47
 [Link](); // extragem un varf din stiva
else // daca exista asemenea varf
{
listaVarfuri[v].aFostVizitat = true; // il marcam
displayVertex(v); // il vizualizam
[Link](v); // il plasam in stiva
}
} // se incheie bucla while
// stiva este goala,am terminat
for(int i=0; i<nVarfuri; i++) // resetam flagurile
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda dfs()
// ------------------
//returneaza un varf nevizitat adiacent cu v
public int obtineVarfAdiacentNevizitat(int v)
{
for(int i=0; i<nVarfuri; i++)
if(matAdiacenta[v][i]==1 && listaVarfuri[i].aFostVizitat==false)
return i;
return -1;
} // se incheie metoda obtineVarfAdiacentNevizitat()
} // se incheie clasa Graf
////////////////////////////////////////////////////////////////
public class DFS {

public static void main(String[] args)

{
Graf unGraf = new Graf();
[Link]('A'); // 0 (varful de start in parcurgerea dfs)
[Link]('B'); // 1
[Link]('C'); // 2
[Link]('D'); // 3
[Link]('E'); // 4

[Link](0, 1); // AB
[Link](1, 2); // BC
[Link](0, 3); // AD
[Link](3, 4); // DE

[Link]("Ordinea de parcurgere in adancime a varfurilor

este: ");
[Link](); // apelam metoda dfs()
[Link]();
}
}

3.6 Algoritmul  Breadth-First Search (BFS) - parcurgerea in laţime

O alta tehnică de parcurgere (explorare) a grafurilor este metoda Breadth-First-Search

(parcurgerea in laţime).

48
 Dat fiind un graf conex G = (E,V) şi un nod sursa s  V, metoda BFS impune vizitarea
mai intâi a nodului şi, apoi a tuturor nodurilor nevizitate adiacente cu s, apoi a tuturor nodurilor
nevizitate adiacente nodurilor adiacente cu s, s.a.m.d.
Aşa cum am văzut în parcucgerea Depth-First-Search ne indepărtam de vârful de start cât
mai repede posibil. Pe de altă parte, in parcurgerea Breadth-First-Search observăm ca algoritmul
preferă să stea cat mai aproape de vârful de start. Conform algoritmului BFS in primul rând se
vizitează toate varfurile adiacente cu vârful de start, si abia după aceea următoarele vârfuri. Spre
deosebire de parcurgerea in adâncime, parcurgerea in lăţime nu este in mod natural recursivă.
Pentru parcurgerea in lătime,vom utiliza o coada.
 Codul java
Metoda bfs() a clasei Graf este similară cu metoda dfs(), cu exceptiă faptului ca se foloseste
o coadă in locul unei stive si coţine două bucle while , una in interiorul alteia. Bucla
exterioară asteapta ca coada sa fie goaăa, in care bucla interioară caută un vârf nevizitat si
adiacent cu un vârf curent.
Codul pentru metoda bfs() va arata in felul următor:

public void dfs() // parcurgerea in latime

{ // vom incepe cu primul varf,cu indicele 0
listaVarfuri[0].aFostVizitat = true; // il marcam
displayVertex(0); // il vizualizam
[Link](0); // inseram in coada
int v2;
while( ![Link]() ) // cat timp coada este goala,
{
int v1 = [Link](); // extragem varful din capul cozii
// cat timp acest varf nu are vecini nevizitate
while ( (v2 = obtineVarfAdiacentNevizitat(v1)) != -1 )
{
listaVarfuri[v2].aFostVizitat = true; // il marcam
displayVertex(v2); // il vizualizam
[Link](v2); // il inseram in coada
} //se incheie bucla while interna
} //se incheie bucla while externa

// coada este goala,am terminat

for(int i=0; i<nVarfuri; i++) // resetam flagurile
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda bfs()

În continuare prezentăm programul [Link] care crează graful din Figura 5 si efectuează
parcurgerea lui in lăţ[Link] program este similar cu programul [Link] cu exceptia

49
introducerii clasei CoadaX in locul clasei StivaX si a metodei bfs() in locul metodei
dfs().
//programul [Link] efectueaza parcurgearea in latime a unui graf
package Grafuri;
class CoadaX
{
private final int SIZE = 20;
private int[] cd;
private int head;
private int tail;
public CoadaX() // constructor
{
cd = new int[SIZE]; // initializam coada,cream un tablou
head = 0;
tail = -1;
}
public void insert(int i) // inseram un elemnt in coada
{
if(tail == SIZE-1)
tail = -1;
cd[++tail] = i;
}
public int remove() // extragem un element din coada
{
int temp = cd[head++];
if(head == SIZE)
head = 0;
return temp;
}
public boolean isEmpty() // adevarat daca coada este goala
{
return ( tail+1==head || (head+SIZE-1==tail) );
}
} // se incheie clasa CoadaX
////////////////////////////////////////////////////////////////
class Varf1
{
public char label;
public boolean aFostVizitat;
// -------------------------------------------------------------
public Varf(char lab) // constructor
{
label = lab;
aFostVizitat = false;
}
// -------------------------------------------------------------
} // se incheie clasa Varf
////////////////////////////////////////////////////////////////
class Graf
{
private final int V_MAX = 20;
private Varf listaVarfuri[]; // lista de varfuri
private int matAdiacenta[][]; // matricea de adiacenta

50
 private int nVarfuri; // numarul curent de varfuri
private CoadaX coada;
// ------------------
public Graf() // constructorul clasei Graf
{
listaVarfuri = new Varf[V_MAX];
matAdiacenta = new int[V_MAX][V_MAX]; // matricea de adacenta
nVarfuri = 0;
for(int i=0; i<V_MAX; i++) // setam elementele matricei
// initial cu 0
for(int j=0; j<V_MAX; j++)
matAdiacenta[i][j] = 0;
coada = new CoadaX();
} // se incheie constructorul
// -------------------------------------------------------------
public void addVertex(char lab)
{
listaVarfuri[nVarfuri++] = new Varf(lab);
}
// -------------------------------------------------------------
public void addEdge(int start, int end)
{
matAdiacenta[start][end] = 1;
matAdiacenta[end][start] = 1;
}
// -------------------------------------------------------------
public void displayVertex(int v)
{
[Link](listaVarfuri[v].label);
}
// -------------------------------------------------------------
public void bfs() // parcurgerea in latime
{ // vom incepe cu primul varf
listaVarfuri[0].aFostVizitat = true; // il marcam
displayVertex(0); // il vizualizam
[Link](0); // inseram in coada
int v2;

while( ![Link]() ) // cat timp coada nu este vida,

{
int v1 = [Link](); // extragem un varf din capul cozii
// cat timp v2 este un varf nevizitat si adiacent cu v1
while( (v2=obtineVarfAdiacentNevizitat(v1)) != -1 )
{
listaVarfuri[v2].aFostVizitat = true; // il marcam
displayVertex(v2); // il vizualizam
[Link](v2); // il inseram
} // se incheie bucla while interna
} // se incheie bucla while externa

// coada este goala,am terminat

for(int i=0; i<nVarfuri; i++) // resetam flagurile
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda bfs()

51
// -------------------------------------------------------------
// returnam un varf nevizitat adiacent cu v
public int obtineVarfAdiacentNevizitat(int j)
{
for(int i=0; i<nVarfuri; i++)
if(matAdiacenta[j][i]==1 && listaVarfuri[i].aFostVizitat==false)
return i;
return -1;
} // se incheie metoda obtineVarfAdiacentNevizitat()
// -------------------------------------------------------------
} // se incheie clasa Graf
////////////////////////////////////////////////////////////////
class BFS
{
public static void main(String[] args)
{
Graf unGraf = new Graf();
[Link]('A'); // 0(varful de start in parcurgerea bfs)

[Link]('B'); // 1
[Link]('C'); // 2
[Link]('D'); // 3
[Link]('E'); // 4

[Link](0, 1); // AB
[Link](1, 2); // BC
[Link](0, 3); // AD
[Link](3, 4); // DE

[Link]("Ordinea de parcurgere in latime a varfurilor

este: ");
[Link](); // parcurgerea in latime
[Link]();
} // se incheie metoda main()
} // se incheie clasa BFS
////////////////////////////////////////////////////////////////

3.7. Algoritmul  de căutare a unui arbore de acoperire de lungime

minimă (Minimum Spanning Tree)
3.7.1. Reprezentarea algoritmului

Să presupunem că am proiectat un circuit electronic şi dorim sa ne asigurăm ca am folosit

un numar minim de trasee, că nu avem trasee in plus intre pini care să ocupe loc sau care să
ingreuneze proiectarea. Daca am avea un algoritm ce ne-ar ajuta sa determinam aceste trasee si sa
le indepărtam, proiectarea ar fi mult mai simplă. În rezultat, am obtine un graf cu un număr
minim de muchii necesare pentru conectarea tuturor vârfurilor. De exemplu, in Figura 6 a) avem

52
cinci vârfuri cu un număr excesiv de muchii, in timp ce in Figura 6 b) avem aceleasi varfuri cu un
numar minim de muchii necesare pentru a conecta toate cele cinci varfuri. Acesta reprezinta un
arbore de acoperire de lungime minima (minimum spanning tree). Pot exista mai multi arbori de
acoperire de lungime minima pentru acelasi set de varfuri. In Figura 6 b) sunt aratate muchiile
AB, BC, CD si DE, dar, la fel de bine se poate construi un arbore de acoperire de lungime
minima cu muchiile AC, CE, ED, si DB. Observam ca, intr-un arbore de acoperire de lungime
minima numarul de muchii este intotdeauna mai mic cu o unitate fata de numarul de varfuri (E =
V − 1) .

a)Numarul maxim de muchii posibile b) Numarul minim de muchii

Fig.6
Algoritmul pentru arborele de acoperire de lungime minima este aproape identic cu cel
folosit pentru parcurgerea unui graf. Acesta se bazeaza pe parcurgerea in adancime (depth-first-
search) sau parcurgerea in latime (breadth-first-search). In exemplul de mai jos vom folosi
parcurgerea [Link] vedea ca executand parcurgerea in adancime si inregistrand
muchiile pe care le-am parcurs, se va construi automat un arbore de acoperire de lungime
minima. Singura diferenta intre metoda mst()(minimum spanning tree), pe care o vom explica
mai jos si metoda dfs() reprezentata mai sus este ca in metoda mst() trebuie sa inregistram
intr-un fel muchiile parcurse.
Prin urmare, putem sa construim un program [Link] asemanator cu programul
[Link], in care vom avea o metoda noua mst() asemenea cu metoda dfs(). In metoda

53
principala vom contrui graful din Figura 6 a) si vom apela metoda mst()pentru a determina un
arbore de acoperire de lungime minima asemenea celui din Figură b) .
Diferenta intre metodele dfs() si mst() este ca in clauza else din ultima metoda sunt
vizualizate doua varfuri in locul unui singur varf: varful curent si urmatorul varf nevizitat vecin
al acestuia. Ele determina o muchie parcursa de algoritm pentru a ajunge la urmatorul varf si care
va apartine unui arbore de acoperire de lungime minima.
In java metoda mst()va avea urmatoarea secventa de cod:

public void mst() // arbore de acoperire de lungime minima

//(parcurgerea in adancime)
{ // vom incepe cu primul varf,cu indicele 0
listaVarfuri[0].aFostVizitat = true; // il marcam
[Link](0); // inseram in stiva

while( ![Link]() ) // cat timp stiva nu este goala,

{ // determinam varful stivei
int varfCurent = [Link]();
// obtinem urmatorul varf vecin nevizitat
int v = obtineVarfAdiacentNevizitat( varfCurent );
if(v == -1) // daca nu exista asemenea varf,
[Link](); // extragem un varf din stiva
else // daca exista asemenea varf
{
listaVarfuri[v].aFostVizitat = true; // il marcam
[Link](v); // il inseram in stiva
displayVertex(varfCurent); //vizualizam muchia de la varful
// curent
displayVertex(v); // la varful nou gasit v
[Link](" ");
}
} // se incheie bucla while
// stiva este goala,am terminat
for(int i=0; i<nVarfuri; i++) // resetam flagurile
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda mst()-minimum spanning tree

In metoda principala a programului [Link] vom crea graful din Figura 6 a) si vom
face apelul la metoda mst()in felul urmator:
public class MST {

public static void main(String[] args)

{
Graf unGraf = new Graf();
[Link]('A'); // 0(varful de start)
[Link]('B'); // 1

54
 [Link]('C'); // 2
[Link]('D'); // 3
[Link]('E'); // 4
[Link](0, 1); // AB
[Link](0, 2); // AC
[Link](0, 3); // AD
[Link](0, 4); // AE
[Link](1, 2); // BC
[Link](1, 3); // BD
[Link](1, 4); // BE
[Link](2, 3); // CD
[Link](2, 4); // CE
[Link](3, 4); // DE
[Link]("Arborele de acoperire de lungime minima este: ");
[Link](); // apelam metoda mst()
[Link]();
} //se incheie metoda principala
} // se incheie clasa MST

La executia programului [Link] vom obtine un arbore de acoperire de lungime

minima care va contine doar patru muchii (Figura 6 b) ) din cele zece ale grafului initial. La
iesire vom avea urmatorul rezultat:
Arborele de acoperire de lungime minima este: AB BC CD DE

3.7.2 Întroducerea datelor de la tastatură. Importarea claselor.

Vom modifica putin programul [Link] ca sa oferim utilizatorului posibilitatea sa
aleaga varful de start pentru parcurgerea grafului. In rezultat, in dependenta de varful ales,vom
vedea ca obtinem arbori partiali de acoperire de lungime minima diferiti. Pentru a realiza acest
lucru vom costrui o metoda noua citireVarf() in clasa Graf cu ajutorul careia vom citi
datele introduse de la tastatura. In timpul executiei acestei metode pot aparea erori, care lanseaza
(throws) o exceptie de tip [Link] aceea, in asemenea situatii, este necesar sa scriem
clauza throws IOException dupa antetul metodelor main(),citireVarf() si mst().
În programele Java pot fi folosite direct toate clasele din pachetul [Link], pachet
care conţine elementele de baza ale limbajului. Dacă un program foloseşte clase din alte pachete,
atunci pachetele respective trebuie precizate explicit in program. Această precizare se face cu
ajutorul instrucţiunii import.        
Metoda citireVarf() pe care o folosim pentru introducerea datelor de la tastatură
utilizează clase din pachetul [Link], pachet destinat operaţiilor de intrare / ieşire (input /
output). De aceea, în programele în care folosim această metodă trebuie să introducem

55
instrucţiunea: import [Link].*;.Această instrucţiune permite să se preia toate clasele
necesare din pachetul [Link] .
Clasele apelate dintr-un program care nu aparţin pachetului [Link] se pot preciza şi
individual. Astfel, in metoda citireVarf() sunt folosite clasele InputStreamReader,
BufferedReader şi IOException. De aceea, programul in care sunt folosite aceste clase ar
putea conţine instrucţiunile:
import [Link];
import [Link];
import [Link];
Pare mai comod să precizăm intreg pachetul din care se preiau clasele, dar printr-o
instrucţiune de forma import [Link].*; nu se pun in evidenţă clasele care sunt utilizate
efectiv de program.
In continuare prezentam metoda citireVarf ( ) si metoda mst()cu urmatoarele
modificari:
public String citireVarf() throws IOException {
String h;
//cream un flux pentru procesarea datelor
InputStreamReader f=new InputStreamReader([Link]);
BufferedReader g=new BufferedReader(f);
h=[Link](); // permite citirea unui flux linie cu linie
return h;
}
//-------------------
public void mst() throws IOException
//arbore de acoperire de lungime minima (parcurgerea in adancime)
{
String s;
int varfStart;
[Link]("Alegeti varful de start intre 0 si 4 :");
// oferim utilizatorului posibilitatea sa aleaga varful de start
// intre cele cele posibile
s=citireVarf(); // apelam metoda citireVarf()
varfStart=[Link](s).intValue(); //convertim valoarea lui
// s intr-un numar intreg
if (varfStart > 5)
[Link]("Ati introdus un varf inexistent !" );

else {
[Link]("Arborele de acoperire de lungime minima
este:");
listaVarfuri[varfStart].aFostVizitat = true; // il marcam
[Link](varfStart); // inseram in stiva

while( ![Link]() ) // cat timp stiva nu este goala,

{ // determinam varful stivei
int varfCurent = [Link]();

56
 // obtinem urmatorul varf vecin nevizitat
int v = obtineVarfAdiacentNevizitat( varfCurent );
if(v == -1) // daca nu exista asemenea varf,
[Link](); // extragem un varf din stiva
else // daca exista asemenea varf
{
listaVarfuri[v].aFostVizitat = true; // il marcam
[Link](v); // il inseram in stiva
displayVertex(varfCurent);// vizualizam muchia de la
// varful curent
displayVertex(v); // la varful v
[Link](" ");
}
} // se incheie bucla while
// stiva este goala,am terminat
}
for(int i=0; i<nVarfuri; i++)
listaVarfuri[i].aFostVizitat = false;
} // se incheie metoda mst()-minimum spanning tree
Asa cum am vazut, executia programului incepe cu metoda main().Ca urmare, după
lansarea programului in execuţie, pe ecranul calculatorului apare textul:
Alegeti varful de start intre 0 si 4 :
şi programul aşteaptă să introducem un număr intreg. Programul trece in starea de aşteptare in
momentul execuţiei instrucţiunii h=[Link](); din metoda citireVarf(). Şirul tastat de
noi este atribuit variabilei h. Acest şir este returnat in metoda mst() şi se atribuie variabilei s.
Valoarea variabilei s este convertită la un număr intreg in timpul execuţiei instrucţiunii
varfStart=[Link](s).intValue(); Numărul intreg obţinut in urma
conversiei este atribuit variabilei varfStart ce determina varful cu care vom incepe
parcurgerea grafului.
Pentru a face posibil fluxul de date intre utilizator si computer am intrebuintat in metoda
citireVarf() urmatoarele doua clasele din pachetul [Link] :
 BufferedReader  clasa folosita pentru a introduce un buffer in procesul de citire a
informatiilor, reducand astfel numarul de accese la dispozitivul ce reprezinta sursa
originala de [Link] mult mai eficienta decat fluxul fara buffer si din acest motiv se
recomanda folosirea acestei clasei ori de cate ori este posibil.
 InputStreamReader  aceasta clasa formeaza o punte de legatura intre fluxurile de
caractere si fluxurile de octeti. Un flux InputStreamReader citeste octeti dintr-un flux
InputStream convertindu-le in caractere folosind codificarea standard sau o codificare
specificata de program.

57
Orice flux este un obiect al clasei ce implementeaza fluxul [Link] unui flux se
realizeaza asadar similar cu crearea obiectelor prin intructiunea new. Crearea unui flux primitiv
de date care citeste informatii de la un dispozitiv extern are forma generala:
FluxPrimitiv numeFlux = new FluxPrimitiv (dispozitiv extern)
Fluxirile de procesare nu pot exista de sine statator, ci se suprapun pe un flux primitiv de citire a
datelor. Din acest motiv constructorii claselor pentru fluxurile de procesare nu primesc ca
argument un dispozitiv extern de memorare a datelor, ci o referinta la un flux primitiv responsabil
cu citirea efectiva a datelor.

Capitolul 4-Interfeţe [Link] aplicaţiei în limbajul

java

4.1 Interfeţe grafice. Pachetul [Link]

    Acest pachet ne ofera o coletie de clase pentru crearea interfetelor grafice. Aceste clase permit
lucrul cu ferestre, desenari, lucrul cu imagini si utilizarea componentelor ca butoane, liste,
meniuri intr-un mod independent de platforma. Pachetul [Link] contine clasele AWT (Abstract
Window Toolkit) GUI iar [Link] ne ofera niste facilitati in plus pentru lucrul cu imagini.
Dupa cum numele sugereaza AWT este o abstractie. Clasele si functionalitatile oferite sunt
aceleasi pentru orice implementare Java. Pentru a obtine Independenta de platforma AWT
utilizeaza toolkituri interschimbabile care actioneaza cu sistemul de ferestre pe care se ruleaza
aplicatia. De exemplu sa presupunem ca aplicatia noastra creaza un buton. Cand se ruleaza
aplicatia, toolkitul specific platformei afiseaza butonul conform platformei. Daca aplicatia se
ruleaza sub Windows vom obtine un buton de tip Windows, iar daca  se ruleaza sub Unix se va
afisaun buton de tip X Windows.
Utilizarea componentelor din acest pachet este relativ usoara, pe cand toolkiturile GUI sunt
foarte complexe, dar aceasta este treaba celor care vor sa implementeze AWT-ul pe o noua
platforma.
Realitatea este ca cele mai multe probleme despre Java se ridica la folosirea acestui pachet.
Implementarea toolkiturilor pentru acest pachet contin cele mai multe buguri Java. Tocmai din

58
aceasta cauza JavaSoft a introdus Swing care reprezinta noua generatie de componentele
grafice si fac parte din JFC (Java Foundation Classes).

4.1.1Componente grafice

Componentele sunt elementele care se utilizeaza la crearea unei interfete grafice. Componentele
sunt incluse in containere, care la randul lor sunt componente speciale. Anumite componente
pot fi containere pentru alte componente: de exemplu o fereastra cu doua panouri. In acest caz
fereastra este containerul, iar panelele sunt componentele continute. Daca adaugam elemente ca
butoane, liste, etichete, casete text etc. in cele doua panouri atunci panoul va fi containerul iar
elementele adaugate vor fi componentele.

Fig.1 Erarhia claselor pentru componente

Pentru simplitate impartim functionalitatea clasei Component in doua categorii: modul de

afisare si comportament. Aceasta  clasa contine metode si variabile care controleaza modul de
afisare general al componentei. Aici sunt incluse atributele pentru vizibilitate, marime, pozitie
si atribute ca culoarea si fontul. Clasa contine metode abstracte, care sunt implementate de
subclasele pentru diferite tipuri de componente, si care determina imaginea grafica a
componentei. Prin comportamentul componentei intelegem actiunile componentei la
evenimentele primite de la  utilizator. In momentul cand utilizatorul actiuneaza asupra unei
componente (de exemplu apasa butonul mouse-ului) un fir de executie AWT informeaza toti
receptorii (componentele care vor sa primeasca acest eveniment) despre evenimentul produs. De

59
exemplu la apasarea unui buton se genereaza evenimentul ActionEvent. Cei care vor sa primeasca
acest eveniment trebuie sa fie inregistrati, aceasta insemnand ca trebuie sa fie obiecte care
respectainterfataActionListener.
    Evenimentele sunt receptionate de catre obiecte de tip Listener, care la primirea evenimentului
apeleaza o metoda de tratare a evenimetului. Obiectele care doresc sa primeasca evenimente
trebuie sa implementeze interfetele pentru tipurile de evenimente pe care doresc sa le primeasca.
De exemplu evenimentele de tip MouseEvents sunt primite de catre obiectele care respecta
interfata MouseListener. Evenimentele reprezinta un mecanism de comunicare intre obiecte (nu
numai obiecte grafice). Evenimentele sunt importante mai alesin cazul beanurilor Java.
    Containerele rezolva tratarea evenimentelor pentru toate componentele continute. De obicei
containerul se inregistrează la sursa de evenimente pentru a primi evenimentele necesare pentru o
anumită componentă.

4.1.2. Peer
În sectiunea precedentă tocmai am descris functionarea acestor componente si evenimentele cu
ajutorul carora aceste componente comunică intre ele. Asa sunt privite componentele de Java, dar
nu si in lumea reală, adica pe platforma pe care vor fi efectiv afisate componentele. Lumea reală
este caracterizata de o anumita arhitectura si de dispozitive fizice. La un anumit nivel obiectele
noastre vor comunica cu obiecte care contin metode native pentru mediul  in care componentele
trebuie sa interacţioneze. Pentru a tine această interactiune sub control Java utilizează interfeţele
peer.  Această interfată peer face posibilă ca o componenta AWT Java  sa utilizeze componenta
corespunzatoare din lumea reală - obiectul peer  din mediul nativ. Programele noastre vor lucra
cu obiectele AWT Java, restul, partea grea este rezolvata de clasa Component.

Este important sa intelegem aceasta arhitectură deoarece astfel putem intelege cam ce putem
realiza cu componentele. În figura precedentă se poate vedea ce se intampla la crearea unui
buton. Toolkitul este de fapt o "fabrica de componente" native. Java utilizeaza aceasta fabrica
pentru a separa funtionalitatea componentelor de modalitatea de implementare pe un sistem de
afisare nativ. Obiectul Toolkit contine metode pentru crearea tuturor tipurilor de componente
grafice. Daca nu ne place acest Toolkit oferit de mediul Java, putem sa scriem toolkitul nostru
propriu.
    Pachetul [Link] contine o interfata pentru fiecare tip de componenta grafica. În acest
pachet clasa de baza este ComponentPeer de la care se deriva aproape toate celelalte clase

60
 4.1.3. Afişarea componentelor

Componetele pot fi rugate sa se autoafiseze. De exemplu daca fereastra care contine

componentele este acoperita de o alta fereastra, in momentul revenirii la fereastra initiala aceasta
trebuie reafisata cel putin partial. Cand AWT roaga componenta sa se autoafiseze, aceasta
apeleaza metoda paint(). Metoda update() are aceasi functionalitae, dar aceasta prima data sterge
suprafata componentei si dupa aceea apeleaz metoda paint(). Componentele nu vor apela direct
update(), aceasta metoda fiind apelata de catre repaint(). Aceasta metoda roaga AWT sa
programeze componenta in cauza pentru improspatare. Atat paint() cat si update() au un
parametru de tip Graphics care reprezinta contextul grafic a componentei in cauza. Corespunde
suprafetei ecran pe care componenta poate desena. Acesta este mecanismul utilizat de
componente pentru autoafisare. Noi vom utiliza aceste metode doar in cazul containerelor
speciale, adica in cazul obiectelor de tip Panel, Canvas si Applet.
 
4.1.4. Organizarea componentelor
Un organizator al componentelor este un obiect care stabileste marimea si pozitia componentelor
in cadrul unui container. Fiecare container are un organizator implicit care in caz de necesitate
poate fi modificat. Containerele principale sunt diferitele tipuri de ferestre, apleturi, panele etc. In
cazul ferestrelor organizatorul implicit este un obiect de tip BorderLayout, iar in cazul apleturilor
si ale panourilor unul de tip FlowLayout. Clasele principale organizatori de componente sunt:
FlowLayot, GridLayout,CardLayout, BorderLayout si GridBagLayout.

61
FlowLayout organizeaza componentele de la stanga la dreapta si daca se umple randul curent
atunci componetul urmator va fi plasat in randul urmator. Inaltimea randului este data de
componenta de cea mai mare inaltime pe randul respectiv.  

FlowLayout fLayout = new FlowLayout();

setLayout( fLayout );
Button butonOk = new Button("Ok");
add(butonOk);
Button butonCancel = new Button("Cancel");
add(butonCancel);
sau scris mai compact:
set Layou(new Flow La yout();
add(new Button("Ok"));
add( new Button("Cancel"));

Organizatorul centreaza componentele adaugate, dar acest tip de aliniere poate fi schimbata prin
metoda setAlignment(). Metoda primeste ca parametru tipul alinierii. Tipurile de aliniere posibile
sunt definite ca constante in clasa FlowLayout (LEFT, RIGHT, CENTER)  si se utilizeaza in
modul urmator:

FlowLayout fLayout = new FlowLayout();

[Link]([Link])
setLayout( fLayout );

BorderLayout aranjeaza componentele in cinci regiuni: Nord, Sud, Vest, Est si Centru. La
adaugarea componentelor utilizand acest organizator trebuie specificat pe langa componenta
adaugata si regiunea la care se adauga. Atat Border Layout cat si CardLayout specificarea
spatiului intre componente indicand numarul de pixeli pe orizontala respectiv pe verticala.

62
setLayout( new BorderLayout(), 10,6);
add( new Button("Unu"),"North");
add( new Button("Doi"),"East");
add( new Button("Trei"),"South");
add( new Button("Patru"),"West");

CardLayout (teanc de carti) se utilizeaza la organizarea componentelor care nu incap pe o

anumita suprafata. Componentele sunt organizate pe aceste carti dintre care unul singurul se va
vedea pe ecran. Visual Caffe introduce ferestrele cu mai multe pagini care pot inlocui acest
organizator.

GridLayout imparte suprafata in randuri si coloane permitand aranjarea componentelor in aceste

celule de dimensiuni egale. Componentele sunt plasate in celule incepand cu primul rand dupa
aceea urmatorul rand si asa mai departe.

GridBagLayout este organizatorul cel mai avansat. Lucreaza asemanator ca GridLayout.

Principala diferenta fata de acesta este ca in caul acestui organizator o componenta poate ocupa
mai mult decat o singura celula.

4.2. Pachetele AWT şi SWING

4.2.1. Notiuni generale

O interfată grafică se creaza de obicei cu sprijinul sitemului de operare (printr-o componenta

numita server grafic).

Limbajul Java pune la dispozitia programatorului doua biblioteci pentru realizarea unei interfete
grafice: [Link] si [Link]. In figura sunt expuse clasele corespondente cu cele din awt:

63
   

In plus fata de pachetul standard awt, pachetul swing adauga noi clase care permit imbunatatirea
interfetei realizate. In figura urmatoare sunt prezentate clasele noi introduse de catre swing:

64
   

4.2.2. Ferestre

Oricarei aplicatii grafice ii corespunde o fereastra principala (de tip FRAME) si una sau mai
multe ferestre [Link] swing exista trei clase pentru gestionarea ferestrelor: Jframe,
JWindow si JDialog.

Clasa JFrame permite crearea unei ferestre de aplicatie. Fereastra are o bara de titlu, o margine,
butoane de minimizare, maximizare si inchidere (butoane "system").

Clasa JWindow permite crearea unei ferestre fara bara de titlu, meniu, butoane sistem etc.

Clasa JDialog permite crearea de ferestre de dialog. Ferestrele de dialog sunt dependente de
ferestrele parinte de tip Frame. O fereastra de dialog poate fi modala (blocheaza aplicatia pana la
inchiderea dialogului) sau nemodala (nu blocheaza).

65
Pentru a crea ferestre de afisare a unor mesaje se poate utiliza direct o functie statica, fara a mai
crea explicit un obiect tip dialog:

[Link](frame, “Mesajul meu.");

Pentru ferestre de dialog standard exista clase specializate: JFileChooser si JColorChooser.

Acestea pot fi utilizate pentru a selecta un fisier sau a alege o culoare.

Crearea unei ferestre principale:

public static void main(String args[]) {

   JFrame win = new JFrame(“Titlul ferestrei");
   [Link](200, 200);
   [Link]();
}

Pentru a accesa continutul unei ferestre se va folosi functia getContentPanel():

Container c = [Link]();

Pentru a obtine inchiderea automata a aplicatiei atunci cand se apasa butonul de Close, se va
utiliza metoda:

setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

Pentru a organiza elementele intr-o fereastra se vor utiliza panouri. Swing pune la dispozitie doua
tipuri de panouri: JPanel (panou simplu) si JScrollPane (panou cu derulare).

4.3. Elemente de control (widgets)

4.3.1. Butoane

Butoanele deriva din clasa JButton. In costructor primesc textul afisat pe buton. Prin procedura
setMnemonic se pot asocia taste de apelare rapida (shortcut).

Pentru a adauga un cuvant de comanda asociat butonului (cuvant ce va fi testat pentru efectuarea
actiunii asociate) se foloseste metoda addActionCommand().

JButton buton = new JButton("I'm a Swing button!");

[Link]('i');
[Link]("butonulSwing");
JPanel panouButon = new JPanel();
[Link](buton);

66
 [Link]. RadioButton

Butoanele radio sunt elemente de control care retin o anumita stare, la fel cu cele de marcaj.
Deosebirea principala consta in faptul ca toate butoanele radio incluse in acelasi grup logic sunt
mutual exclusive. Pentru gestionarea grupurilor de butoane radio se va folosi clasa
ButtonGroup, respectiv metoda add() care adauga un buton la grup.

Si pentru butoanele radio se pot apela metodele setSelected(boolen marcat) pentru a stabili
marcajul prin program, respectiv getSelected() pentru a afla starea marcajului.

// Create the radio buttons.

JRadioButton birdButton = new JRadioButton(“Pasare”);
[Link](KeyEvent.VK_B);
[Link](“Pasare”);
[Link](true);
JRadioButton catButton = new JRadioButton(“Pisica”);
[Link](KeyEvent.VK_C);
[Link](“Pisica”);
…
// Group the radio buttons.
ButtonGroup group = new ButtonGroup();
[Link](birdButton);
[Link](catButton);
…
// Put the radio buttons in a column in a panel
JPanel radioPanel = new JPanel();
[Link](new GridLayout(0, 1));
[Link](birdButton);
[Link](catButton);

[Link]. ListBox

ListBox-urile afiseaza liste de optiuni. Ele se compun dintr-un element care se ocupa de
vizualizare (derivat din clasa JList), respectiv dintr-un element care se ocupa cu gestionarea
continutului (derivat din ListModel).

Interfata ListModel pune la dispozitie o metoda addElement() care permite adaugarea unei
noi optiuni in lista.

Constructorul clasei JList primeste un obiect de tip ListModel pe care il va afisa pe ecran.
Pentru a avea la dispozitie bare de derulare asociate listei, aceasta va trebui inclusa intr-un
element de tip JScrollPane (un panou derulant).

67
Aditional listelor simple se pot defini si liste cu derulare (de tip ComboBox). Acestea afiseaza in
mod obisnuit o singura optiune din lista iar pentru a accesa restul optinulor lista trebuie derulata
de la un buton special. Listele derulante nu trebuie adaugate intr-un JScrollPane.

ListModel listModel = new DefaultListModel();

[Link](“Linie1");
…
JList list = new JList(listModel);
[Link](ListSelectionModel.SINGLE_SELECTION);
[Link](0);
JScrollPane listScrollPane = new JScrollPane(list);
--------
String[] culori = { "Alb", "Negru", "Rosu", "Verde",
"Albastru" };
JComboBox listaCulori = new JComboBox(culori);
[Link](1); // selecteaza elementul 2
(Negru)
[Link](true);

4.4. Reprezentarea aplicaţiei

Interfaţa utilizator grafica (engl.: GUI - Graphical User Interface) permite utilizatorului sa
comunice cu aplicaţia, folosind in acest scop obiecte grafice de pe ecran: ferestre, butoane, casete
de validare, meniuri etc. Acţionarea asupra acestora se face folosind tastatura sau dispozitive de
intrare speciale, dintre care cel mai raspandit este mouse-ul.
În JDK exista pachete de clase care permit realizarea de interfeţe grafice, unul dintre acestea fiind
[Link]. Initialele AWT provin de la Abstract Window Toolkit - set de dezvoltare de ferestre
abstracte. Acest set permite realizarea de interfeţe grafice care nu depind de platforma pe care
ruleaza aplicaţia. El ofera programatorului clase de componente organizate sub forma unei
ierarhii care are ca radacina clasa Component.

Folosirea interfeţelor grafice implica si o abordare specială in programare, numita programare

orientată pe evenimente (engl: Event Oriented Programming) sau programare ghidata de
evenimente (engl.: Event Driven Programming). În aceasta conceptie, obiectele din program pot
fi surse de evenimente sau consumatoare ("ascultatoare") de evenimente (eng.: Event Listeners).
Evenimentele inseşi sunt obiecte (instante ale unor clase de evenimente ) generate de surse si
interceptate de consumatori. Clasele consumatoare de evenimente sunt cele care conţin metodele
prin care aplicaţia reactionează la evenimentele respective.

68
Se disting evenimente de nivel inferior (cele generate de diferite componente) si evenimente
abstracte (care reprezinta diferite evenimente conceptuale, independente de componenta care le-a
generat). Fiecarei clase de evenimente ii corespunde o interfata pe care trebuie sa o implementeze
clasele concepute de programator, care interceptepteaza si trateaza evenimentele respective.
Interfetele sunt, de asemenea organizate intr-o ierarhie, similara celei a claselor. Pentru unele
interfete s-au realizat si clase-prototip care le implementeaza, numite adaptoare. Clasele de
evenimente, interfetele si adaptoarele se gasesc in pachetul [Link].

Clasa Graphics
In pachetul [Link] este definita clasa abstracta Graphics, care este clasa de baza a tuturor
contextelor grafice care permit trasarea de desene pe suprafata componentelor grafice realizate pe
diverse dispozitive fizice.
Un obiect din clasa Graphics incapsuleaza informatia de stare a contextului grafic la care se
refera si anume:
- obiectul din clasa Component (sau dintr-o subclasa a acesteia) pe care se deseneaza;
- o translatie a originii sistemului de coordonate; toate coordonatele din desen sunt raportate la
aceasta origine;
- decupajul curent (dreptunghiul in interiorul caruia se traseaza desenul);
- culoarea curenta; - fontul curent;
- operatia logica pe pixeli curenta (XOR sau paint);
- alternarea curenta de culori pentru operatia pe pixeli XOR.

Clasa interfata_grafica face desenarea interfetei grafice:

public class interfata_grafica
{
Font f = new Font("", [Link], 30);

Ascultadecomenzi trateaza=new Ascultadecomenzi();

Frame frame=new Frame("Aplicatie");

MenuBar mb=new MenuBar();

Menu m1=new Menu("Comenzi");

menuiesire m1B1=new menuiesire("Iesire");

69
 butoniesire b3 = new butoniesire("Iesire");
butonulmeu b4 = new butonulmeu("Calculeaza",this);
setbuton actiune_b5 = new setbuton("Set");
butonopriere b6= new butonopriere("Oprire cautare");

JTextField status = new JTextField("", 5);

JLabel untext =new JLabel("Status");

JLabel untext1 =new JLabel("Plecare: ");

JLabel untext2 =new JLabel("Destinatie: ");

JLabel actiune_untext1 =new JLabel("Plecare: ");

JLabel actiune_untext2 =new JLabel("Destinatie: ");
JLabel actiune_untext3 =new JLabel("Actiuni: ");
JLabel actiune_untext4 =new JLabel("Valoare: ");

JTextField actiune_val = new JTextField(4);

JRadioButton optiunea1 = new JRadioButton("Stergere");

JRadioButton optiunea2 = new JRadioButton("Setare lungime");
ButtonGroup group = new ButtonGroup();

JPanel panel=new JPanel();

Retea retea;

final int x=10,y=20;

Choice plecare = new Choice();

Choice destinatie = new Choice();

Choice actiune_plecare = new Choice();

Choice actiune_destinatie = new Choice();

Thread a;

TextArea rezultate = new TextArea();

interfata_grafica()
{

Clasa [Link] contine metoda main. Aici se fac 2 thread-uri, unul pentru interfata
grafica si unul care deseneaza odata la 100 ms graful curent, in functie de configuratia retelei:

public class principal {

static interfata_grafica a;

static class Fir_grafica extends Thread

{
Fir_grafica()
{

70
 a = new interfata_grafica ();
}

public void run()

{
yield();
}
}

static class Desenare_drum extends Thread

{
int i,j,x1,x2,y1,y2,m,n;
Font f1 = new Font("", [Link], 20);
Font f2 = new Font("", [Link], 18);

Desenare_drum()
{

public void run()

{

try
{
[Link](200);
yield();

Pentru modelarea retelei s-au folosit clasele retea, nod, linie.

Clasa [Link] are campuri datele despre respectivul nod (nume, coordonate, legaturi cu alte
nod-uri) si metodele care permit sa se faca/stearga legatura cu alte noduri.
public class Nod {

String nume;
Linie legatura[] = new Linie[15];
int nr_legaturi=0;
int x,y;
interfata_grafica interfata;

Nod(String nume, int x, int y, interfata_grafica interfata)

{
[Link]=nume;
this.x=x;
this.y=y;

[Link]=interfata;
}

public void setLegatura(Nod destinatie, int lungime)

{

71
 legatura[nr_legaturi]=new Linie(this,destinatie,lungime,
interfata);
nr_legaturi++;

[Link](this, lungime); //seteaza si

distanta inversa
}

public void setLegaturaReverse(Nod destinatie, int lungime)

{
legatura[nr_legaturi]=new Linie(this,destinatie,lungime,
interfata);
nr_legaturi++;
}

Clasa [Link] se face configurarea retelei folosind figura:

Fig.4
public class Retea {
interfata_grafica interfata;
Nod nod[] = new Nod[20];
int lungime=16;
Retea(interfata_grafica interfata)
{
nod[0]=galati;
nod[1]=bucuresti;
nod[2]=tulcea;
nod[3]=constanta;

72
 nod[4]=iasi;
nod[5]=craiova;
nod[6]=pitesti;
nod[7]=brasov;
nod[8]=piatra_neamt;
nod[9]=cluj;
nod[10]=timisoara;
nod[11]=oradea;
nod[12]=baia_mare;
nod[13]=suceava;
nod[14]=orsova;
nod[15]=bacau;

}
} [Link]=interfata;

Clasa [Link] stabileşte sursa, destinaţia şi lungimea drumului:

public class Linie {
int lungime;
Nod sursa, destinatie;

interfata_grafica interfata;

Linie(Nod sursa, Nod destinatie, int lungime, interfata_grafica

ref)
{
[Link]=sursa;
[Link]=destinatie;
[Link]=lungime;

Clasa [Link] face calcularea drumului. Fiecare instanta catre aceasta clasa ruleaza
pentru un thread separat pentru a nu se intepa interfata grafica cand se face calculul drumului.
Algoritmul de cautare este unul recursiv, se merge din nod in nod si la fiecare nod se cauta
vecinii. Se stocheaza intr-un vector nod-urile vizitate pentru a nu se merge de două ori prin
acelasi nod (fig.5).

public class calculare extends Thread

{
interfata_grafica interfata;
Nod drum[] = new Nod[50];
int gasite=0;
Nod vector[][] = new Nod[400][50];
int vector_lungime[] = new int[400];
int indexi[] = new int[400];
boolean gasit=true;
int temp;
Nod p; Nod d;

calculare(interfata_grafica interfata, Nod p, Nod d)

73
 {
[Link]=interfata;
this.p=p;
this.d=d;
}

public void cauta_in_vecini(Nod nod, Nod plecare, Nod destinatie,

int lungime, int pas)
{

74
 Fig.5 Calcularea drumului minim

Concluzii
Principalele probleme tratate în lucrare:
 Utilizarea structurilor de date şi al algoritmilor în programarea
la calculator
 Grafuri, arbori - traversări, parcurgeri
 Crearea unei interfeţe grafice
 Calcularea unui drum minim
Această lucrare reprezintă ceea ce avem nevoie să ştim “după”ce am învăţat un
limbaj de programare.
Scopul esenţial al lucrării a fost de a face toate subiectele expuse, uşor de înţeles.
Lucrarea prezentată este ilustrată cu ajutorul unor programe demonstrative
reprezentate pas cu pas ,cu “imagini în mişcare”, principiile de bază ale funcţionării
structurilor de date.

75
 BIBLIOGRAFIE
1. Athanasiu Irina, Costinescu B., Drăgoi O.A., Popovici F.I.  Limbajul Java. O perspectivă
pragmatică. Editura Agora, [Link]ş

2. Fraizer C., Bond J.  Java API. Pachetele API [Link] si java awt. Editura Teora, Bucureşti,
1998. .3. Rotariu E.  Limbajul Java.  Editura Agora, [Link]ş, 1996.

3. Norton P., Stanek W. Ghid de programare in Java.  Editura Teora, Bucureşti, 1997

4. Prodan A., Prodan M.  Mediul Java pentru Internet. Editura Promedia Plus, Cluj-Napoca,
1997.

5. Rotariu E.  Limbajul Java.  Editura Agora, [Link]ş, 1996.

SURSE INTERNET

[Link]
html[Link]
[Link]

[Link]

[Link]

[Link]

76
77