Parcurgerea grafurilor
Pentru parcurgerea grafurilor există următoarele două metode:
1. Parcurgerea în lăţime – Breadth first (BF).
1. Parcurgerea în lăţime – Breadth first (BF).
2. Parcurgerea în adâncime – Depth First (DF).
Parcurgerea în lăţime – Breadth first (BF), implementarea foloseste o coada de aşteptare c si vectorul nodurilor vizitate
Complexitatea algoritmului de parcurgere în lăţime -este liniară, de ordinul
O(m+n).
Aplicatie :
1. Prieteni3
Într-o reţea de socializare cu n membri sunt cunoscuţi prietenii fiecărei persoane. Pentru o persoană precizată A şi pentru un număr natural dat k, determinaţi toate persoanele din reţea care, în raport cu persoana A, au rangul egal cu k. Vor primi rangul k toate persoanele din reţea care au cel puţin un prieten în Pk-1 dar nu au prieteni în nici una dintre multimileP0, P1, …,Pk-2.
Rangul celor n persoane este memorat într-un vector rang cu n componente. Pentru a afla rangul fiecărei persoane în raport cu persoana A parcurgem graful în adâncime. De fiecare dată când adăugăm în coadă toți vecinii nodului aflat în primul nod al cozii, rangul lor va fi egal cu rangul acelui nod, plus unu. Rangul lui A este 0, rangul tuturor vecinilor lui A este egal cu 1, rangul vecinilor vecinilor lui A este 2, ș.a.m.d.
Persoanele care vor primi rangul k au cel puţin un prieten în Pk-1 dar nu au prieteni în nici una dintre multimile P0, P1, …,Pk-2 deoarece aceștia din urmă au fost deja vizitați și nu mai pot fi adăugați în coadă.
Aplicatie :
1. Prieteni3
Într-o reţea de socializare cu n membri sunt cunoscuţi prietenii fiecărei persoane. Pentru o persoană precizată A şi pentru un număr natural dat k, determinaţi toate persoanele din reţea care, în raport cu persoana A, au rangul egal cu k. Vor primi rangul k toate persoanele din reţea care au cel puţin un prieten în Pk-1 dar nu au prieteni în nici una dintre multimileP0, P1, …,Pk-2.
Rangul celor n persoane este memorat într-un vector rang cu n componente. Pentru a afla rangul fiecărei persoane în raport cu persoana A parcurgem graful în adâncime. De fiecare dată când adăugăm în coadă toți vecinii nodului aflat în primul nod al cozii, rangul lor va fi egal cu rangul acelui nod, plus unu. Rangul lui A este 0, rangul tuturor vecinilor lui A este egal cu 1, rangul vecinilor vecinilor lui A este 2, ș.a.m.d.
Persoanele care vor primi rangul k au cel puţin un prieten în Pk-1 dar nu au prieteni în nici una dintre multimile P0, P1, …,Pk-2 deoarece aceștia din urmă au fost deja vizitați și nu mai pot fi adăugați în coadă.
2. grafxy
Fie un graf neorientat conex cu N vârfuri (numerotate de la 1 la N) şi M muchii. Se consideră de asemenea două mulţimi nevide X şi Y de vârfuri din acest graf, mulţimi care nu au vârfuri comune. Lungimea unui lanţ de la un vârf v1 la un vârf v2 este dată de numărul de muchii ale lanţului. Definim distanţa de la un vârf v la mulţimea Y ca fiind lungimea minimă a unui lanţ de la vârful v la un vârf din mulţimea Y.
Să se determine distanţa de la orice vârf din mulţimea X la mulţimea Y.
Soluţie: Utilizam parcurgerea BF, în care inițial punem in coadă toate varfurile din mulțimea Y. În vectorul d de lungime n, în care inițial d[Y[i]] = 0, se calculează distanța de la un vârf din Y la oricare alt varf.Distanțele se gasesc după BF în d[X[i]], pentru i=1..nx.
Complexitate algoritmului este O(m + n).
Fie un graf neorientat conex cu N vârfuri (numerotate de la 1 la N) şi M muchii. Se consideră de asemenea două mulţimi nevide X şi Y de vârfuri din acest graf, mulţimi care nu au vârfuri comune. Lungimea unui lanţ de la un vârf v1 la un vârf v2 este dată de numărul de muchii ale lanţului. Definim distanţa de la un vârf v la mulţimea Y ca fiind lungimea minimă a unui lanţ de la vârful v la un vârf din mulţimea Y.
Să se determine distanţa de la orice vârf din mulţimea X la mulţimea Y.
Soluţie: Utilizam parcurgerea BF, în care inițial punem in coadă toate varfurile din mulțimea Y. În vectorul d de lungime n, în care inițial d[Y[i]] = 0, se calculează distanța de la un vârf din Y la oricare alt varf.Distanțele se gasesc după BF în d[X[i]], pentru i=1..nx.
Complexitate algoritmului este O(m + n).
3. Programul naţional de televiziune este transmis în ţară prin intermediul unui sistem de relee. Semnalul porneşte din releul 7 şi se transmite din oraş în oraş ca în harta de mai jos. Din cauza condiţiilor meteo nefavorabile s-a constatat o avarie a releelor ce transmit în zonele afectate de furtună. Să se indice zonele care încă mai recepţionează postul de televiziune.
Soluție: Se parcurge subgraful obținut prin eliminarea releelor din zonele afectate de furtună, începând cu releul 7. Releele care primesc semnalul sunt cele aflate în coadă prin această parcurgere. De exemplu, dacă este afectat releul din zona 10 atunci cel din zona 9 nu mai primește semnal și toate celelalte vor primi semnalul.
Parcurgerea în adâncime – Depth First (DF)
Parcurgerea în adâncime a unui graf G, neorientat și conex, asociază lui G un arbore parțial.
Parcurgerea în adâncime a unui arbore, pornind din rădăcină, are ca efect parcurgerea în preordine a arborelui.
Parcurgerea în adâncime a unui arbore, pornind din rădăcină, are ca efect parcurgerea în preordine a arborelui.
Implementarea algoritmului foloseste o stiva st si vectorul nodurilor vizitate:
Complexitatea algoritmului de parcurgere în adâncime -este liniară, de ordinul O(m+n).
Aplicații: Parcurgerea în adâncime a fost formulată cu mult timp în urmă ca o tehnică de explorare a unui labirint. O persoană care caută ceva într-un labirint și aplică această tehnică are avantajul că “următorul loc în care caută” este mereu foarte aproape.
Aplicații: Parcurgerea în adâncime a fost formulată cu mult timp în urmă ca o tehnică de explorare a unui labirint. O persoană care caută ceva într-un labirint și aplică această tehnică are avantajul că “următorul loc în care caută” este mereu foarte aproape.