Metode si Tehnici de programare - limbajul C++
Adrian Runceanu
Capitolul 5
A. Consideratii teoretice
Definitie. Numim graf o pereche de multimi G=(V, E), unde V - reprezinta multimea varfurilor din graf, iar E - reprezinta multimea muchiilor din graf.
La curs s-au prezentat modalitatile de reprezentare a unui graf neorientat. Acum prezentam doua modalitati de parcurgere.
1. Parcurgerea in latime(parcurgere BF - BREATH FIRST), care consta in a "vizita" varful initial i, apoi vecinii acestuia, apoi vecinii nevizitati ai acestora s.a.m.d.
Pentru constructia algoritmului, atunci cand avem de ales dintre toti vecinii unui varf, pe acela nevizitat inca trebuie sa folosim un vector numit VIZ care are n elemente astfel:
VIZ[i]=1 daca varful i a fost vizitat
VIZ[i]=0 daca varful i nu a fost vizitat
Initial se considera ca nici un nod nu este vizitat, inca. Rezolvarea problemei se bazeaza pe folosirea unei cozi C, in care prelucrarea unui varf v aflat la un capat al cozii consta in introducerea in celalalt capat al ei a tuturor varfurilor i vecine cu v, nevizitate inca.
Exemplu: Pentru graful din figura urmatoare, ordinea de parcurgere BF a varfurilor, plecand de la nodul 1 este : 1, 2, 3, 4, 5, 6, 7, 8.
2. Parcugerea in adancime(parcurgere DF - DEEP FIRST), consta in a "vizita" varful initial i si a continua cu vecinii sai nevizitati j. Tot timpul mergem in adancime, cat este posibil, cat nu ne intoarcem si plecam, daca este posibil, spre vecinii nevizitati inca.
Pentru implementarea acestui algoritm se foloseste vectorul VIZ cu aceeasi semnificatie ca la parcurgerea in latime si se inlocuieste coada C cu o stiva S, care ne da posibilitatea sa parcurgem in fiecare moment de la varful curent spre primul dintre vecinii sai nevizitati, acesta din urma fiind plasat in varful stivei; cu acest nod se continua la fel. Varianta aleasa este cea recursiva.
Exemplu: Pentru graful din figura urmatoare, ordinea de parcurgere DF a varfurilor, plecand de la nodul 1 este : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
B. Exemple de programe
In continuare prezentam programele care permit implementarea metodelor de parcurgere a unui graf neorientat si anume parcurgerea in latime - BF (Breath First) si parcurgerea in adancime - DF (Deep First).
Ultimul program este determinarea componentelor conexe ale unui graf neorientat.
1. Parcurgerea in latime - BF:
1. Parcurgerea in adancime - DF:
3. Afisarea componentelor conexe ale unui graf neorientat:
C. Exercitii si teme
1. Sa se ruleze programele prezentate mai sus si sa se verifice folosind mai multe grafuri ca exemplu.
2. Sa se scrie un program C++ care sa parcurga in latime un graf neorientat, reprezentat printr-o lista de adiacenta simplu inlantuita.