SDA_c4

97

4. Grafuri orientate şi neorientate

Pentru a exemplifica un graf foarte simplu, să ne imaginăm harta unui oraş ca un ansamblu de

străzi şi să ne propunem să descriem un traseu dintr-un punct x într-un punct y. Vom reprezenta

intersecţiile străzilor prin puncte şi străzile dintre intersecţii prin linii (arce). Traseul astfel descris între

cele două puncte x, y reprezintă un graf. Dacă nu sunt restricţii în ceea ce priveşte direcţia de

parcurgere a străzilor avem un graf neorientat. Dacă însă străzile nu pot fi parcurse decât într-o anumită

direcţie (cum ar fi străzile cu sens unic pentru autovehicule) atunci vom avea un graf orientat.

Dacă deplasarea implică şi nişte costuri (timp, combustibil) atunci pe graf fiecărei legături (arc)

între două intersecţii (noduri ale grafului) se va specifica şi costul respectiv. În acest caz vom avea şi o

probelmă de drum optim sau cea de drum de cost minim.

Se numeşte graf neorientat o pereche ordonată de mulţimi (V, M), unde V este mulţimea finită şi

nevidă de vârfuri sau noduri, iar M este o mulţime neordonată de perechi de elemente din V, numite

muchii sau arce.

Gradul unui nod (vârf) dintr-un graf reprezintă numărul de muchii care trec prin nodul

respectiv. Un nod cu gradul zero nu este legat la nici o muchie, este un nod izolat, iar unul care are

gradul unu este un nod terminal. Într- un graf cu m muchii suma gradelor tuturor muchiilor este egală

cu 2*m, deoarece fiecare muchie contribuie cu câte două unităţi (una la nodul i, şi una pentru nodul j)

la suma gradelor grafului.

Un graf poate fi reprezentat în mai multe moduri: prin matricea de adiacenţă sau drumuri, prin

vector de muchii sau prin lista vecinilor.

Reprezentarea prin matricea de adiacenţă (A) pentru un graf cu n noduri şi m muchii va fi o

matrice n*n cu m valori diferite de 0 deasupra diagonalei principale şi tot atâtea dedesubtul acesteia,

întrucât matricea unui graf neorientat este simetrică. Dacă există muchia (i,j) atunci a[i][j]=a[j][i]=1,

iar în caz contrar a[i][j]=a[j][i]=0. De obicei se iniţializează matricea A cu 0 şi apoi se citesc muchiile

grafului şi se actualizează valorile acelor respective din matricea grafului. Matricea drumurilor (sau

costuri) conţine pentru muchiile existente (deci care aveau în matricea de adiacenţă valoarea 1)

valoarea costului (lungimea drumului) arcului respectiv, iar pentru celelalte (care nu sunt conectate, şi

care aveau valoarea 0 în matricea de adiacenţă) valoarea infinit (sau o valoare foarte mare, pentru

reprezentarea lor în calculator).

Reprezentarea grafului prin vector de muchii presupune că fiecare muchie a grafului poate fi

privită ca o structură cu două componente, şi anume cele două vârfuri, la care se poate adăuga şi costul

(drumul) asociat muchiei.

Alte noţiuni legate de grafuri sunt noţiunile de lanţ şi ciclu. Se numeşte lanţ o succesiune de

vârfuri {v1, v2, . . ., vn} cu proprietatea că oricare două vârfuri (vi, vj) sunt adiacente. Dacă toate

vârfurile sunt distincte, lanţul se numeşte elementar, în caz contrar lanţul este ne-elementar.

De exemplu:

avem lanţurile elementare {1, 2, 3, 5, 6, 8}, {1, 4, 3, 5, 6, 8} şi lanţurile ne-elementare {7, 3, 5, 6, 3, 2},

{4, 3, 5, 6, 3, 2}.

Un ciclu este un lanţ {v1, v2, . . ., vn} cu proprietatea că v1 = vn şi toate muchiile sunt distincte.

Dacă toate vârfurile sunt distincte, ciclul se numeşte elementar, în caz contrar ciclul este ne-elementar.

5

8

4

1

2 3

6

7

98

Să considerăm problema care verifică dacă o secvenţă de vârfuri dată reprezintă un lanţ

elementar sau ne-elementar, într-un graf neorientat. Aceasta înseamnă să verificăm în matricea de

adiacenţă existenţa muchiilor (vi, vj) ce aparţin lanţului de testat, vi şi vj fiind vârfuri succesive din

lanţul de testat. După determinarea existenţei lanţului verificăm dacă este elementar sau nu, adică dacă

toate vârfurile sunt distincte sau nu.

/* lantgraf.c - programul determina daca exista un lant dat intr-un graf */

#include <stdio.h>

#include <conio.h>

#define DIMN 6 // numar maxim noduri

#define DIMM 10 // numar maxim muchii

void citire_graf (int a[DIMN+1][DIMN+1], int *pn, int *pm){

int i, j, k;

clrscr();

printf("\nDati numar noduri, graf neorientat, n: ");

scanf("%d", pn);

printf("Nr. de muchii: ");

scanf("%d", pm);

for (i=1; i<= *pn; i++)

for (j=1; j<=*pn; j++)

a[i][j]=0; // initializare matrice drumuri (costuri) pt. graf

printf("\nCitire graf prin muchiile sursa.\n");

for (k=1; k<= *pm; k++)

{

printf("Muchie, varf sursa, dest: ");

scanf ("%d%d", &i, &j);

a[j][i]=a[i][j]=1; // pt. graf neorientat costul (i,j)=cost(j,i)

}

}

void citire_lant(int l[DIMM+1], int *pdl){

int i;

printf("\nDati numar noduri pentru lantul de testat: ");

scanf("%d", pdl);

for (i=1; i<= *pdl; i++)

{

printf("Varful %d din lant: ", i);

scanf ("%d", &l[i]);

}

printf("\nLantul cautat in garf este urmatorul:\n");

for (i=1; i<= *pdl; i++)

printf("%d -> ", l[i]);

}

int test_lant(int g[DIMN+1][DIMN+1], int l[DIMM+1], int dl, int *elem){

int i, j;

*elem=1; // initializam cu 1 (presupunem ca este lant elementar)

for (i=1; i<=dl; i++)

if (!g[l[i]][l[i+1]])

return 0; // nu este lant, un varf nu este in matrice

for (i=1; i<=dl-1; i++)

99

for (j=i+1; j<=dl; j++)

if(l[i]==l[j])

*elem=0; // este ne-elementar

return 1;

}

void main()

{

int a[DIMN+1][DIMN+1], l[DIMM+1]; // matricea de adiacenta si lantul cautat

int n, nm, dl, elementar;

citire_graf (a, &n, &nm);

citire_lant (l, &dl);

if (test_lant(a, l, dl, &elementar)){

printf("\n\nEste un lant ");

if (!elementar)

printf("ne-");

printf("elementar!\n");

}

else

printf("\n\nNu este un lant in graf !!!\n");

printf("\n");

}

Un alt exemplu de prelucrare de graf ar putea fi problema colorării muchiilor unui graf. Se cere

să se determine toate modurile posibile de colorare a muchiilor unui graf neorientat cu n vârfuri şi m

muchii, utilizând c culori, cu restricţia ca oricare două muchii ce pleacă din acelaşi vârf să fie colorate

diferit (să nu aibă aceeaşi culoare). Vom memora colorile muchiilor grafului într-un vector culoare ce

va avea m componente. Vom utiliza metoda backtracking şi vom valida o culoare culoare[i] dacă

valoarea respectivă se mai află în vectorul culoare pe un nivel k pentru muchia k, dacă aceste două

muchii nu ajung în acelaşi vârf (adică, nu se intersectează).

/* colorgrf.c - programul determina toate solutiile pentru colorarea celor

m muchii ale unui graf cu n noduri, utilizand c culori diferite,

cu restrictia ca doua muchii ce se intersecteaza intr-un nod sa

nu aiba aceeasi culoare

Graful este reprezentat ca un vector de muchii

*/

#include <stdio.h>

#include <conio.h>



typedef struct{

int v1, v2; // cele doua varfuri ale unei muchii

} VECT_MUCHII;

int nr_sol=0;

void citire_graf (VECT_MUCHII vm[DIMM+1], int a[DIMN+1][DIMN+1], int *pn, int *pm){

int i, j, k;

clrscr();


100

scanf("%d", pn);


scanf("%d", pm);

for (i=1; i<= *pn; i++)

for (j=1; j<=*pn; j++)


printf("\nCitire graf prin muchiile sursa.\n");

for (k=1; k<= *pm; k++)

{

printf("Muchie: varfuri sursa, dest: ");

scanf ("%d%d", &vm[k].v1, &vm[k].v2);

a[vm[k].v1][vm[k].v2]=a[vm[k].v2][vm[k].v1]=1; // costul (i,j)=cost(j,i)

}

}

void tipar_culoare(int culoare[DIMM+1], VECT_MUCHII vm[DIMM+1], int nm){

int i;

for (i=1; i<=nm; i++) // tipareste culoarea pentru muchia 'i', specificand

if (vm[i].v1 < vm[i].v2) // varful sursa si cel destinatie, in ordine

printf("m(%d-%d)=c%d, ", vm[i].v1, vm[i].v2, culoare[i]);

else

printf("m(%d-%d)=c%d, ", vm[i].v2, vm[i].v1, culoare[i]);

printf("\n");

if ((nr_sol+1)%20==0){

printf("\nAfisarea continua dupa apasarea unei taste !!!\n");

getch();

}

}

int validare_culoare (VECT_MUCHII vm[DIMM+1], int culoare[DIMM+1], int p){

int k;

for (k=1; k<p; k++)

if (culoare[k] == culoare [p])

if (vm[k].v1==vm[p].v1 || vm[k].v1==vm[p].v2 ||

vm[k].v2==vm[p].v1 || vm[k].v2==vm[p].v2)

return 0;

return 1;

}

void incerc_culoare(VECT_MUCHII vm[DIMM+1], int culoare[DIMM+1],

int c, int nm, int p){

int i, j;

for (i=1; i<=c; i++)

{culoare[p]=i;

if (validare_culoare(vm, culoare, p))

if (p==nm) // solutie completa (toate nodurile colorate)

{tipar_culoare(culoare, vm, nm);

nr_sol++;

}

else

incerc_culoare(vm, culoare, c, nm, p+1);

// culoare[p]=0; // sterge culoarea incercata

101

}

}

void main(){

VECT_MUCHII vm[DIMM+1]; // vectorul de muchii (muchie=doua varfuri)

int culoare[DIMM+1], a[DIMN+1][DIMN+1]; // vect culori si matricea de adiacenta

int n, nm, c;

citire_graf (vm, a, &n, &nm);

printf("\nNumarul de culori cu care se coloreaza: ");

scanf("%d", &c);

incerc_culoare(vm, culoare, c, nm, 1);

if(nr_sol)

printf("\nNumarul total de solutii este: %d\n", nr_sol);

else

printf("\nProblema nu are solutii");

printf("\n");

}

O altă problemă legată de grafuri neorientate ar fi cea care generează, utilizând metoda

backtracking, toate ciclurile elementare dintr-un graf. Problema nu diferă mult de cea precedentă. Se

modifică condiţia de validitate, acum toate vârfurile din vectorul ce conţine soluţia trebuie să fie

diferite, cu excepţia primului care va fi egal cu ultimul, şi cea care determină dacă soluţia este

completă, adică există cel puţin trei vârfuri şi ultimul este identic cu primul (lungimile lor vor fi

diferite).

/* ciclugrf.c - programul determina toate ciclurile elementare dintr-un

graf cu n noduri si m muchii. */

#include <stdio.h>

#include <conio.h>



typedef struct{

int v1, v2; // cele doua varfuri ale unei muchii

} VECT_MUCHII;

int nr_sol=0;

void citire_graf (VECT_MUCHII vm[DIMM+1], int a[DIMN+1][DIMN+1], int *pn, int *pm){

int i, j, k;

clrscr();


scanf("%d", pn);


scanf("%d", pm);

for (i=1; i<= *pn; i++)

for (j=1; j<=*pn; j++)


printf("\nCitire graf prin muchiile sale.\n");

for (k=1; k<= *pm; k++)

{

printf("Muchia %d, varfuri: ", k);

scanf ("%d%d", &vm[k].v1, &vm[k].v2); // costul (i,j)=cost(j,i)

102

a[vm[k].v1][vm[k].v2]=a[vm[k].v2][vm[k].v1]=1;

}

}

void init_ciclu (int ciclu[DIMM+1], int nm){

int i;

for (i=1; i<=nm; i++)

ciclu[i]=0;

}

void tipar_ciclu(int ciclu[DIMM+1], int p){

int i;

for (i=1; i<p; i++) // tipareste ciclul 'p'

printf("%d -> ", ciclu[i]);

printf("%d\n", ciclu[p]);

if ((nr_sol+1)%20==0){

printf("\nAfisarea continua dupa apasarea unei taste !!!\n");

getch();

}

}

int validare_ciclu (int a[DIMN+1][DIMN+1], int ciclu[DIMM+1], int p){

int k;

if ( !a[ciclu[p]][ciclu[p-1]] ) // daca nu exista muchia -> nu e valid ciclul

return 0;

for (k=2; k<p; k++) // daca varful mai exista in solutia 'ciclu', pana

if (ciclu[k] == ciclu [p]) // la pozitia 'p-1' -> nu e solutie corecta

return 0;

return 1;}

void incerc_ciclu(int a[DIMN+1][DIMN+1], int ciclu[DIMM+1], int n, int p){

int i;

for (i=1; i<=n; i++)

{ciclu[p]=i;

if (validare_ciclu(a, ciclu, p))

if (ciclu[p]==ciclu[1] && p>3) // solutie completa

{tipar_ciclu(ciclu, p); // (nod final = nod initial

nr_sol++; // si sunt cel putin 3 noduri)

}

else

incerc_ciclu(a, ciclu, n, p+1);

// ciclu[p]=0; // sterge ciclul incercat

}

}

void main()

{


int ciclu[DIMM+1], a[DIMN+1][DIMN+1]; // vect culori si matricea de adiacenta

int n, nm;


printf("\nCiclurile din graf sunt urmatoarele:\n");

init_ciclu(ciclu, nm);

incerc_ciclu(a, ciclu, n, 1);

103

if(nr_sol)


else


printf("\n");

}

4.1. Parcurgerea grafurilor neorientate Prin parcurgerea unui graf se înţelege vizitarea tuturor nodurilor (vârfurilor) sale într-o anumită

ordine, pe baza unui anumit criteriu. Există doi algoritmi de parcurgere a grafurilor neorientate:

algoritmul de parcurgere în lăţime BF, şi algoritmul de parcurgere în adâncime DF.

Algoritmul de parcurgere în lăţime porneşte parcurgerea cu vizitarea un vârf de start, pentru

care se vizitează toţi vecinii săi. Pentru fiecare din aceste vârfuri (vecini) se vizitează vecinii lor care nu

au fost vizitaţi. Procedeul contină în acest mod până când au fost vizitate toate vârfurile. Pentru graful

prezentat anterior, acest algoritm va furniza următoarea parcurgere:

Parcurgerea grafului Noduri vizitate (vecini) Observaţii

3 – vârful de start 2, 4, 5, 6, 7

2 – vecin al nodului 3 1 3 a fost vizitat

4 – vecin al nodului 3 - 1 şi 3 au fost vizitate

5 – vecin al nodului 3 - 3 şi 6 au fost vizitate

6 – vecin al nodului 3 8 3, 5 şi 7 au fost vizitate

Ordinea vizitării vârfurilor în parcurgerea BF este următoarea: 3, 2, 4, 5, 6, 7, 1, 8,

Pentru a memora ordinea de parcurgere a grafului vom folosi un vector de tip coadă C, în care printr-un

capăt vom introduce vârfurile (de start şi apoi vecinii, adică vârfurile cele nevizitate), iar prin celălalt

vom extrage vârfurile vizitate. De fapt extragerea înseamnă nu elimiarea din vector ci actualizarea

corespunzătoare a poziţiei (indecelui) vârfului extras. Cele două poziţii, de introducere şi respectiv de

extragere, vor fi reprezentate de pi (poziţie introducere) şi pe (poziţie extragere). Pentru graful anterior

evoluţia cozii este următoarea:

pi, pe

Introducem în coadă vârful de start 3. 1

3

pi pe Extragem vârful 3 şi

introducem vecinii săi nevizitaţi

(2, 4, 5, 6, 7).

2 6

3 2 4 5 6 7

pi pe Extragem vârful 2 şi

introducem vecinii săi

nevizitaţi (1)

3 7

3 2 4 5 6 7 1

pi pe Extragem 4 şi 5 care nu

au vecini nevizitaţi, iar

pentru 6 introducem 8.

6 8

3 2 4 5 6 7 1 8

Pe lângă coada C, vom mai utiliza un vector V care specifică dacă un vârf a fost vizitat sau nu

(0-nu a fost vizitat, 1-a fost vizitat). Dimensiunile celor doi vectori vor fi egale cu numărul de noduri

104

din graf. Ambii vectori vor fi iniţializaţi cu 0. Când se introduce un nou vârf k în coada C, vom memora

faptul că urmează a fi vizitat făcând atribuirea C[k]=1. La fiecare pas, după ce se extrage un vârf din

coadă, din poziţia pe, se vor introduce pe la celălalt capăt pi vecinii nevizitaţi ai vârfului extras. Pentru

fiecare vecin vom verifica dacă a fost vizitat sau nu, utilizând vectorul V.

În final pentru a lista ordinea vizitării vârfurilor este suficient să tipărim vectorul C. Vectorul va

conţine atâtea vârfuri câte au fost introduse (pi). Întreg programul este prezentat în continuare.

/* LatBFgrf.c – algoritmul de parcurgere in latime BF a unui graf */

#include <stdio.h>

#include <conio.h>




int i, j, k;

clrscr();


scanf("%d", pn);


scanf("%d", pm);

for (i=1; i<= *pn; i++)

for (j=1; j<=*pn; j++)



for (k=1; k<= *pm; k++)

{

printf("Muchie, varfuri sursa, dest: ");

scanf ("%d%d", &i, &j);

a[j][i]=a[i][j]=1; // pt. graf neorientat costul (i,j)=cost(j,i)

}

}

void parcurg_lat_BF (int a[DIMN+1][DIMN+1], int C[DIMM+1], int V[DIMM+1],

int n, int prim, int *pdimV){

int k, pi=1, pe=1, v; // init. pozitie intrare/ 'extragere' C(oada)

for (k=1; k<=n; k++)

C[k]=V[k]=0;

C[1]=prim; // primul varf vizitat

V[prim]=1; // varful 'prim' a fost vizitat

while (pe<=pi){

v=C[pe]; // varful 'extras', v, din coada, C

for (k=1; k<=n; k++)

if (a[v][k] && !V[k]){ // nod vecin ?, nevizitat ?

pi++; // se introduce in coada

C[pi]=k; // varful k

V[k]=1; // memorez ca a fost vizitat

}

pe++; // 'extrag' urmatorul varf din coada

}

*pdimV=pi;

}

void main()

105

{

int a[DIMN+1][DIMN+1], l[DIMM+1]; // matricea de adiacenta

int C[DIMN+1], V[DIMN+1]; // coada varfurilor parcurse, vizitate

int n, nm, primul, dimV, k;


printf("\nProgramul parcurge in latime graful.\n");

printf("\nSpecificati varful de start pentru parcurgere: ");

scanf("%d", &primul);

parcurg_lat_BF(a, C, V, n, primul, &dimV);

printf("\nParcurgerea in latime este urmatoarea:\n");

for (k=1; k<dimV; k++)

printf("%4d - ", C[k]);

printf("%4d\n", C[k]);

printf("Apasati o tasta pentru a termina programul\n");

getch();

}

Dacă în urma parcurgerii grafului (cu algoritmul BF) s-au vizitat toate nodurile, indiferent care

a fost varful de start, atunci graful este conex. Altfel spus graful are o singură componentă care

cuprinde toate vârfurile grafului.

Se numeşte componentă conexă a grafului G = (V, M), un subgraf G1 = (V1, M1), a lui G, conex,

cu proprietatea că nu există nici un lanţ care să lege un vârf dim V1 cu un vârf din V- V1.

Utilizând algoritmul de parcurgere în lăţime BF putem determina dacă un graf este conex, dacă

după parcurgerea lui nu au rămas vârfuri nevizitate (toate componentele lui V sunt 1).

4.2. Arborele parţial de cost minim Un astfel de arbore are costul cel mai mic dintre toţi arborii ce se pot construi cu vârfurile unui

graf neorientat, care are pentru asociat fiecare muchie un anumit cost. Vom prezenta în continuare

algoritmul lui Prim.

Se consideră pe lângă matricea costurilor a, trei vectori cu următoarea semnificaţie:

- vectorul arborelui propriu-zis, ARB, în care fiecare element are valoarea 1, dacă vârful i a

fost deja inclus în arborele parţial, şi 0 în caz contrar; deci iniţial este 0, iar la introducerea

unui vârf i în arbore vom pune V[i]=1;

- vectorul părinţilor, P, în care pentru fiecare vârf adăugat i, elementul P[i] va reprezenta

vârful părinte al lui i;

- vctorul costurilor C, în care pentru fiecare vârf i elementul C[i] va avea valoarea costului

muchiei care îl leagă de părintele său în arbore.

Toţi cei trei vectori vor fi iniţializaţi cu 0.

Se va alege un vârf de plecare (prim), pe care îl includem în arbore (ARB[prim]=1). Apoi, într-

un ciclu vom adăuga câte un nou vârf în arbore, luând în considerare doar muchiile ce au un vârf în

arborele deja construit şi celălalt vârf în afara arborelui, iar dintre aceste muchii o vom alge pe cea care

are costul minim. Pentru această operaţie vom actualiza cei trei vectori. Dacă sunt mai multe care oferă

aceeaşi soluţie de cost minim, vom alege una din ele (prima sau ultima, în funcţie de cum se face

compararea), ceea ce înseamnă că nici soluţia nu este unică.

Să exemplificăm câţiva paşi pe următorul graf:

106

La primul pas se va iniţializa ARB[1]=1 (prim); muchia cu costul minim ce pleacă din vârful 1

este (1-2), de cost 12. La al doilea pas se caută muchii care pleacă fie din 1, şi au celălalt capăt diferit

de 2, fie pleacă din 5, şi au celălalt vârf diferit de 1, cu costul minim. În această situaţie sunt 2 muchii,

de cost minim (17), şi anume (1-5) şi (2-3). În funcţie de semnul comparaţiei (< sau <=) va fi selectată

prima sau cea de-a doua muchie, în cazul programului prezentat va fi aleasă muchia (1-5). În acest caz

se va continua cu alegerea unei muchii ce are un vârf în arborele creat (de ramuri: 1-2 şi 1-5) şi un altul

în afară, de cost minim. Se va determina vârful 4, corespunzător muchiei (5-4), de cost 14 (cost minim

dintre variantele rămase: 2-3/ cost 17, 1-3/ 22, 1-4/28). Deci acum arborele este format din ramurile: 1-

5-4, şi 1-2. La ultimul pas avem de ales între muchiile: 3-2 de cost 17, 3-1 de cost 22, şi 3-4 de cost 15.

Ultima este de cost minim şi va fi cea aleasă, astfel că arborele parţial de cost minim este format din

ramurile: 1-5-4-3 şi 1-2. În continuare este prezentat programul pentru a determina arborele parţial de

cost minim.

/* ArbCsMin.c - programul construieste un arbore partial de cost minim

pentru un graf neorientat, utilizand algoritmul lui Prim */

#include <stdio.h>

#include <conio.h>

#include <values.h>




int i, j, k, cost;

clrscr();


scanf("%d", pn);


scanf("%d", pm);

for (i=1; i<= *pn; i++)

for (j=1; j<=*pn; j++)



for (k=1; k<= *pm; k++)

{

printf("Muchie, varfuri sursa, dest: ");

scanf ("%d%d", &i, &j);

printf("\tCost(%d-%d)= ", i, j);

scanf("%d", &cost);

a[j][i]=a[i][j]=cost; // pt. graf neorientat cost (i,j)=cost(j,i)

25

28 22

17

12

1

2

3

5

4

15

14

17

107

}

}

void construct_arb_cost_min (int a[DIMN+1][DIMN+1], int ARB[DIMM+1],

int P[DIMM+1], int C[DIMN+1], int n, int prim){

int k, i, j, cost_min, v1, v2;

for (i=1; i<=n; i++){ // initializare vectori V, P, C cu 0

ARB[i]=0; C[i]=0; P[i]=0;

}

ARB[prim]=1; // initializare varf de inceput

for (k=1; k<=n-1; k++){ // se dermina celalate n-1 varfuri ale arborelui

cost_min=MAXINT;

v1=0; v2=0;

for (i=0; i<=n; i++)

for (j=0; j<=n; j++)

if (ARB[i]==1 && ARB[j]==0)// i e in arbore, iar j nu

if(a[i][j]) // si i-j este muchie in graf cu

if (a[i][j]<cost_min){ // cost minim

cost_min=a[i][j];

v1=i; v2=j; // retin muchia

} // in v1-v2

ARB[v2]=1; // adaug varful de cost minim in arborele ARV

P[v2]=v1; // parintele lui 'v2' este 'v1'

C[v2]=cost_min; // retin costul minim pt v1-v2 in C

}

}

void tip_arb_cost_min (int C[DIMN+1], int P[DIMN+1], int nn){

int i, cm=0;

for (i=2; i<nn; i++){ // tiparim parintele-varful si costul ramurii

printf("%2d -%2d (%d) / ", P[i], i, C[i]);

cm+=C[i];

}

cm+=C[nn];

printf("%2d - %2d (%d)\n\t\tcost minim = %d\n", P[i], i, C[i], cm);

}

void main(){

int a[DIMN+1][DIMN+1]; // matricea de adiacenta (costuri/ drumuri)

int ARB[DIMN+1], C[DIMN+1], P[DIMN+1]; // ARB-arb partial, P-parinti, C-cost

int n, nm, primul, dimV, k;


printf("\nProgramul parcurge in latime graful.\n");

printf("\nSpecificati varful de start pentru parcurgere: ");

scanf("%d", &primul);

construct_arb_cost_min (a, ARB, P, C, n, primul);

printf("\nArborele de cost minim este urmatorul:\n");

tip_arb_cost_min (C, P, n);

printf("\nApasati o tasta pentru a termina programul\n");

getch();

}

108

4.3. Grafuri orientate Un graf orientat este o pereche ordonată de mulţimi (V, M), unde V este mulţimea finită şi

nevidă de vârfuri sau noduri, iar M este o mulţime de perechi ordonate de elemente din V, numite

muchii sau arce. Prin perechi ordonate se înţelege că muchiile sunt diferenţiate prin ordinea de scriere a

vârfurilor, adică arcul (x, y) nu este tot una cu arcul (y, x), cum era în cazul grafurilor neorientate. Ca o

consecinţă şi matricea costurilor (drumurilor) pentru un graf orientat nu mai este simetrică faţă de

diagonala principală (cum este în cazul grafurilor neorientate). Într-un graf orientat avem pentru un arc

dar un nod predecesor (de unde porneşte arcul) şi un nod succesor (unde ajunge arcul respectiv). Dacă

avem un arc (x, x), atunci pleacă din x şi se termină tot în x, şi se numeşte buclă.

Formele de reprezentare a grafurilor orientate sunt aceleaşi ca şi pentru cele orientate: prin

matricea de adiacenţă sau drumuri, prin vector de muchii sau prin lista vecinilor. Dacă în cazul

reprezentării prin matrice, de adiacenţă sau drumuri, diferenţele faţă de graful neorientat au fost

specificate, în cazul reprezentării prin vector de muchii, diferenţa faţă de un graf neorientat constă în

ordinea în care se specifică nodurile (vârfurile) corespunzătoare muchiei (arcului) respectiv: arcul (x, y)

nu este tot una cu arcul (y, x). Dacă folosim pentru reprezentare structura anterioară

(VECTOR_MUCHII) atunci putem nota v1 şi v2 cu vi (vârf iniţial, de pornire a arcului) şi respectiv vf

(vârf final, de terminare arc), şi putem asocia arcului şi costul (lungimea drumului) respectiv.

Definiţiile prezentate pentru grafuri neorientate pot fi extinse şi pentru cele orientate. De

exmplu, un graf orientat este conex dacă oricare ar fi două vârfuri ale sale, există un lanţ care le leagă

(pentru lanţ definiţia este aceeaşi, decât că acum avem un sens de parcurgere al grafului). Un graf

oreintat este tare conex, dacă oricare ar fi două vârfuri ale sale, există un lanţ care le leagă, de la x la y,

precum şi un lanţ de la y la x.

Exemple de probleme ce utilizează grafuri orientate.

1) Se consideră un graf orientat cu n noduri şi m arce; se cere să se determine nodurile izolate

din graf (cele prin care nu trece nici un arc).

/* nodizgrf.c - programul determina toate nodurile izolate dintr-un

graf orientat cu n noduri si m muchii,*/

#include <stdio.h>

#include <conio.h>



typedef struct{

int vi, vf; // cele doua varfuri ale unei muchii

} VECT_MUCHII;

void citire_graf (VECT_MUCHII vm[DIMM+1], int a[DIMN+1][DIMN+1],

int *pn, int *pm){

int i, j, k;

clrscr();

printf("\nDati numar noduri, graf orientat, n: ");

scanf("%d", pn);


scanf("%d", pm);

for (i=1; i<= *pn; i++)

for (j=1; j<=*pn; j++)


109


for (k=1; k<= *pm; k++)

{

printf("Muchia %d, varf initial -> final: ", k);

scanf ("%d%d", &vm[k].vi, &vm[k].vf);

a[vm[k].vi][vm[k].vf]=1; // cost muchie vi-> vf

}

}

void init_nod_iz (int nod_iz[DIMM+1], int nn){

int i;

for (i=1; i<=nn; i++)

nod_iz[i]=0;

}

void determin_nod_iz (int a[DIMN+1][DIMN+1], int nod_iz[DIMN+1], int nn){

int i, j;

for (j=1; j<=nn; j++)

for (i=1; i<=nn; i++)

if (a[i][j])

nod_iz[j]++;

}

void tipar_nod_iz(int nod_iz[DIMM+1], int nn){

int i, ni=0;

printf("\nNoduri izolate:\n");

for (i=1; i<=nn; i++) // tipareste 'noduri izolate'

if (!nod_iz[i]){

printf("%5d", i);

ni++;

}

printf("\n");

if (ni)

printf("Numar de noduri izolate: %d.\n", ni);

else

printf("\tNu sunt noduri izolate.\n");

}

void main()

{


int nod_iz[DIMM+1], a[DIMN+1][DIMN+1]; // noduri izolate, matr. de adiacenta

int n, nm;


init_nod_iz (nod_iz, n);

determin_nod_iz (a, nod_iz, n);

tipar_nod_iz (nod_iz, n);

printf("\n");

}

2) Se consideră un grup format din n persoane, care se cunosc sau nu între ele. Se citesc de la tastatură

perechi de numere întregi (i, j), care înseamnă că persoana i o cunoaşte pe persoana j, fără ca relaţia să

110

fie şi reciprocă. Să determinăm persoana cea mai cunoscută din grup şi persoana care cunoaşte cele mai

multe persoane din grup. Relaţia de “cunoaştere” poate fi reprezentată printr-un graf orientat. Pentru

aceasta este suficient să construim doi vectori, unul cu suma valorilor pe linii (număr de persoane

cunoscute de persoana i) şi altul cu suma valorilor pe coloane (numărul respectiv de persoane cunosc

persoana j). Vom selecta din primul vector maximul, adică persoana cu numărul maxim de cunoştinţe

în grup, şi din cel de-al doilea tot maximul, deci persoana cea mai cunoscută.

3) O companie dispune de un număr de sucursale în teritoriu, iar acestea sunt interconectate prin

drumuri, astfel încât pornind dintr-un punct se pot parcurge toate filialele (pe mai multe rute). Se

doreşte să se renunţe la o parte din aceste filiale pentru a reduce şi costurile cu drumurile. Din acest

punct de vedere se doreşte ca suma totală a drumurilor dintre filialele rămase să fie cuprinsă între două

valori date. Filialele ce rămân vor fi păstrate într-un vector solutie, care va conţine submulţimi ale

grafului iniţial, cu condiţia ca ultima filială din vector să fie identică cu prima (pentru a închide

circuitul) şi suma drumurilor să fie cuprinsă între cele două limite. Pentru a genera toate soluţiile se va

utiliza metoda backtracking, iar dacă se mai pune şi condiţia de optim (minim) se poate determina

soluţia optimă.

/* elimgraf.c - programul elimina noduri dintr-un graf, cu conditia

ca suma drumurilor pentru nodurile ramase sa fie cuprinsa intre

doua limite.

Se considera graf cu n noduri si m muchii, ce reprezinta configuratia

in teritoriu a unei companii impreuna cu sucursalele sale. Sucursalele

sunt interconectate intre ele prin drumuri de lungime data.

Matricea de adiacenta contine costurile (drumurile) intre aceste

filiale. Se doreste renuntarea la un numar de filiale, astfel incat

suma drumurilor intre filialele ramase sa fie cuprinsa intre 2 valori */

#include <stdio.h>

#include <conio.h>



typedef struct{ // cele doua varfuri ale unui arc orientat

int vi, vf; // vi, vf - varfurile initial si final al arcului

} VECT_MUCHII;

int nr_sol=0;

void citire_graf (VECT_MUCHII vm[DIMM+1], int a[DIMN+1][DIMN+1],

int *pn, int *pm){

int i, j, k, drum;

clrscr();


scanf("%d", pn);


scanf("%d", pm);

for (i=1; i<= *pn; i++)

for (j=1; j<=*pn; j++)

a[i][j]=0; // init.(0) matrice drumuri (costuri) pt. graf


for (k=1; k<= *pm; k++)

{

printf("Muchia %d, varf sursa -> destinatie: ", k);

111

scanf ("%d%d", &vm[k].vi, &vm[k].vf);

printf("Cost (%d -> %d)= ", vm[k].vi, vm[k].vf);

scanf ("%d", &drum);

a[vm[k].vi][vm[k].vf]=drum;

}

printf("\nMatricea drumurilor pentru graful introdus este:\n");

for (i=1; i<=*pn; i++){

for (j=1; j<=*pn; j++)

printf("%3d", a[i][j]);

printf("\n");

}

}

void init_solutie (int solutie[DIMM+2], int nm){

int i; // initializeaza solutia cu 0

for (i=1; i<=nm; i++)

solutie[i]=0;

}

int suma_drum_sol(int a[DIMN+1][DIMN+1], int solutie[DIMM+2],

int p, int dmin, int dmax){

int k, suma_drum=0; // drumul total al solutiei determinate

for (k=1; k<p; k++)

suma_drum+=a[solutie[k]][solutie[k+1]];

if (suma_drum >= dmin && suma_drum <= dmax)

return suma_drum; // daca satisface conditia returneaza suma

return 0; // altfel returneaza 0

}

void tipar_solutie(int a[DIMN+1][DIMN+1], int solutie[DIMM+2],

int p, int dmin, int dmax){

int i;

for (i=1; i<p; i++) // tipareste solutia 'p'

printf("%d -> ", solutie[i]);

printf("%d\n\tSuma drumurilor=%d\n", solutie[p],

suma_drum_sol(a, solutie, p, dmin, dmax));

if ((nr_sol+1)%10 == 0){ // s-a afisat un ecran, continua ? -> apasa tasta

printf("\nAfisarea continua dupa apasarea unei taste!\n");

getch();

}

}

int validare_solutie (int a[DIMN+1][DIMN+1], int solutie[DIMM+2], int p){

int k;

if ( !a[solutie[p-1]][solutie[p]] ) // daca nu e drum -> nu e valida solutia

return 0;

for (k=2; k<p; k++) // daca varful mai exista in 'solutia' pana la

if (solutie[k]==solutie[p]) // pozitia 'p-1' -> nu e solutie corecta

return 0; // varful mai poate fi doar pe prima pozitie

return 1;

}

void incerc_solutie(int a[DIMN+1][DIMN+1], int solutie[DIMM+2],

112

int n, int p, int dmin, int dmax){

int i;

for (i=1; i<=n; i++)

{solutie[p]=i; // initializare varf pe pozitia 'p'

if (validare_solutie(a, solutie, p))

if (solutie[1] == solutie[p] && p > 3 && // sol completa ?

suma_drum_sol(a, solutie, p, dmin, dmax))

{tipar_solutie(a, solutie, p, dmin, dmax);

nr_sol++;

}

else

incerc_solutie(a, solutie, n, p+1, dmin, dmax);

solutie[p]=0; // sterge ciclul incercat

}

}

void main(){


int sol[DIMM+2], a[DIMN+1][DIMN+1]; // vect culori si matricea de adiacenta

int n, nm, dmin, dmax;


printf("Limitele pentru suma drumurilor din graf (min, max): ");

scanf("%d%d", &dmin, &dmax);

init_solutie(sol, nm);

printf("\nSolutiile din graf sunt urmatoarele:\n");

incerc_solutie(a, sol, n, 1, dmin, dmax);

if(nr_sol)


else


printf("\n");

}

4) Într-un grup de n persoane, în care nu toate se cunosc între ele (fiecare cunoaşte o parte dintre ele) o

persoană posedă o carte pe care doreşte să o transmită grupului, pentru a fi citită de toţi membrii

grupului. Fiecare persoană poate transmite cartea doar acelor persoane pe care le cunoaşte, după un

anumit interval de timp (zile), ce depinde de persoana căreia urmeză să-i dea cartea, şi care va fi

specificat pentru fiecare succesor. Să se determine o soluţie optimă, dacă există, astfel încât cartea să

trecă pe la fiecare persoană din grup, doar o singură dată, iar în final să revină la posesorul cărţii, după

un timp minim (optim), ştiind că transmiterea cărţii de la o persoană la alta necesită un anumit interval

de timp (de ordinul zilelor, inclusiv timpul necesar pentru lectură). Pentru fiecare transfer al cărţii

(muchie a grafului), de la persoana i la persoana j, se va specifica durata corespunzătoare.

Această problemă este asemănătoare cu precedenta, cu deosebirea că se pleacă dintr-un punct

(nod) dat şi se ajunge în final la acelaşi nod. Arcele grafului vor fi etichetate cu durata necesară

transferului cărţii de la persoana respectivă la succesor.

/* optigraf.c - programul parcurge optim nodurile dintr-un graf,

plecand dintr-un anumit nod, cu un cost (drum) optim.

Avem grup de n persoane, in care nu toate se cunosc intre ele

(fiecare cunoaste o parte dintre ele); o persoana poseda o carte

113

pe care doreste sa o transmita grupului, pentru a fi citita de toti

membrii grupului. Fiecare persoana poate transmite cartea doar acelor

persoane pe care le cunoaste. Fiecare persoana citeste si da cartea

intr-un anumit interval de timp (zile), ce depinde de persoana

careia urmeaza sa-i dea cartea, si care va fi specificat pentru

fiecare succesor.

Sa se determine o solutie optima, daca exista, astfel incat cartea sa

treca pe la fiecare persoana din grup, doar o singura data, iar

in final sa ajunga la posesorul cartii, astfel incat timpul dupa

care cartea revine la proprietar sa fie minim (optim).

Programul afiseaza toate solutiile, dar o retine pe cea optima. */

#include <stdio.h>

#include <conio.h>

#include <values.h>



typedef struct{ // cele doua varfuri ale unui arc orientat

int vi, vf; // vi, vf - varfurile initial si final al arcului

int timp; // timpul necesar pentru a citi cartea

} VECT_MUCHII;

int nr_sol=0, nr_sol_op=0, sol_optima[DIMM+1];

void citire_graf (VECT_MUCHII vm[DIMM+1], int a[DIMN+1][DIMN+1], int *pn){

int i, j, k, durata, pers, np;

clrscr();


scanf("%d", pn);

for (i=1; i<= *pn; i++)

for (j=1; j<=*pn; j++)

a[i][j]=0; // init.(0) matrice drumuri (costuri) pt. graf

printf("\nCitire graf prin varfurile (persoanele) sale.\n");

for (k=1; k<= *pn; k++)

{vm[k].vi=k;

printf("Numarul de persoane cunoscute de persoana (%d): ", k);

scanf("%d", &np);

for (i=1; i<=np; i++){

printf("\tcunostinta(%d): ", i);

scanf("%d", &pers);

vm[k].vf=pers;

printf("\t\ttransferul %d -> %d dureaza (zile): ", k, pers);

scanf("%d", &durata);

a[vm[k].vi][vm[k].vf]=durata;

}

vm[k].timp=durata;

}

printf("\nMatricea costurilor pentru graful introdus este:\n");

for (i=1; i<=*pn; i++){

for (j=1; j<=*pn; j++)

printf("%3d", a[i][j]);

printf("\n");

114

}

}

void init_solutie (int solutie[DIMM+1], int nn){

int i; // initializeaza solutia cu 0

for (i=1; i<=nn; i++)

solutie[i]=0;

}

int timp_sol(int a[DIMN+1][DIMN+1], int solutie[DIMM+1], int p){

int k, total_timp=0; // timpul total al solutiei determinate

for (k=1; k<p; k++)

total_timp+=a[solutie[k]][solutie[k+1]];

total_timp+=a[solutie[p]][solutie[1]];

return total_timp;

}

void tipar_solutie(int a[DIMN+1][DIMN+1], int solutie[DIMM+1], int p){

int i;

for (i=1; i<=p; i++) // tipareste solutia 'p'

printf("%d -> ", solutie[i]);

printf("%d\t/timp total=%d/ solutie %d\n\n", solutie[1],

timp_sol(a, solutie, p), nr_sol+1);

if ((nr_sol+1)%10 == 0){ // s-a afisat un ecran, continua ? -> apasa tasta

printf("\nAfisarea continua dupa apasarea unei taste!\n");

getch();

}

}

int validare_solutie (int a[DIMN+1][DIMN+1], int solutie[DIMM+1], int p){

int k;

if ( !a[solutie[p-1]][solutie[p]] ) // nu e legatura -> nu e valida solutia

return 0;

for (k=1; k<p; k++) // daca varful mai exista in 'solutia' pana la

if (solutie[k]==solutie[p]) // pozitia 'p-1' -> nu e solutie corecta

return 0;

return 1;

}

void copie_sol_optima(int solutie[DIMM+1], int sol_optima[DIMM+1], int nn){

int i;

for (i=1; i<=nn; i++)

sol_optima[i]=solutie[i];

}

void incerc_solutie(int a[DIMN+1][DIMN+1], int solutie[DIMM+1],

int n, int p, int varf_init, int *poptim){

int i;

for (i=1; i<=n; i++)

{solutie[p]=i; // initializare varf pe pozitia 'p'

if (validare_solutie(a, solutie, p))

if (p==n && a[solutie[p]][solutie[1]] && // sol completa ?

varf_init==solutie[1])

{tipar_solutie(a, solutie, p);

115

if (timp_sol(a, solutie, p) < *poptim){

copie_sol_optima(solutie, sol_optima, n);

*poptim=timp_sol(a, solutie, p);

nr_sol_op=nr_sol+1; // numarul sol optime

}

nr_sol++; // contor numar solutii

}

else

incerc_solutie(a, solutie, n, p+1, varf_init, poptim);

solutie[p]=0; // sterge varful incercat

}

}

void main(){


int sol[DIMM+1], a[DIMN+1][DIMN+1]; // vect solutie si matricea de adiacenta

int i, n, varf_ini, optim=MAXINT;

citire_graf (vm, a, &n);

printf("Varful initial (persoana de pornire): ");

scanf("%d", &varf_ini);

init_solutie(sol, n);

printf("\nSolutiile din graf sunt urmatoarele:\n");

incerc_solutie(a, sol, n, 1, varf_ini, &optim);

if(nr_sol)

{printf("\nNumarul total de solutii este: %d\n", nr_sol);

printf("\nSolutia optima este:\n");

for (i=1; i<=n; i++) // tipareste solutia optima

printf("%d -> ", sol_optima[i]);

printf("%d\t/timp total=%d/ solutie %d\n\n", sol_optima[1],

timp_sol(a, sol_optima, n), nr_sol_op);

}

else


printf("\n");

}

116

4.4. Determinarea celor mai scurte drumuri într-un graf Fie G = <V, M> un graf orientat, unde V este mulţimea vârfurilor şi M este mulţimea

muchiilor. Fiecărei muchii i se asociază o lungime (valoare pozitivă). Dorim să calculăm lungimea

celui mai scurt drum între fiecare pereche de varfuri.

Vom presupune ca vârfurile sunt numerotate de la 1 la n şi că matricea L dă lungimea fiecarei

muchii: L[i, i] = 0, L[i, j] >= 0 pentru i <> j, L[i, j] = +∞ dacă muchia (i, j) nu există. Principiul

optimalităţii este: dacă cel mai scurt drum de la i la j trece prin vârful k, atunci porţiunea de drum de la

i la k, cât şi cea de la k la j, trebuie să fie, de asemenea, optime.

Construim o matrice D care să conţină lungimea celui mai scurt drum între fiecare pereche de

vârfuri. Algoritmul de programare dinamică iniţializează pe D cu L. Apoi, efectuează n iteraţii. Dupa

iteraţia k, D va conţine lungimile celor mai scurte drumuri care folosesc ca vârfuri intermediare doar

vârfurile din {1, 2, ..., k}, iar dupa n iteraţii, obtinem rezultatul final. La iteraţia k, algoritmul trebuie să

verifice, pentru fiecare pereche de varfuri (i, j), dacă există sau nu un drum, ce trece prin varful k, care

este mai bun decât drum optim actual, ce trece doar prin varfurile din {1, 2, ..., k-1}. Fie Dk matricea D

dupa iteratia k. Verificarea necesară este atunci:

Dk[i, j] = min(Dk-1[i, j], Dk-1[i, k] + Dk-1[k, j])

S-a considerat că un drum optim care trece o dată prin k nu poate trece de două ori prin k.

Acest algoritm simplu este datorat lui Floyd (1962).

D=L

for (k=1; k<=n; k++)

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

if ( D[i][k] + D[k][j] < D[i][j] )

D[i][j] = D[i][k] + D[k][j];

Se deduce că algoritmul lui Floyd necesită un timp în O(n3). Un alt mod de a rezolva această

problemă este să aplicăm algoritmul Dijkstra de n ori, alegând mereu un alt vârf sursă. Se obţine un

timp în n O(n2), adica tot în O(n

3). Algoritmul lui Floyd, datorită simplităţii lui, are însă constanta

multiplicativă mai mică, fiind probabil mai rapid în practică. Dacă folosim algoritmul Dijkstra-

modificat în mod similar, obţinem un timp total în O(max(mn, n2) log n), unde m = număr muchii M.

Dacă graful este rar, atunci este preferabil să aplicăm algoritmul Dijkstra-modificat de n ori; dacă

graful este dens (m n2), este mai bine sa folosim algoritmul lui Floyd.

De obicei, dorim să aflăm nu numai lungimea celui mai scurt drum, dar şi traseul său. În acestă

situaţie, vom construi o a doua matrice P, iniţializată cu zero. Bucla cea mai interioară a algoritmului

devine

if ( D[i][k] + D[k][j] < D[i][j] )

{D[i][j] = D[i][k] + D[k][j];

P[i][j] = k; }

Când algoritmul se opreşte, P[i][j] va conţine vârful din ultima iteraţie care a cauzat o

modificare în D[i][j]. Pentru a afla prin ce vârfuri trece cel mai scurt drum de la i la j, testăm elementul

P[i][j]. Dacă P[i][j] = 0, atunci cel mai scurt drum este chiar muchia (i, j). Dacă P[i][j] = k, atunci cel

mai scurt drum de la i la j trece prin k şi urmează să testăm recursiv elementele P[i][k] şi P[k][j] pentru

a găsi şi celelalte vârfuri intermediare.

În continuare este prezentat întreg programul pentru acest algoritm.

/* Floyd.c - programul determina cele mai scurte drumuri dintr-un graf,

utilizand algoritmul Floyd (sau Djikstra modificat),

care poate fi aplicat atat pentru grafuri orientate cat si pentru

117

cele neorientate (se elimina linia care face simetrica matricea

drumurilor, din functia de citire graf). */

#include <stdio.h>

#include <conio.h>

#include <values.h>

#define DIM 6

int D[DIM+1][DIM+1], P[DIM+1][DIM+1], t[DIM+1];

int i, j, k, n, nm, sursa, dest;

char rasp[10];

void main(){

clrscr();

printf("\nDati numar noduri graf, n: ");

scanf("%d", &n);


scanf("%d", &nm);

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

{D[i][j]=0; // initializare matrice drumuri (costuri) pt. graf

P[i][j]=0; // initializare predecesori

}

printf("Se citeste graful prin muchii, nod sursa, dest, si costul asociat.\n");

for (k=1; k<=nm; k++){

printf("Muchiile sursa, dest: ");

scanf ("%d%d", &i, &j);

printf("Cost(%d,%d): ", i, j);

scanf("%d", &D[i][j]); // daca graful e orientat se elimina linia urmatoare

D[j][i]=D[i][j]; // pt. graf neorientat costul (i,j)=cost(j,i)

}

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

if (D[i][j]==0) // initializare costuri pentru noduri fara

D[i][j]=1000; // legaturi (o valoare foarte mare)

else // initializare predecesor nod 'j'

P[i][j]=i; // cu nodul liniei (precedent) 'i'

for (k=1; k<=n; k++) // algoritmul Floyd de determinare a drumului minim

for (i=1; i<=n; i++) // intre doua noduri 'i' si 'j'

for (j=1; j<=n; j++) // se verifica toate cazurile i->k->j

if (i != j && D[i][j] > D[i][k]+D[k][j])

{ // daca se determina un k pt. care distanta

D[i][j]=D[i][k]+D[k][j];// este minima

P[i][j]=P[k][j]; // se actualizeaza distanta

} // si se retine nodul precedent lui j

for (i=1; i<=n; i++){ // afisare matrice distante (costuri)

for (j=1; j<=n; j++)

printf("%5d", D[i][j]);

printf("\n");}

do {

printf("\nDoriti distanta (costul) intre doua noduri (da/nu)? ");

fflush(stdin); // golire buffer tastatura

118

gets(rasp);

if (rasp[0]!='d' && rasp[0]!='D')

{fflush(stdin);

printf("\nApasati o tasta pentru a termina programul !\n");

getch();

exit(1);

}

printf("Drumul (costul) intre nodurile sursa, destinatie: ");

scanf("%d%d", &sursa, &dest);

k=dest;

i=0;

while (P[sursa][k] && P[sursa][k] != sursa)

{ // se determina lantul de invers succesori, de la dest

t[++i]=k; // la sursa, cu cond. sa existe conexiunea

k=P[sursa][k]; // sursa-k, si continua pana ajunge k la sursa

}

t[++i]=k;

t[++i]=sursa;

printf("Drumul (%d->%d): ", sursa, dest);

for (j=i; j>0; j--)

{

if (j!=1) printf("%2d -> ", t[j]);

else printf("%2d.", t[j]);

}

printf("\tcost: %d\n", D[sursa][dest]);

} while (rasp[0]=='d' || rasp[0]=='D');

}

Date post:	08-Jul-2016
Category:	Documents
Upload:	andy-cioacata
View:	216 times
Download:	2 times

SDA_c4

Documents