Parcurgerea in latime a grafurilor

Parcurgerea unui graf neorientat indica posibilitatea de a ajunge o singura data in fiecare varf al grafului, pornind de la un varf dat “xk” si parcurgand muchii adiacente. Aceasta operatiune poarta numele de vizitare sau traversare a varfurilor grafului si este efectuata cu scopul prelucrarii informatiei asociata varfurilor.Deoarece graful este o structura neliniara de organizare a datelor, prin parcurgerea sa in mod systematic se realizeaza si o aranjare liniaraq a varfurilor sale, deci informatiile stocate in varfuri se pot regasi si prelucra mai usor. Pentru a facilita scrierea, convenim ca in loc de {x1,x2,…, xn} sa se scrie {1,2,…,n}, fara ca valabilitatea rezultatelor sa fie diminuata. Astfel, prin similitudine, se poate folosi drept relatie de ordine intre varfurile grafului, relatia de ordine din numerele naturale (notata cu “<”).Metoda de parcurgere BFNumele provine din limba engleza (Breadth First-“in latime”) si principiul este: se viziteaza intai varful initial, apoi vecinii acestuia, apoi vecinii nevizitati ai acestora, si asa mai departe.Vizitarea unui varf inseamna de fapt o anumita prelucrare specificata asupra varfului respectiv.Derularea algoritmului presupune alegerea, la un moment dat, dintre toti vecinii unui varf, pe acela ce nu a fost inca vizitat. Acest lucru este posibil prin folosirea unui vector VIZITAT de dimensiune n, ale carui componente se definesc astfel: pentru ( k({1,2,3,…,n}:VIZITAT[k] ( 1, daca varful k a fost vizitat( 0, in caz contrar Se foloseste o structura de tip coada (simulata in alocare statica printr-un vector V) in care prelucrarea unui varf k aflat la un capat al cozii (varful cozii), consta in introducerea in celalat capat al ei (coada cozii), a tuturor varfurilor j vecine cu k, nevizitate inca. Pentru inceput, k este egal cu varful indicat initial i si toate componentele lui VIZITAT sunt zero.Algoritmul consta in urmatorii pasi:se prelucreaza varful initial k;se adauga varful k in coada;varful k se considera vizitat;cat timp coada este nevida se executa:pentru toti vecinii j nevizitati inca ai varfului k, executa:se adauga varful j in coada;varful j se considera vizita;varful j devine varful k;3) se afiseaza continutul cozii;