Parcurgerea grafurilor neorientate

Parcurgerea grafurilor neorientate

Asa cum arata si denumirea, 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 si este efectuata cu scopul prelucrarii informatiei asociata varfurilor.

Deoarece graful este o structura neliniara de organizare a datelor, prin parcurgerea sa, in mod sistematic se realizeaza si o aranjare lineara a varfurilor sale, deci informatiile stocate in varfuri se pot regasi si prelucra mai usor.

Pentru a facilita scrierea, convenim ca in lc de sa se scrie , fora ca valabilitatea rezultatelor sa fie diminuata. Astfel, prin similitudine, se poate folosii drept relatie de ordine intre varfurile grafului, relatia de ordine din numerele naturale (notata cu "<").

Cele mai cunoscute metode de parcurgere a unui graf sunt parcurgerea BF ("in latime") si parcurgerea DF ("in adancime") fiind prezentate in continuare .

1. Metoda de parcurgere BF (Breath First - "in latime"). Se viziteaza intai varful initial, apoi vecinii acestuia, apoi vecinii nevizitati ai acestora, s.a.m.d.

Vizitarea unui varf inseamna de fapt o anumita prelucrare specificata asupra varfului respectiv, insa in acest moment este importanta intelegerea problemelor legate de parcurgerea unui graf prin metoda BF, deci se va insista doar asupra acestui aspect.

Derularea algoritmului presupune alegerea, la un moment dat, dintre toti vecinii unui varf, pe acela ce nu a fost vizitat. Acest lucru este posibil prin folosirea unui vector VIZITAT de dimensiunea n, ale carui componente se definesc astfel:

pentru ∀k:1, daca varful k a fost vizitat

VIZITAT[k] =

0, in caz contrar.

Se foloseste o structura de tip coada (simulata in alegerea statica printr-un vector V) in care prelucrarea unui varf aflat la un capat al cozii (varful cozii) consta in introducerea in celalalt capat al ei (coada cozii) a tuturor varfurilor j vecine cu k, nevizitate, inca. Evident, pentru inceput, k este egal cu varful indicat initial i si toate componentele lui VIZITAT sunt zero.

Algoritmul consta in urmatorii pasi:

Pasul 1. Se prelucreaza varful initial k:

Pasul 1.1 Se adauga varful k in coada;

Pasul 1.2 Varful k se considera vizitat

Pasul 2. Cat timp coda este nevida se executa:

Pasul 2.1 Pentru toti vecinii j nevizitati inca ai varfului k, executa:

Pasul 2.1.1 Se adauga varful j in coada; Pasul 2.1.2 Varful j se considera vizitat ;

Pasul 2.2 Se reia de la pasul 2.1

Se doreste parcurgerea sa incepand cu varful 1. s-a marcat cu linii punctate ordinea de vizitare a varfurilor. Pentru aceasta se executa pasii:

• Se adauga in coada varful 1(varful initial);coada contine: 1;
• Se analizeaza varful 1 (ca prim element al cozii):
• Se adauga in coada vecinii sai (nevizitati) 2, 3, 4; coada contine:1, 2, 3, 4;
• Se trece pe nivelul urmator:
• Se analizeaza varful 2 (ca element curent al cozii);
• Se adauga in coada vecinii sai (nevizitati): 5;coada contine:1, 2, 3, 4, ,5;
• Se trece pe nivelul urmator;
• Se analizeaza varful 3 (ca element curent al cozii):

o      Se adauga in coada vecinii sai(nevizitati):6; coada contine 1,2,3,4,5,6;

o      Se trece pe nivelul urmator;

• Se analizeaza varful 4 (ca element curent al cozii):
• Vecinii varfului 4 (varful 6) sunt deja vizitati; coada contine 1,2,3,4,5,6;
• Se trece pe nivelul urmator;
• Se analizeaza varful 5 (ca element al cozii):
• Vecinii sai (nevizitati) se adauga in coada: 7; coada contine 1,2,3,4,5,6,7
• Se trece pe nivelul urmator;
• Se analizeaza varful 6 (ca element curent al cozii):
• Se adauga in coada vecinii sai (nevizitati): 8; coada contine 1,2,3,4,5,6,7,8
• Se trece pe nivelul urmator;
• Se analizeaza varful 7 (ca element curent al cozii):
• Vecinii varfului 7 (varful 8)sunt deja vizitati; coada contine 1,2,3,4,5,6,7,8
• Se trece pe nivelul urmator;
• Se analizeaza varful 8 (ca element curent al cozii):
• Vecinii varfului 8 (varful 8) sunt deja vizitati; coada contine 1,2,3,4,5,6,7,8;
• Se trece pe nivelul urmator;
• Toate elementele cozii au fost tratate;
• Se afiseaza continutul cozii: 1,2,3,4,5,6,7,8, ceea ce indica succesiunea de varfuri rezultata din parcurgerea acestui graf folosind metoda BF.

2.Metoda de parcurgere DF. (Deph First - "in adancime")

Parcurgerea unui graf in acest mod este o problema specifica metodei de rezolvare backtracking. Pentru rezolvarea practica a acestei probleme se foloseste un vector VIZITAT definit ca si la metoda BF; insa in locul cozii se va folosii o stiva (simulata in alocare statica printr-un vector V). astfel, in orice moment, exista posibilitatea de a ajunge de al varful curent la primul dintre vecinii sai nevizitati inca acesta fiind plasat in varful stivei. Cu acest varf se continua in acelasi mod. In vectorul URM se determina, la fiecare pas, urmatorul mod ce va fi vizitat dup nodul k (cand acesta exista). Pentru al determina, se parcurge linia k din matricea de adiacenta A asociata grafului, incepand cu urmatorul, pana se gaseste un vecin j al lui, nevizitat inca.

Daca este gasit, se incarca in varful stivei si se mareste corspunzator "pointerul de stiva" p. Daca sunt mai multi vecini, se alege acela care are cel mai mic numar de ordine (pentru ca denumirea de "radacina" sa aiba sens).

Daca nu se poate determina un astfel de varf, se coboara in stiva (p se micsoreaza cu 1), incercand sa aplicam procedeul urmatorului element al stivei.

Folosind o structura de tip stiva, prelucrarea unui varf aflat la un capat al stivei (varful stivei), consta in introducerea in acelasi capat al ei, a tuturor varfurilor j vecine cu k, nevizitate inca. Evident, pentru inceput, k este egal cu varful indicat initital i.

Algoritmul consta in urmatorii pasi:

Pasul 1. Se adauga varful k in stiva si se afiseaza;

Pasul 2. Se analizeaza varful k:

Pasul 2.1 Se cauta primul dintre vecini sai nevizitati, cu numar >k;

Pasul 2.1.1 Daca exista (fie acesta j), se adauga in stiva varful j si se afiseaza;

Pasul 2.1.2 Daca nu exista, se coboara in stiva; fie j continutul corespunzator al stivei;

Pasul 2.2 varful j devine varful ce trebuie analizat ;

Pasul 3. Cat timp stiva este nevida se executa pasul 2.

➊

Se considera urmatorul graf: ➋ ➌ ➍

➎ ➏

➐ ➑

Se doreste parcurgerea sa incepand cu varful 1. S-a marcat cu sageti punctate ordinea de vizitare a varfurilor.

Pentru aceasta se executa pasii:

• adauga in stiva varful 1 (varful initial); stiva contine: 1;
• se afiseaza varful 1;
• se analizeaza varful 1 (ca prim element al stivei):

o      se determina primul dintre vecinii sai: 2;

o      se adauga in stiva varful 2, si se afiseaza ; stiva contine: 1,2;

• se analizeaza varful 2 (ca element curent al stivei):

o      se determina primul dintre vecinii sai: 5;

o      se adauga in stiva varful 5 si se afiseaza: stiva contine: 1,2,5;

• se analizeaza varful 5 (ca element curent al stivei):

o      se determina primul dintre vecinii sai: 7;

o      se adauga in stiva varful 7 si se afiseaza; stiva contine: 1,2,5,7;

• se analizeaza varful 7 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati, cu numar >7;

o      nu exista; se coboara in stiva; stiva contine: 1,2,5;

• se analizeaza varful 5 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati, cu numar >5;

o      nu exista; se coboara in stiva; stiva contine: 1,2;

• se analizeaza varful 2 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati, cu numar >2;

o      nu exista; se coboara in stiva; stiva contine: 1;

• se analizeaza varful 1 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati, cu numar>1: 3;

o      se adauga in stiva varful 3; se afiseaza varful 3; stiva contine: 1,3;

• se analizeaza varful 3 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati, cu numarul>3: 6;

o      se adauga in stiva varful 6; se afiseaza varful 6; stiva contine:1,3,6;

• se analizeaza varful 6 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati, cu numar>6: 8;

o      se adauga in stiva varful 8;se afiseaza varful 8; stiva contine: 1,3,6,8;

se analizeaza varful 8 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati, cu numar>8;

o      nu exista; se coboara in stiva; stiva contine:1,3,6;

se analizeaza varful 6 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati, cu numarul>6;

o      nu exista; se coboara in stiva; stiva contine: 1,3;

• se analizeaza varful 3 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati cu numar>3;

o      nu exista; se coboara in stiva; stiva contine: 1;

• se analizeaza varful 1 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai cu numar>1: 4;

o      se adauga in stiva si se afiseaza; stiva contine:1,4;

• se analizeaza varful 4 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati, cu numar>4;

o      nu exista; se coboara in stiva; stiva contine:1,4;

• se analizeaza varful 1 (ca element curent al stivei):

o      se cauta primul dintre vecinii sai nevizitati, cu numar>1;

o      nu exista; se coboara in stiva; stiva este vida.

Succesiunea de varfuri afisata, 1,2,5,7,3,6,8,4 indica succesiunea de varfuri rezultata din parcurgerea acestui graf folosind metoda DF.