Parcurgerea grafurilor
1. Parcurgerea în lăţime (BF - Breadth First)
Principiul: se vizitează întâi vârful iniţial, apoi vecinii acestuia, apoi vecinii nevizitaţi ai acestora… Parcurgerea este o parcurgere pe nivele ale nodurilor din graf.
Prin vizitarea unui vârf înţelegem de fapt o anumită prelucrare asupra vârfului respectiv.
Prin vecinul nodului x înţelegem un nod y care este adiacent cu x, adică există o muchie între x şi y.
Algoritmul constă în alegerea, la un moment dat, dintre toţi vecinii unui vârf, pe acela ce nu a fost încă vizitat. Acest lucru este posibil prin folosirea unui vector V cu n componente care se defineşte astfel:
Se foloseşte o structură de tip coada (simulată în alocarea statică printr-un vector V) în care prelucrarea unui vârf k aflat la un capăt al cozii (vârful cozii), consta în introducerea în celălalt capăt al ei (coada cozii), a tuturor vârfurilor j vecine cu k, nevizitate încă. Pentru început, k este vârful indicat iniţial - p şi toate componentele lui V sunt 0.
Algoritmul constă în urmatorii paşi:
1) se prelucrează vârful iniţial k;
- se adauga varful k in coada;
- varful k se considera vizitat;
2) cât timp coada este nevida se execută:
- pentru toţi vecinii j nevizitaţi încă ai vârfului k, execută:
- se adaugă vârful j în coadă;
- vârful j se consideră vizitat V[j]=1;
- vârful j devine vârful k
3) se afiseaza continutul cozii.
Presupunând că plecăm cu parcurgerea începând cu nodul 1.
Introducem pe 1 în coadă. Vecinii lui 1 nevizitaţi sunt 2şi 5.
Îi introducem şi pe aceştia în coadă. Până în acest moment coada arată astfel: C=[1,2,5]. 1 nu mai are vecini nevizitaţi şi începem să căutăm vecinii nevizitaţi ai lui 2.
Îl găsim pe 3 şi-l introducem în coadă C=[1,2,5,3].
Nu mai avem vecini nevizitaţi ai lui 2, căutăm vecinii lui 5 (nu găsim).
Căutăm vecinii nevizitaţi ai lui 3. Găsim nodul 4 şi-l introducem în coadă: C=[1,2,5,3,4].
Căutăm apoi vecinii nevizitaţi ai lui 4 (nu găsim).
Scriem conținutul cozii: 1,2,3,5,4
Algoritmul de parcurgere in adancime (DF - Depth First)
În cazut algoritmului de parcurgere în adâncime DF se va folosi o stivă în care adăugarea şi eliminarea elementelor se face la acelaşi capăt, numit capul stivei. Eliminarea elementelor se va face în ordinea inversa introducerii lor, la orice moment putând fi eliminat ultimul element introdus.
Metoda consta în:
- alegem un vârf de pornire, pentru acesta se alege primul vecin al său nevizitat încă, pentru acest vecin căutăm primul vecin al său nevizitat şi ş.a.m.d. În cazul în care un vârf nu mai are vecini nevizitaţi atunci ne întoarcem la nodul anterior, iar pentru acel nod căutăm următorul vecin nevizitat al său.
Folosim un vector V cu n elemente, cu ajutorul căruia se marchează nodurile deja vizitate pentru a evita trecerea de mai multe ori prin acelaşi nod. Cu alte cuvinte V [j] = 1 daca nodul j a fost deja vizitat şi V[j] = 0 în caz contrar. Vom spune despre un nod i că a fost explorat dacă are toate nodurile adiacente vizitate.
subprogram Parcurgere_in_adancime(i)
vizităm nodul i
pentru toate varfurile k adiacente cu varful i executa
daca varful k este neparcurs atunci apel parcurgere_in_adancime(k)
Ieşirea din recursivitate se produce în momentul în care nu se mai găsesc vârfuri neparcurse adiacente cu vârfurile parcurse deja. Este posibil ca după un apel al procedurii începând cu un anumit vârf i să rămână în graf vârfuri neparcurse. În această situaţie apelul procedurii se repetă pentru un alt vârf iniţial (dintre vârfurile neparcurse) până la parcurgerea tuturor nodurilor grafului.
