Home - qdidactic.com
Didactica si proiecte didacticeBani si dezvoltarea cariereiStiinta  si proiecte tehniceIstorie si biografiiSanatate si medicinaDezvoltare personala
referate stiintaSa fii al doilea inseamna sa fii primul care pierde - Ayrton Senna





Aeronautica Comunicatii Drept Informatica Nutritie Sociologie
Tehnica mecanica




Informatica


Qdidactic » stiinta & tehnica » informatica
Algoritmi pentru prelucrarea grafurilor



Algoritmi pentru prelucrarea grafurilor


ALGORITMI PENTRU PRELUCRAREA GRAFURILOR



1.Continutul lucrarii


In lucrare sunt prezentati algoritmii lui Dijkstra si Floyd pentru gasirea cailor de cost minim intre doua noduri precizate, respectiv intre oricare doua noduri ale unui graf si algoritmii lui Kruskal si Prim pentru gasirea arborelui de cost minim de acoperire a unui graf.


2.Consideratii teoretice

2.1.Caile de cost minim dintr-un varf

Se considera un graf orientat G =(V, E) etichetat, in care fiecare arc are ca eticheta un numar nenegativ numit cost. Graful se reprezinta in memorie prin matricea de adiacente etichetata, care se mai numeste matricea costurilor.

Fiind date doua varfuri, unul sursa si unul destinatie, se cere gasirea drumului de cost minim de la sursa la destinatie. Algoritmul lui Dijkstra de rezolvare a acestei probleme consta in urmatoarele:

- se pastreaza o multime S de varfuri jIV, pentru care exista cel putin un drum de la sursa la j. Initial S =.

- la fiecare pas, se adauga la S un varf a carui distanta fata de un varf din S este minima.

Pentru a inregistra caile minime de la sursa la fiecare varf se utilizeaza un tablou TATA, in care TATA[k] pastreaza varful anterior lui k pe calea cea mai scurta.

In descrierea algoritmului se fac urmatoarele notatii:




- n numarul varfurilor multimii V;

- multimea S se reprezinta prin vectorul caracteristic ( elementele sale sunt S[i]=1, daca iIS si S[i]=0, daca i S;

- vectorul DISTANTE de n elemente al distantelor minime de la sursa la fiecare varf;

- matricea de costuri COST de nxn elemente: COST[ i ][j]=c>0 daca ( i ,j)IE, COST[i][j]=0 daca i =j si COST[i][j]=+ daca (i, j) E;

- vectorul TATA.

Algoritmul lui Dijkstra este urmatorul:

#define NMAX .

#define INFINIT .

float DISTANTE[NMAX];

float COST[NMAX][NMAX];

int TATA[NMAX];

int S[NMAX];

void DIJKSTRA(int n,int sursa)


/*introducere sursa in S*/

S[sursa]=1;

TATA[sursa]=0;

DISTANTE[sursa]=0;

/*construire vectori DISTANTE si TATA */


for (pas=1;pas<=n-1;pas++)


}

}


Vectorul TATA contine varfurile accesibile din varfurile sursa. El permite reconstruirea drumurilor de la varful sursa la oricare varf accesibil. Pentru varfurile inaccesibile din varful sursa vom avea S[i]=0 si DISTANTE[i]=INFINIT.


2.2.Caile de cost minim din oricare varf

Algoritmul prezentat la 2.1. poate fi repetat din nodurile unui graf. Acest lucru permite calculul unui tablou al drumurilor minime intre toate perechile de varfuri ale grafului. In continuare se prezinta un algoritm mai simplu, algoritmul lui Floyd.

Algoritmul lui Floyd consta in gasirea costurilor minime intre oricare doua varfuri i, jIV. Aceste costuri minime se pastreaza in matricea A. Matricea A este initial egala cu matricea costurilor. Calculul distantelor minime se face in n iteratii, n fiind numarul varfurilor. La iteratia k, A[i][j] va avea ca valoare cea mai mica distanta intre i si j pe cai care nu contin varfuri peste k (exceptand capetele i si j). Se utilizeaza formula urmatoare:

Aij(k)= min (Aij(k-1),Aik(k-1)+Akj(k-1)).

Deoarece Aik(k)=Aik(k-1) si Akj(k)=Akj(k-1) se poate utiliza o singura copie a matricii A.


Algoritmul lui Floyd este urmatorul:


#define NMAX .

float C[NMAX][NMAX];  /*matricea costurilor*/

float A[NMAX][NMAX];

void FLOYD(int n)



Pentru a pastra caile minime, se utilizeaza un tablou aditional P, unde P[i][j] tine acel varf k ce a condus la distanta minima A[i][j]. Daca P[i][j]==0, atunci arcul (i, j) este calea minima intre i si j.



Pentru a afisa varfurile intermediare aflate pe calea cea mai scurta intre i si j se poate proceda conform algoritmului urmator:


void CALE(int i, int j)


}


2.3.Arborele de acoperire de cost minim


Fie G =(N, R) un graf neorientat conex. Fiecarei muchii (i, j)IR i se asociaza un cost c[i][j]>0. Problema consta in a determina un graf partial conex A = (N, T), astfel incat suma costurilor muchiilor din T sa fie minima. Se observa imediat ca acest graf partial este chiar arborele de acoperire.

Algoritmul lui Prim consta in urmatoarele:

- se porneste cu o submultime W, formata din nodul de plecare si multimea T  vida;

- la fiecare iteratie, se selecteaza muchia (w, u) cu cel mai mic cost, wIW si uIN-W. Se adauga u la W si (w, u) la T. In final, W va contine toate nodurile din N, iar T va contine muchiile arborelui de  acoperire minimal.

void algoritm_PRIM(int n)

; //se pleaca din nodul 1

T=; //multimea vida

while (W!=N)


}


Un alt algoritm apartine lui Kruskal. In acest caz, muchiile sunt ordonate crescator dupa cost. Arborele de acoperire va contine n-1 muchii. La fiecare pas se alege muchia de cost minim care nu formeaza ciclu cu muchiile aflate deja in T.

Acest algoritm are urmatoarea descriere:


void algoritm_Kruskal(int n)

;

while (T nu este arbore de acoperire)


}


Problema mai dificila in algoritm consta in verificarea daca o muchie creeaza ciclu in T.


3.Mersul lucrarii


3.1.Sa se implemeteze algoritmul lui Dijkstra de gasire a cailor de cost minim dintr-un varf al unui graf orientat. Se va construi si afisa arborele avand ca radacina varful sursa. Care este performanta algoritmului in ceea ce priveste timpul de calcul?


3.2.Sa se implementeze algoritmul lui Floyd de gasire a cailor de cost minim din oricare varf al unui graf neorientat. Se vor afisa caile de cost minim intre doua varfuri, date de la tastatura. Care este performanta algoritmului in ceea ce priveste timpul de calcul?


3.3..Sa se implementeze algoritmul lui Prim de gasire a arborelui de acoperire a unui graf neorientat.


3.4.Sa se implementeze algoritmul lui Kruskal de gasire a arborelui de acoperire a unui graf neorientat. Sa se faca o comparatie in ceea ce priveste timpul de calcul intre algoritmul lui Kruskal si cel al lui Prim.









Contact |- ia legatura cu noi -|
Adauga document |- pune-ti documente online -|
Termeni & conditii de utilizare |- politica de cookies si de confidentialitate -|
Copyright © |- 2022 - Toate drepturile rezervate -|

Informatica



Access
Autocad
Baze de date
C
Calculatoare
Catia
Excel
Foxpro
Grafica design
Html
Internet
Java
Linux
Mathcad
Matlab
Oracle
Outlook
Photoshop
Php
Powerpoint
Retele calculatoare
Sql
Windows
Word

Referate pe aceeasi tema


Bazele informaticii - test grila
Identificarea tipurilor de informatii si caracterizarea acestora pentru un site comercial - prezentarea site-ului www.dacia.ro
Arbori
Aplicatii - nnmodel
Lucrare pentru sustinerea examenului de atestat profesional in informatica - “catalog oriflame” aplicatie programare vizuala



Ramai informat
Informatia de care ai nevoie
Acces nelimitat la mii de documente, referate, lucrari. Online e mai simplu.

Contribuie si tu!
Adauga online proiectul sau referatul tau.