FUNDAȚIA PENTRU CULTURĂ ȘI ÎNVĂȚĂMÂNT IOAN SLAVICI [626139]

1
FUNDAȚIA PENTRU CULTURĂ ȘI ÎNVĂȚĂMÂNT “IOAN SLAVICI”
TIMIȘOARA
UNIVERSITATEA “IOAN SLAVICI” TIMIȘOARA
FACULTATEA DE INGINERIE
DOMENIUL CALCULATOARE ȘI TEHNOLOGIA INFORMAȚIEI
FORMA DE ÎNVĂȚĂMÂNT – ZI

PROIECT DE DIPLOMĂ

COORDONATOR ȘTIINȚIFIC
Prof. Univ. Dr. TITUS SLAVICI

ABSOLVENT: [anonimizat]
2018

2
FUNDAȚIA PENTRU CULTURĂ ȘI ÎNVĂȚĂMÂNT “IOAN SLAVICI”
TIMIȘOARA
UNIVERSITATEA “IOAN SLAVICI” TIMIȘOARA
FACULTATEA DE INGINERIE
DOMENIUL CALCULATOARE ȘI TEHNOLOGIA INFORMAȚIEI
FORMA DE ÎNVĂȚĂMÂNT – ZI

GRAFURI PONDERATE

COORDONATOR ȘTIINȚIFIC
Prof. Univ. Dr. TITUS SLAVICI

ABSOLVENT: [anonimizat]
2018

3
Cuprins

I.Grafuri. Reprezentări . ………………………….. ………………………….. ………………………….. ……………………… 4

1.1 Ce este un graf? Considerații general e ………………………….. ………………………….. …………………….. 4

1.2 Definiții și reprezentare grafic ă ………………………….. ………………………….. ………………………….. ….. 4

1.3 Grafuri orientat e ………………………….. ………………………….. ………………………….. ………………………. 6

1.4 Grafuri neorientat e ………………………….. ………………………….. ………………………….. ……………………. 9

1.5 Tipuri speciale de grafur i ………………………….. ………………………….. ………………………….. …………. 17

1.6 Tehnici de implementare a grafurilo r ………………………….. ………………………….. …………………….. 19

1.6.1 Implementarea grafurilor prin matrice de adiacenț ă ………………………….. ……………………….. 19

1.6.2 Implementarea grafurilor prin sturcturi de adiacenț ă ………………………….. ………………………. .20

II. Algoritmi de drum mini m ………………………….. ………………………….. ………………………….. …………….. 26

2.1 Prezentare general ă ………………………….. ………………………….. ………………………….. …………………. 26

2.2 Algoritmul lui Dijkstr a ………………………….. ………………………….. ………………………….. ……………. 28

2.3 Algoritmul lui Bellman -Ford ………………………….. ………………………….. ………………………….. ……. 31

2.4 Algoritmul lui Floyd -Warshal l ………………………….. ………………………….. ………………………….. …. .32

III. Prezentarea aplicației Graph G ………………………….. ………………………….. ………………………….. ………. 34

3.1. Prezentare general ă ………………………….. ………………………….. ………………………….. ………………… 34

3.2. Utilizarea practică a aplicație i ………………………….. ………………………….. ………………………….. …. 35

3.3 Implementarea aplicație i………………………….. ………………………….. ………………………….. ………….. 37

Concluzii : ………………………….. ………………………….. ………………………….. ………………………….. …………… 42

Bibliografie: ………………………….. ………………………….. ………………………….. ………………………….. ……….. 43

4

CAPITOLUL I
Grafuri. Reprezentări.

1.1 Ce este un graf? Considerații generale

Graful este un model abstract (matematic) pentru multe probleme reale,
concrete, a cãror rezolvare necesitã folosirea unui calculator. În matematicã un
graf este definit ca o pereche de douã mulțimi G = (V,M), unde V este
mulțime a (nevidã) a vârfurilor (nodurilor), iar M este mulțimea muchiilor
(arcelor).
Să presupunem că avem o reațea intranet a unei firme. Fiecare componentă a
rețelei reprezintă un nod al unui graf neorientat cu n vârfuri, iar legăturile din
acestea repr ezintă muchiile grafului, sau rețeaua de străzi a unui oraș, străzile
sunt arcele î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 pi etonilor, „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.

Un alt exemp lu traseele aeriene, se cere să se precizeze drumul optim dintre
două state, cel mai optim drum trebuie să respecte un anumit criteriu din puncte
de vedere al prețului al timpului și al accesibilității. Pentru rezolvarea acestor
tip de probleme sunt necesa re interconexiunile dintre obiecte care pot fi
reprezentate într -un calculator sub forma unor grafuri.

1.2 Definiții și reprezentare grafică

Deci numim graf o pereche ordonată de mulțimi, notată G=(X,U), unde X este
o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar U este o
mulțime de perechi (ordonate sau neordonate) de elemente din X numite muchii
(dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). Fiecare
arc dintr -un graf este specificat de o pereche de noduri, mu lțimea nodurilor este
{1, 2, 3, 4, 5, 6, 7,} iar mulțimea arcelor este {(1,2), (2,4), (2,5), (3,7), (4,5)}.

5
Traseele dintre noduri reprezintă arcele. Vârfurile săgeților reprezintă al doilea
nod sau destinația și celălalt capăt al arcului reprezita primul nod într o pereche
de noduri.

Figura. 1.1 Exemplu de graf

Termenii “vârf” și “muchie” provin din analogia unui graf cu un poliedru și
se folosesc mai ales pentru grafuri neorientate. termenii “nod” și “arc” se
folosesc mai ales pentru grafuri orien tate.
Într-un graf orientat, numit și digraf, arcul (v,w) pleacã din nodul v și intrã în
nodul w; el este diferit de arcul (w,v) care pleacã de la w la v. Într -un graf
neorientat poate exista o singurã muchie între douã vârfuri date, notatã (v,w)
sau (w,v) . cel mult douã arce, iar între douã vârfuri ale un graf neorientat poate
exista cel mult o muchie.
Cu ajutorul unui graf neorientat putem modela o relație simetrică între
elementele unei mulțimi, în timp ce cu ajutorul unui graf orientat modelăm o
relație care nu este simetrică.
Între oricare două vârfuri ale unui graf poate exista cel mult o muchie/arc. Dacă
între două vârfuri există mai multe muchii/arce atunci structura se numește
multigraf. Nu vom lucra cu structuri multigraf.
În practică, informațiile asociate unui graf pot fi oricât de complexe, dar, pentru
a simplifica, vom considera că vârfurile grafului sunt etichetate cu numere
naturale de la 1 la n (unde cu n vom nota numărul de vârfuri din graf). Această
numerotare nu este o restrân gere a generalității (de exemplu, numărul vârfului
poate fi considerat poziția pe care sunt memorate într -un vector informațiile
asociate vârfului).

6
Figura 1.2 Graf neorientat

Figura 1.3 Graf orientat

1.3 Grafuri orientate

Un graf G este conex, dacă oricare ar fi două vârfuri ale sale, exista un lanț care
le leagă.

Un lanț într -un graf orientat este un șir de arce {u1, u 2, u3 , …, un} cu
proprietatea că oricare două arce consecutive au o extremitate comună. Altfel
spus, un la nț este un traseu care unește prin arce două noduri numite
extremitățile lanțului, fără a ține cont de orientarea arcelor componente.

7

Figura 1.4 Graf conex

Graful este conex pentru că oricum am lua două noduri putem ajunge de la
unul la celălalt pe un traseu de tip lanț. De exemplu, de la nodul 4 la nodul 2
putem ajunge pe traseul de noduri (4,3,2) stabilind astfel lanțul {u5, u3}, dar și
pe traseul de noduri (4,1,2) stabilind lanțul {u6, u2}

Figura 1.5 Grafuri asemănătoare dar care nu sunt conex

Exemplul din figura 1.5 nu este un graf conex deoarece: luând submulțimea
de noduri {1,2,3}, putem spune că între oricare două noduri din această
submulțime exista cel puțin un lanț., de exemplu lanțul {u1, u2} sau {u3, u1}.
La fel stau lucrurile cu submul țimea de noduri {4,5,6}. Dar nu ptuem găsi un
lanț intre un nod din prima submulțime și un nod din a doua submulțime.

8

Plecând dintr -un nod al primei submulțimi și deplasându -ne pe arce, nu
avem cum să trecem în a doua submulțime pentru că nu exista nici u n arc direct
care să lege cele două submulțimi. De exemplu plecând din nodul 1 putem
ajunge în nodul 2 pe traseul {u3, u2}, dar de aici nu putem ajunge mai departe
în nodul 4, deci nu exista lanț de la 2 la 4.

Componenta conexa a unui graf G=(X, U), repre zintă un subgraf G1=(X1,
U1) conex, a lui G, cu proprietatea că nu exista nici un lanț care să lege un nod
din X 1 cu un nod din X -X 1 (pentru orice nod, nu există un lanț între acel nod
și nodurile care nu fac parte din subgraf).

De exemplu graful din figura 1.5 nu este conex , însă în el distingem două
componente conexe: G1 =(X1, U1), unde X1={1,2,3} și U1={u1, u2, u3}; și
G2=(X2, U2), unde X2={4,5,6} și U2={u4, u5}.

Graful tare conex este un graf orientat G=(X, U), dacă pentru oricare două
noduri x și y aparțin lui X, exista un drum de la x la y precum și un drum de la
y la x.Exemplu Graful cu n=3 din fig. 4 este tare conex.

Figura. 1.6 Graf tare convex

Pentru a demonstra acest lucru, formăm toate perechile posibile de noduri
distincte (x, y) cu x, y aparțin mulțimii {1,2,3}, și pentru fiecare astfel de
pereche căutam un drum de la x la y și un drum de la y la x.

9
x=1, y=2
De la 1 la 2 – drumul [1,3,2], pe arcele (1,3) și (3,2); De la 2 la 1 – drumul
[2,3,1], pe arcele (2,3) și (3,1).
x=1, y= 3
De la 1 la 3 – drumul [1,2,3], pe arcele (1,2) și (2,3); De la 3 la 1 – drumul
[3,2,1], pe arcele (3,2) și (2,1).
x=2, y=3
De la 2 la 3 – drumul [2,1,3], pe arcele (2,1) și (1,3); De la 3 la 2 – drumul
[3,1,2], pe arcele (3,1) și (1,2).

Componenta tar e conexa.

Un subgraf se obține dintr -un graf G= (X, U) eliminând niște vârfuri și
păstrând doar acele muchii care au ambele extremități în mulțimea vârfurilor
rămase.

Fie un subgraf tare conex G1=( X1, U1) al grafului G=(X, U). Adăugăm la
subgraf un nod x care nu face parte din mulțimea nodurilor sale (x aparține X –
X1). Obținem astfel mulțimea de vârfuri X1 reunit cu {x}. Subgraful indus pe
mulțimea X1 reunit cu {x} se obține luând și arcele care tre c prin nodul x.Dacă
acest subgrafnu mai este tare conex, atunci el se numește componenta tare
conexa.

Figura 1.7/1.8 Graf tare conex

10
Graful cu n=3 din fig. 1.7 este tare conex dar observăm că prin eliminarea
nodului 4 obținem subgraful tare conex G1=(X1, U1).

Acestui graf îi adăugăm un nod x care nu face parte din mulțimea nodurilor
subgrafului G1, graful obținut este componenta tare conexa.

1.4 Grafuri neorientate

Graful reprezintă orice mulțime finită V prevăzută cu o relație binară internă
E. Notăm graful cu G=(V, E) iar graful neorinentat este graful G=(V, E) în care
relația binară este simetrică (v,w)
E atunci (w,v)
E. Nodul este un element
al mulțimii V, iar muchia element al mulțimii E ce descrie o relație existentă
între două vârfuri din V, unde G=(V, E) este un graf neorientat. Exemplu în
figură 1.9, V={1,2,3,4,5,6} sunt noduri, E={[1,2], [1,4], [2,3],[3,4],[3,5]}
sunt muchii, E={[1,2], [1,4],
[2,3],[3,4],[3,5]} sunt muchii

Figura 1.9 Graf neori entat

Într-un graf neorientat existența muchiei (v,w) presupune că w este adiacent
cu v și v adiacent cu w, aceasta o numim adiacentă. În exemplul din figură de

11
mai sus vârful 1 este adiacent cu 4 dar 1 și 3 nu reprezintă o pereche de vârfuri
adiacente.

O muchie este incidentă cu un nod dacă îl are pe acesta ca extremitate.
Muchia (v,w) este incidentă în nodul v respectiv w,.

Gradul unui nod v, dintr -un graf neorientat, este un număr natural ce
reprezintă numărul de noduri adiacente cu acesta (sau număru l de muchii
incidente cu nodul respectiv), un nod cu gradul 0 se numezte nod izolat iar un
nod cu gradul 1 se numește terminal. În Graful din figura 1.10 nodul 5 este
terminal de gradul 1, nodul 6 este izolat (gradul 0), nodurile 1, 2, 4 au gradele
egale c u 2.

Figura 1.10

Numim lanț o secvență de noduri ale unui graf neorientat G=(V,E), cu
proprietatea că oricare două noduri consecutive din lanț sunt adiacente,
L=[w1, w2, w3,… ,wn] cu proprietatea că (wi, wi+1)
E pentru 1
i<n, iar
numărul de muchii din care este format reprezintă lungimea lanțului.

Lanțurile pot fi de 3 tipuri: lanțul simplu este lanțul care conține numai
muchii distincte, lanțul compus este opus lanțulului simplu și nu este format
numai din muchii distincte și lanțul elemen tar care conține numai noduri
distincte.

Un ciclu este un lanț care de cel puțin un nod, care începe și se sfârșește cu
același nod și care are toate arcele distinct.Ciclul este elementar dacă este
format doar din noduri distincte, excepție făcând primul și ultimul. Lungimea
unui ciclu nu poate fi 2.

12

Exemplu în figură 1.11 Sccesiunea de vârfuri 2, 3, 5, 6 reprezintă un lanț
simplu și elementar de lungime 3, lanțul 5 3 4 5 6 este simplu dar nu este
elementar, lanțul 5 3 4 5 3 2 este compus și nu este eleme ntar și lanțul 3 4 5 3
reprezintă un ciclu elementar.

Figura 1.11

Dacă dintr -un graf G=(V,E) se suprimă cel puțin o muchie atunci noul graf
G‟=(V,E‟), E‟
E se numește graf parțial al lui G.

13

Figura 1.12 G Figura 1.13 G1 este graf parțial al lui G

Dacă dintr -un graf G=(V,E) se suprimă cel puțin un nod împreună cu
muchiile incidente lui, atunci noul graf G‟=(V‟,E‟), E‟
E și V‟
V se
numește subgraf al lui G, figurile 1.14 și 1.15.

14

Figura. 1.14 Figura. 1.15 G1 este graf parțial al lui G

Graful neorientat în care toate nodurile au același grad se numește graf
regulat.

Figura. 1.16 Graf regulat
Un graf neorientat G=(V,E) în care există muchie între oricare două noduri
se numește graf complet numărul de muchii ale unui graf complet este: nr*(nr –
1)/2, unde nr este numărul de noduri.

15

Figura 1.17 Graf complet

Un graf se numește conex dacă de la fiecare nod al său există un drum spre
oricare alt nod al grafului, respectiv dacă oricare pereche de noduri aparținând
grafului este conectată

Figura 1.18 Graf conex Figura 1.19 Nu este graf conex

Componentă conexă est e un subgraf al grafului de referință, maximal în
raport cu proprietatea de conexitate (între oricare două vârfuri există lanț);

16
Lanț hamiltonian este un lanț elementar care conține toate nodurile unui
graf. De exemplu în figură de mai jos L=[2 ,1, 6, 5, 4, 3] este lanț hamiltonian.

Figura 1.20 Lanț Hamiltonian

Un ciclu hamiltonian este un ciclu elementar care conține toate nodurile
grafului, cu alte cuvinte este un ciclu elementar de lungime n=card(V) într -un
graf G=(V, E).În exemplu de mai jos C=[1,2,3,4,5,6,1] este ciclu hamiltonian

Figura 1.21 Ciclu Hamiltonian

17
Un graf G este un graf hamiltonian care conține un ciclu hamiltonian

Fie un graf G=(V,E). Se numește un ciclu eulerian un ciclu simplu care
conține toate muchiile grafulu i. Un graf care conține un ciclu eulerian se
numește graf eulerian

Figura 1.21 Graf eulerian

În figură 1.21 lanțul: L=[1.2.3.4. 5.3.6.2.5.6] este lanț eulerian iar ciclul:
C=[1.2.3.4.5.3.6.2.5.6.1] este ciclu eulerian. Este suficientă o singură
condiție pentru a fi un graf eulerian: dacă și numai dacă oricare vârf al său are
gradul par.

1.5 Tipuri speciale de grafuri

Definiție: Se numește graf complet cu n vârfuri un graf G=(X,U) cu
proprietatea că oricare două vârfuri sunt adia cente adică x ,y X muchia [x,y]U

18

Figura 1.22 Graf complet

Un graf orientat se numește antisimetric dacă pentru oricare două vârfuri din
graf x și y dacă există arcul ,(x,y) atunci nu există arcul (y,x).
Observație: Orice relație de ordine între elementele unei mulțimi poate fi
modelată cu ajutorul unui graf orientat asimetric (vârfurile grafului corespund
elementelor mulțimii; dacă elementul x este în relația de ordine respectivă cu
elementul y, atunci în graf va exista arcul (x,y), graful astfel definit este
antisimetric, deoarece relația de ordine este antisimetrică). Un graf orientat
complet și antis imetric se numește graf turneu.

Un graf neorientat G=(V,E) se numește bipartit dacă mulțimea
vârfurilor sale poate fi partiționată în două submulțim i A și B nevide astfel
încât orice muchie are o extremitate în A și una în B. Un graf bipartit poate fi și
un graf bipartite complet dacă fiecare vârf din mulțimea A este adiacent cu
fiecare vârf din mulțimea B.

Figura 1.23 Graf neorientat bipartit e Figura 1.24. Graf neorientat bipartit complet

19
1.6 Tehnici de implementare a grafurilor

Pentru a prelucra grafurile,cu ajutorul unui calculator, este necesar
dezvoltarea unor tehnici de implementare a acestora în scopul de prelucrare,
vizualizare grafică și redare a tipului de graf. În continuare sunt prezentate mai
multe posibilități de implementare a unui tip de date ab stract, în funcție de
natura grafului de implementat, și a operațiilor care se execută asupra lor

1.6.1 Implementarea grafurilor prin matrice de adiacență

Reprezentarea cea mai directã a unui graf este printr -o matrice de adiacente
(de vecinătăți), pe ntru grafuri de relație respectiv printr -o matrice de costuri,
pentru rețele. Avantajele reprezentãrii unui graf printr -o matrice sunt:
simplitatea și claritatea programelor, aceeași reprezentare pentru grafuri
orientate și neorientate, cu sau fãrã costuri, se pot obține ușor și repede
succesorii sau predecesorii unui nod dat v (coloanele nenule din linia v sunt
succesorii, iar liniile nenule din coloana v sunt predecesorii). Timp constant
pentru verificarea existenței unui arc înt re douã noduri date (nu necesitã
cãutare, deci nu depinde de dimensiunea grafului).
Reprezentarea matricialã este preferatã în determinarea drumurilor dintre
oricare douã vârfuri (tot sub formã de matrice), în determinarea drumurilor
minime dintre ori care douã vârfuri dintr -un graf cu costuri, în determinarea
componentelor conexe ale unui graf orientat (prin transpunerea matricei se
obține graful cu arce inversate, numit și graf dual al grafului inițial), și în alte
aplicații cu grafuri.
O matrice este o re prezentare naturalã pentru o colecție de puncte cu atribute
diferite: un labirint (puncte accesibile și puncte inaccesibile), o suprafață cu
puncte de diferite înălțimi, o imagine formatã din puncte albe și negre (sau
colorate diferit), s.a.
Dezavantajul m atricei de adiacente apare atunci când numãrul de noduri din
graf este mult mai mare că numãrul de arce, iar matricea este rarã ( cu peste
jumãtate din elemente nule). În astfel de cazuri se preferã reprezentarea prin
liste de adiacente.
Matricea de adiace nte "a" este o matrice pãtraticã cu valori întregi , având
numãrul de linii și de coloane egal cu numãrul de noduri din graf. Elementele
a[i][j] sunt:

20
1 (true) dacã existã arc de la i la j sau 0 (false) dacã nu existã arc de la i la j
Exemplu de definire a unui tip graf printr -o matrice de adiacente alocatã
dinamic:

// cu matrice alocată dinamic
typedef struct {
int n,m ; // n=nr de noduri, m=nr de arce
int ** a; // adresa matrice de adiacente
} Graf ;

Succesorii unui nod dat v sunt elementele nenule din linia v , iar predecesorii
unui nod v sunt elementele nenule din coloana v. De obicei nu existã arce de la
un nod la el însuși și deci a[i][i]=0. Exemple de funcții cu grafuri în cazul
utilizãrii matrice i de adiacente.

void initG (Graf & g, int n) { // inițializare graf
int i;
g.n=n; g.m=0;
g.a=(int**) malloc( (n+1)*sizeof(int*)); // vârfuri numerotate 1..n
for (i=1;i<=n;i++)
g.a[i]= (int*) calloc( (n+1),sizeof(int)); // linia 0 și col. 0 nefolosite
}
void addArc (Graf & g, int x,int y) { // adauga arcul (x,y) la g
g.a[x][y]=1; g.m++;
}
int arc (Graf & g, int x, int y) { // dacă există arcul (x,y) în g
return g.a[x][y];
}

I.6.2 Implementarea grafurilor prin sturcturi de adiacență

O altă manieră de reprezentare a unui TDA graf o constituie structurile de
adiacență ( adjacency structures). În cadrul acestei reprezentări, fiecărui nod al
grafului i se asociază o listă de adiacente în care sunt înlănțuite toate nodurile
cu care acesta este conectat.

În continuare se prezintă două metode pentru implementarea grafurilor cu
ajutorul structurilor de adiacente. Prima metodă. Implementarea structurii de
adiacente se bazează în acest caz pe liste simplu înlănțuite. Listele sunt

21
construite în maniera obișnuită, cu un nod fictiv z pe post de fanion,a cărui
înlănțuire indica nodul însuși.

Începuturile listelor de adiacente sunt păstrate într -un tablou “Stradi“ indexat
prin inte rmediul nodurilor. Inițial în acest tablou se introduc înlănțuirile la
nodurile fictive, urmând ca inserțiile în liste să fie “la începutul listei”.
Adăugarea unui arc care conectează nodul x cu nodul y în cazul acestui mod de
reprezentare presupune în caz ul grafurilor neorientate inserția nodului x în lista
de adiacente a lui y și inserția lui y în lista de adiacente a nodului x. Un
exemplu de program care construiește o astfel de structura apare în secvența de
mai jos:

Program StructuraDeAdiacente:

#define maxN 100
Typedef struct nod;
Typedef nod *ref;

Int j,x,y,N,A;
Ref v,z;
Ref stradi[maxN];

Char n1,n2;

Int index(char c) ;
void main()
}

Se observa că un arc oarecare (x,y) este evidențiat în două locuri în cadrul
structurii (atât în lista d e adiacente a lui x, cât și în lista de adiacente a lui y ).
Acest mod redundant de evidențiere își dovedește utilitatea în situația în care se
cere să se determine într -o manieră eficienta care sunt nodurile conectate de un
anumit nod x.

Pentru acest mod de reprezentare contează ordinea în care sunt prezentate
arcele (perechile de noduri) la intrare. Astfel, un același graf poate fi reprezentat
ca structură de adiacente în moduri diferite. Ordinea în care apar arcele în lista
de adiacente afectează la rândul ei ordinea în care arcele sunt prelucrate de către
algoritm. În funcție de natura algoritmilor utilizați în prelucrare, această
ordine poate să influențeze sau nu rezultatul prelucrării.

22
Această metodă necesita ca fiecare nod alocat să conțină un număr variabil
de pointeri,depinzând de numărul de noduri cu care este adiacent.În figură 1.26
apare reprezentarea grafică a structurii construite pornind de la graful din
figura 1.25. Datele de intrare (arcele) au fost furnizate în următoarea
ordine:(A,G), (A,B), (A,C), (J,K), (H,J), (H,I), (E,D), (F,D), (L,M), (F,E),
(A,F), (G,E).

Figura. 1.25

Figura 1.26 Reprezentarea înlănțuită(Metoda I)

23
A doua metodă de implementare a structurilor de adiacente se bazează
pe structuri multiinlantuite. Astfel, o structură de adiacente este de fapt o listă
înlănțuita a nodurilor grafului. Pentru fiecare nod al acestei liste se păstrează o
listă a arcelo r, respectiv, o listă înlănțuita a cheilor nodurilor adiacente. În
consecință, fiecare nod al listei nodurilor va conține două înlănțuiri, una
indicând nodul următor,cealaltă, lista nodurilor adiacente. În figură 2.7 apare
reprezentarea schematică a unei structuri de adiacente:

Fig. 1.27 Reprezentarea schematică a unei structuri de adiacente

Secventa “C” care implementează structura multilista este următoarea:
Typedef int TipCheie:
Typedef int TipInfo;
Typedef struct
TipElement;
Typedef struct
Adiacente

Typedef Adiacente padi:
Typedef struct nod;
Typedef pnod *nod;
Typedef graf pnod;
Typedef struct TipArc;
Graf g;

Pnod indiceNod;
TipArc indiceArc;
TipCheie k,k1,k2;
TipElement E;

24
Se face precizarea ca valorile aferente nodurilor sunt păstrate integral în lista
de noduri. În lista de arce apar numai cheile. Desigur este posibil să lipsească
câmpul “inf o” și deci TipElement=TipCheie.

În cadrul acestei structuri localizarea unui nod a cărui cheie este cunoscută
se face utilizând tehnica căutării liniar.Inserția unui nod se va realiza simplu,la
începutul listei nodurilor. Procedura InserArc(g,k1,k2) presupune inserția lui k1
în lista de adiacente a lui k2 și reciproc.Și în acest caz inserția se realizeza cel
mai simplu la începutul listei .
Suprimarea arcului precizat de indiceArc presupune extragerea a două
noduri din două liste de adiacente diferite.Astfel,în figură 2.3, indiceArc
conține doi pointeri v1 și v2, care indica două noduri în lista de noduri. În
vederea suprimării arcului care le conectează este necesar ca fiecare nod în
parte să fie suprimat din lista de adiacente a celuilalt. În cazul ilustrat, pentru a
suprima arcul (A,C)=(C,A) se scoate A din lista lui C, respectiv C din lista lui
A.
Procedura care realizează suprimarea arc ului este următoarea:

void SuprimaArc(graf*g, TipArc indiceArc);

padi ik1,ik2;

Else printf(„Arcul nu există.‟);
}; /* SuprimArc */

Funcția Cauta și procedura Suprima au fost realizate în termenii setului de
operatori aplicabili obiectelor de tip lista. Caută(X,L) cauta nodul cu cheia X în
lista de adiacente cu începutul listei precizat de variabilă pointer L și returnează
adresa nodului cu cheia X din această listă.Dacă X nu apare deloc returnează
pointerul nul:
Padi Cauta(TipCheie X;PointAdi *L) ;
/* Cauta */

25
Procedura Suprimă(AX,LY) suprima nodul X de adresa AX, determinată prin
procedura Cauta (prin căutarea nodului X în lista de adiacente a nodului Y), din
lista de adiacente a nodului Y (cu începutul marcat de variabilă pointer LY).

Observație: Apelul funcției se face din funcția SuprimArc numai în cazul în
care arcul exista.
void Suprimă(padi AX;padi *LY);
} /* Suprima */

Suprimarea unui nod dintr -o structură de tip graf presupune nu numai
suprimarea propriu -zisă a nodului respectiv, ci și suprimarea tuturor arcelor
incidente acestiu nod.

26
CAPITOLUL II
Algoritmi de drum minim

2.1 Prezentare generală

Fiind dat un graf orientat G = (V, E), se consideră funcția w : E -> W,
numită funcție de cost, care asociază fiecărei muchii o valoare numerică.
Domeniul funcției poate fi extins, pentru a include și perechile de noduri între
care nu există muchie directă, caz în care valoarea este +8 . Costul unui drum
format din mu chiile p12 p23 … p(n -1)n, având costurile w12, w23,…, w(n -1)n,
este suma w = w12+w23+…+w(n – 1)n. În figură 2.1 alăturat, costul drumului de
la nodul 1 la 5 este:

• drumul 1: w14 + w45 = 30 + 20 = 50

• drumul 2: w12 + w23 + w35 = 10 + 20 + 10 = 40

• drumul 3: w13 + w35 = 50 + 10 = 60

Costul minim al drumului dintre două noduri este minimul dintre costurile
drumurilor existente între cele două noduri. În exemplul de mai sus, drumul de
cost minim de la nodul 1 la 5 este prin nodurile 2 și 3. Deși, în cele mai multe
cazuri, costul este o funcție cu valori nenegative, există situații în care un graf
cu muchii de cost negativ are relevanță practică. O parte din algoritmi pot
determina drumul corect de cost minim inclusiv pe astfel de grafuri. Totuși, nu
are sens căutarea drumului minim în cazurile în care graful conține cicluri de
cost negativ − un drum minim ar avea lungimea infinită, întrucât costul său s -ar
reduce la fiecare reparcurgere a ciclului. Ciclul 1 -> 2 -> 3 -> 1 din figura 2.2
are costul -20.

• drumul 1: w12 + w23 + w35 = 10 + 20 + 10 = 40

• drumul 2: (w12 + w23 + w31) + w12 + w23 + w35 = -20 + 10 + 20 +
10 = 20

• drumul 3: (w12 + w23 + w31) + (w12 + w23 + w31) + w12 + w23 +
w35 = -20 + ( -20) + 10 + 20 + 10
= 0

27

Figura 2.1 Figura 2.2

Relaxarea unei muchii v1v2 constă în a testa dacă se poate reduce costul ei,
trecând printr -un nod intermediar u. Fie w12 costul inițial al muchiei de la v1 la
v2, w1u costul muchiei de la v1 la u, și wu2 cos tul muchiei de la u la v2. Dacă
w > w1u + wu2, muchia directă este înlocuită cu succesiunea de muchii v1u,
uv2.În figură 2.3, muchia de la 1 la 3, de cost w13 = 50, poate fi relaxată la
costul 30, prin nodul intermediar u = 2, fiind înlocuită cu succesiune a w12,
w23. Toți algoritmii prezentați în continuare se bazează pe relaxare pentru a
determina drumul minim.

Figura 2.3

28

2.2 Algoritmul lui Dijkstra

Dijkstra poate fi folosit doar în grafuri care au toate muchiile nenegative.
Algoritmul este de tip Greedy: optimul local căutat este reprezentat de costul
drumului dintre nodul sursa s și un nod v. Pentru fiecare nod se reține un cost
estimat d[v], inițializat la început c u costul muchiei s -> v, sau cu +8, dacă nu
există muchie. În figură 2.4, surs a s este nodul 1.

Figura 2.4

Aceste drumuri sunt imbuntățite la fiecare pas, pe baza celorlalte
costuri estimate. Algoritmul selectează, în mod repetat, nodul u care are, la
momentul respectiv, costul estimat minim (față de nodul surs ă). În continuare,
se încearcă și; se relaxeze restul costurilor d[v]. Dacă d[v] < d[u] + wuv , d[v]
ia valoarea d[u] + wuv. Pentru a ține evidența muchiilor care trebuie relaxate, se
folosesc două structuri: S(mulțimea de vârfuri deja vizitate) și Q (o co adă cu
priorități, în care nodurile se află ordonate după distanța față de sursă) din care
este mereu extras nodul aflat la distanța minimă. În S se află inițial doar sursa,
iar în Q doar nodurile spre care există muchie directă de la sursă, deci care au
d[nod] < +8.

În exemplul din figura 2.4 vom inițializa S = {1} și Q = {2, 4, 3}. La primul
pas este selectat nodul 2, care are d[2] = 10. Singurul nod pentru care d[nod]
poate fi relaxat este 3. d[3] = 50 > d[2] + w23 = 10 + 20 = 30.

29

Figura 2.5

După primul pas, S = {1, 2} și Q = {4, 3}. La următorul pas este selectat
nodul 4, care are d[4] = 30. Pe baza lui, se poate modifica d[5]: d[5] = +∞ >
d[4] + w45 = 30 + 20 = 50.

Figura 2.6

După al doilea pas, S = {1, 2, 4} ți Q = {3, 5}. La următorul pas este selectat
nodul 3, care are d[3] = 30, ți se modifică din nou d[5]: d[5] = 50 > d[3] + w35
= 30 + 10 = 40. Algoritmul se încheie când coada Q devine vidă, sau când S
conține toate nodur ile.

Pentru a putea determina și muchiile din care este alcătuit drumul minim
căutat, nu doar costul său final, este necesar să reținem un vector de părinți P.

30
Pentru nodurile care au muchie directă de la sursă, P[nod] este inițializat cu
sursa, pentru re stul cu null.

Pseudocodul pentru determinarea drumului minim de la o sursă către
celelalte noduri utilizând algoritmul lui Dijkstra este:
AlgDijk(sursa, deșt):

selectat(sursa) = true
foreach nod în V // V = mult nodurilor
dacă există muchie[sursa, nod] // inițializam distanța până la
nodul respectiv
x[nod] = w[sursa, nod]
introdu nod în Q // părintele nodului devine sursa
n[nod] = sursa
altfel
x[nod] = +∞ // distanta infinită
n[nod] = null // nu are părinte
// relaxări succesive
cât timp Q nu e vida
u = extrage_min (Q)
selectat(u) = true
foreach nod în vecini[u] // (*)
// dacă drumul de la sursa la nod prin u
//este mai mic decât cel curent
dacă not selectat(nod) și d[nod] > x[u] + w[u, nod] //
actualizează distanta și părinte
x[nod] = d[u] + w[u, nod]
n[nod] = u // actualizează poziția nodului în coada prioritară
actualizează (Q,nod) // găsirea drumului efectiv
Inițializează Drum = {}
nod = n[deșt]
cât timp nod != null
inserează nod la începutul lui Drum
nod = n[nod]

31
2.3 Algoritmul lui Bellman -Ford

Algoritmul Bellman Ford poate fi folosit și pentru grafuri ce conțin muchii
de cost negativ, dar nu poate fi folosit pentru grafuri ce conțin cicluri de cost
negativ (când căutarea unui drum minim nu are sens). Cu ajutorul său putem
afla dacă un g raf conține cicluri. Algoritmul folosește același mecanism de
relaxare ca și Dijkstra, dar, spre deosebire de acesta, nu optimizează o soluție
folosind un criteriu de optim local, ci parcurge fiecare muchie de un număr de
ori egal cu numărul de noduri și încearcă să o relaxeze de fiecare dată, pentru a
îmbunătăți distanța până la nodul destinație al muchiei curente. Motivul pentru
care se face acest lucru este că drumul minim dintre sursă și orice nod destinație
poate să treacă prin maximum |V| nodur i (adică toate nodurile grafului); prin
urmare, relaxarea tuturor muchiilor de |V| ori este suficientă pentru a propaga
până la toate nodurile informația despre distanța minimă de la sursă. Dacă, la
sfârșitul acestor |E|*|V| relaxări, mai poate fi îmbun ătățită o distantă, atunci
graful are un ciclu de cost negativ și problema nu are soluție.

Menținând notațiile anterioare, pseudocodul algoritmului este:

AlgBF(sursa):

// inițializări
foreach nod în V // V = mult nodurilor
dacă muchie[sursa, nod]
x[nod] = w[sursa, nod]
n[nod] = sursa
altfel
x[nod] = +∞
n[nod] = null
x[sursa] = 0
n[sursa] = null
// relaxări succesive
for i = 1 to |V|
foreach (u, v) în E // E = mulțimea muchiilor
dacă x[v] > x[u] + w(u,v)
x[v] = x[u] + w(u,v)
n[v] = u;
// dacă se mai pot relaxa muchii
foreach (u, v) în E
dacă x[v] > x[u] + w(u,v)
fail (exista cicluri negativ)

32
2.4 Algoritmul lui Floyd -Warshall

Algo ritmii din această secțiune determină drumul de cost minim dintre
oricare două noduri dintr -un graf. Pentru a rezolva această problemă s -ar putea
aplica unul din algoritmii de mai sus, considerând că sursă fiecare nod, pe rând,
dar o astfel de abordare ar fi ineficientă. Algoritmul Floyd – Warshall compară
toate drumurile posibile din graf dintre fiecare 2 noduri, și poate fi utilizat și în
grafuri cu muchii de cost negativ. Estimarea drumului optim poate fi
reținut într -o structură tridimension ală d[v1, v2, k], cu semnificația − costul
minim al drumului de la v1 la v2, folosind ca noduri intermediare doar noduri
până la nodul k. Dacă nodurile sunt numerotate de la 1, atunci d[v1, v2, 0]
reprezintă costul muchiei directe de la v1 la v2, consider ând +∞ dacă aceasta nu
există. Exemplu, pentru v1 = 1, respectiv 2.

Figura 2.7

Pornind cu valori ale lui k de la 1 la |V|, ne interesează să găsim cea mai
scurtă cale de la fiecare v1 la fiecare v2 folosind doar noduri intermediare din
mulțimea {1, …, k}. De fiecare dată, comparăm costul deja estimat al drumului
de la v1 la v2, deci d[v1, v2, k -1] obținut la pasul anterior, cu costul drumurilor
de la v1 la k și de la k la v2, adică d[ v1, k, k -1] + d[k, v2, k -1], obținute la
pasul anterior. Atunci, d[v1, v2, |V|] va conține costul drumului minim de la v1
la v2.

33
Pseudocodul acestui algoritm este:
FloydWarshall(G):

n = |V|
int x[n, n, n]
foreach (i, j) în (1..n,1..n)
x[i, j, 0] = w[i,j] // costul muchiei, sau infinit
for k = 1 to n foreach (i,j) în (1..n,1..n)
x[i, j, k] = min(x[i, j, k -1], x[i, k, k -1] + x[k, j, k -1])

Complexitatea temporală este O(|V|3), iar cea spațială este tot O(|V|3).
O complexitate spațială cu un ordin mai mic se obține observând că la un
pas nu este nevoie decât de matricea de la pasul precedent d[i, j, k -1] și cea de
la pasul curent d[i, j, k]. O observație și mai bună este că, de la un pas k -1 la k,
estimările lungi milor nu pot decât să scadă, deci putem să lucrăm pe o singură
matrice. Deci, spațiul de memorie necesar este de dimensiune |V|2.
n = |V|
int x[n, n]
foreach (j, k) în (1..n,1..n)
x[j, k] = w[j,k] // costul muchiei
for k = 1 to n foreach (j,k) în (1..n,1..n)
x[j, k] = min(x[j, k], x[j, m] + x[m, j])

Ca o mică concluzie în privința algoritmilor de drum minin puteam spune că
algoritmult lui Dijkstra calculează drumurile minime de la o sursă către
celelalte noduri , nu poate fi folosit dacă există cicluri de cost negative și
complexitate minimă O(|V|lg |V| + |E|) utilizând heapuri Fibonacci . Algoritmul
lui Bellman – Ford calculează drumurile minime de la o sursă către celelalte
noduri, detectează existenta ciclurilor de cost negative iar complexitate O(|V| *
|E|) pe când algoritmul Floyd – Warshall ca lculează drumurile minime intre
oricare două noduri din graf, poate fi folosit în grafuri cu cicluri de cost negativ,
dar nu le detectează iar complexitate O(|V|3)

34
CAPITOLUL III
Prezentarea aplicației GraphG

3.1. Prezentare generală

Aplicația Graph este un program realizat cu scop demonstrative pentru
drumurile minime între noduri.Pentru a demonstra un drum minim dintre noduri
am folosit unul din algoritmi Greedy și anume algoritmul lui Dijkstra.
Fereastra principală a aplicației conț ine trei câmpuri și trei butoane pentru a
crea și a trasa arcele dintre noduri.
-Câmpul “De la” reprezintă nodul de plecare primul nod creeat, locul de
“decolare” de la acesta va începe să se calculeze și până la ultimul nod cel de
“sosire” ponderea cea ma i mică.
-Câmpul “Până la” reprezintă cel de -al doilea nod între care se va forma un
arc dândui o pondere.
-Câmpul “Pondere” este valoarea atribuită unui arc.
-Butonul “Adauga” reprezintă acordul utilizatorului de a crea acel nod și
faptul că este de accord cu valoarea atribuită arcului.
-Butonul “Start” pornește aplicația
-Butonul “Reset” resetează toate nodurile arcele create, pentru a reîncepe o
nouă demonstrație Cum se construiește un graf nou ?
Pentru a construi noduri trebuie doar o apăsare de cl ick pe zona albă
deasupra butoanelor, și se va creea un nod care vor fi numerotați în oridinea în
care au fost creați.Nodurile grafului apar sub forma unor butoane dispuse
circular de culoare neagră numerotate cu cifre începând de la 0 iar arcele sunt
traseele dintre noduri. (Figura 3.1)

35

Figura 3.1

3.2. Utilizarea practică a aplicației

Presupunem că avem un traseu de făcut de la o destinație nodul 0 la altă
destinație nodul n, pe care o să trebuiască să îl parcurgem.Desigur avem puncte
fixe de trecere, “stații” și mai multe oportunități de a parcurge acest traseu noi
încercând să -l aflăm pe cel mai scurt ,cel mai ieftin sau cel mai rapid asta
depinzând la cel fel de pondere ne referim, putem utiliza aplicația pentru a afla
asta.

Începem prin a creea nodul sursă și nodul destinație prin două click -uri pe
zona albă,presupunând că sunt cele mai distanțate, creăm și celelalte noduri sau
“ stații” pe aceeași zonă prin același procedeu. (Fig 3.2)

36

(Figura 3.2)

După ce am creat nodurile în câmpul “De la” și în cel “Până la” vor apărea
nodurile create.Selectăm în primul câmp nodul de plecare nodul 0, pe următorul
nod stație, care poate fi 2 , 4, 3, 5 până la nodul final nodul 1 de fiecare dată
când selectăm două n oduri mergem la câmpul pondere și îi asociem o valoare și
apăsăm butonul “Adauga”, vom observa că între cele două
noduri se va trasa un arc cu o anumită valoare după ce terminăm traseele
apăsăm butonul “Start”.
Putem observa în figură 3.3 ca pentru fiecare nod s -a calculat distanța
minimă începând din nodul sursa.Pe fiecare nod este afișat o valoare calculată
din care ne putem da seama că pentru fiecare nod poate să fie un drum optim
diferit.
De exemplu : nodul 3, drumul optim este 0 – 7 – 3 cu o pondere de 15 fiind
cea mai mică decât traseul 0 – 2 – 3.
Pentru nodul final ales de noi, nodul 1, drumul optim este parcurgerea
nodurilor 0, 7 și 9.

37

(Figura 3.3)

Butonul “Resetează” șterge toate nodurile și legăturile dintre acesta și este
pregătit pentru un nou test de calcul al drumului minin.

3.3 Implementarea aplicației

Dijkstra poate fi folosit doar în grafuri care au toate muchiile nenegative.
Algoritmul este de tip Greedy: optimul local căutat este reprezentat de costul
drumului dintre nodul sursa s și un nod v.
Pentru fiecare nod se reține un cost estimat d[v], inițializat la început cu
costul muchiei. Pentru a putea determina și muchiile din care este alcătuit
drumul minim căutat, nu doar costul său final, este necesar să reținem un ve ctor
de părinți . Aceste drumuri sunt imbuntățite la fiecare pas, pe baza celorlalte
costuri estimate. Algoritmul selectează, ăn mod repetat, nodul u care are, la
momentul respectiv, costul estimat minim (față de nodul sursă). În continuare,

38
se încearcă și ; se relaxeze restul costurilor d[v]. Dacă d[v] < d[u] + wuv , d[v]
ia valoarea d[u] + wuv. Pentru a ține evidența muchiilor care trebuie relaxate, se
folosesc două structuri: S(mulțimea de vârfuri deja vizitate) și Q (o coadă cu
priorități, în care noduri le se află ordonate după distanța față de sursă) din care
este mereu extras nodul aflat la distanța minimă. În S se află inițial doar sursa,
iar în Q doar nodurile spre care există muchie directă de la sursă. Pentru
nodurile care au muchie directă de la su rsă, P[ nod] este inițializat cu sursa.

Structura codului sursă a implementării algoritmului este :
public class Dijkstra
{
/* Ia matricea de adiacenta în următorul formatul prezentată într -un
format 2D
*Exemplu nodul 1 la 3 e accesibil la un cost de 4
* 0 1 2 3 4
* 0 { 0, 2, 5, 0, 0},
* 1 { 0, 0, 0, 4, 0},
* 2 { 0, 6, 0, 0, 8},
* 3 { 0, 0, 0, 0, 9},
* 4 { 0, 0, 0, 0, 0}
/* Rezultând tablouri cu distanțele până la noduri
public double[] dist { get; private set; }
public int[] cale { get; private set; }
private List<int> coada = new List<int>();
private void Inițializează(int s, int len)
{
dist = new double[len];
cale = new int[len];

/*Setează distanța pentru toate nodurile la valoarea infinit*/
for (int i = 0; i < len; i++)
{
dist[i] = Double.PositiveInfinity;
coada.Add(i);
}

/*Setează distanța la 0 pentru nodul de început și null pe cel din
urmă*/
dist[s] = 0; cale[s] = -1;
}

39
/*Selectează următorul nod pentru a evalua șirul*/
private int GetNextNod()
{
double min = Double.PositiveInfinity;
int Arce= -1;

/*Cauta în șir pentru a găsi nodul cu cea mai mică distanța*/

foreach (int j în coadă)
{
if (dist[j] <= min)
{
min = dist[j];
Nod = j;
}
}

coada.Remove(Nod);
return Nod;

}

/* Ia un graf ca input o matrice de adiacența și un nod de început */ public
Dijkstra(double[,] G, int s)
{
/*Verifica formatul grafului și dacă conține ceva */

if (G.GetLength(0) < 1 || G.GetLength(0) != G.GetLength(1))
{
throw new ArgumentException("Eroare de graf sau format greșit!!!");
}

int len = G.GetLength(0);

Initialize(s, len);

while (coadă.Count > 0)
{
int u = GetNextNod();
/* Find the nodes that u connects to and perform relax */
/* Găsește nodurile care le am conectat/* for (int v = 0; v < len; v++)
{

40
/* Verifica dacă arcele au valori negative*/ if (G[u, v] < 0)
{
throw new Argume ntException("Graful conține arce negative(s)");
}
/* Verifica dacă există un arc intre u și v */
if (G[u, v] > 0)
{
/* Dacă există realaxeaza muchia */
if (dist[v] > dist[u] + G[u, v])
{
dist[v] = dist[u] + G[u, v];
path[v] = u;
}
}
}
}
}
}
}

Clasa nodurilor :

namespace Dijkstra
{
public class Noduri
{
public Point p { get; private set; }
public int ident {get; private set; }
public int dist { get; set; }

public Noduri(Point p, int ident)
{
this.p = p;
this.ident = ident;
}
}
}

41
Clasa arce:
namespace Dijkstra
{
public class Arce
{
public int from { get; private set; } public int to { get; private set; }
public Double weight { get; private set; }

public Arce(int from, int to, Double weight)
{
this.from = from; this.to = to;
this.weight = weight;
}
}
}

42

Concluzii:

Ideea de a dezvolta o aplicație de grafuri ponderate a fost o provocare, care
mi-a oferit șansa de a îmbina cunoștințele acumulate de -a lungul anilor de
studiu cu studiul celei mai noi tehnologii pentru dezvoltarea de aplicații.
Această aplicație poate avea și o utilitate practică,în transporturi în cea mai
mare măsura pentru economie de timp și bani, lăsând însă și posibilitatea
îmbunată țirii acesteia.

43
Bibliografie:

1. Paraschiva Popovici – Structuri de date de tip graf în C
2. Charles Carroll – C# ASP . NET Lessons
3. Claudiu Moisescu – Aproape totul despre Internet, Editura Cartea de
Buzunar
4. Herbert Schildt – C#, Editura Teora
5. Nandu -C#.NETWebDeveloper‟sGuise
6. http://bigfoot.cs.upt.ro/~chirilă/teaching/upt/labs/2ctipaa/lab10/paa10 .ht
ml
7. http://www.cipsoft.go.ro/sdaa/lab05/sdaa05.html
8. http://www.graf.go.ro/index1.html
9. http://vega.unitbv.ro/~andonie/Cartea%20de%20algoritmi/cap9.htm#s9
10. http://andreidiaconeasa.site90.com/drumuriminimeingraf.html