Grafuri neorientate.Parcurgerea in latime

Parcurgerea grafurilor presupune examinarea n vederea prelucrrii tuturor vrfurilor acelui graf ntr-o anumit ordine, ordine care s permit prelucrarea optim a informaiilor ataate grafului. n acest scop s-au dezvoltat dou tehnici fundamentale de traversare a grafurilor, una bazat pe cutarea n adncime, cealalt bazat pe cutarea prin cuprindere. Ambele tehnici constituie nuclee de baz pornind de la care se pot dezvolta numeroi algoritmi eficieni de prelucrare a grafurilor. Parcurgerea n lime a fost descoperit de ctre Moore n contextul cutrii de drumuri n labirinturi. Lee a descoperit, n mod independent, acelai algoritm n contextul stabilirii firelor de pe plcile de circuite. Hopcroft i Tarjan au argumentat folosirea reprezentrii prin liste de adiacen n defavoarea reprezentrii prin matrice de adiacen, pentru grafurile rare, i au fost primii care au recunoscut importana algoritmic a parcurgerii n adncime. Parcurgerea n adncime a fost folosit pe scar larg ncepnd cu anul sfritul anului 1950, n special n programele din domeniul inteligenei artificiale. Tarjan este cel care a elaborat un algoritm liniar pentru determinarea componentelor tare conexe, iar Knuth a fost primul care a dat un algoritm liniar pentru sortarea topologic.

Cutarea prin cuprindere sau traversarea grafurilor n lime este unul dintre cei mai simpli algoritmi de cutare ntr-un graf i arhetipul pentru muli algoritmi de grafuri importani. Algoritmul lui Dijkstra pentru determinarea drumurilor minime de la un nod surs la toate celelalte i algoritmul lui Prim pentru determinarea arborelui parial de cost minim folosesc idei similare din algoritmul de cutare n lime Aceast metod se bazeaz pe urmtoarea tehnic: - fie un graf G = (X,U) cu n noduri i un nod de plecare ns numit i nod surs - cutarea n lime exploreaz sistematic muchiile grafului G pentru a "descoperi" fiecare nod accesibil din ns. Algoritmul calculeaz distana (cel mai mic numr de muchii) de la ns la toate vrfurile accesibile lui. El produce un "arbore de lime" cu rdcina n ns, care conine toate nodurile accesibile. Pentru fiecare nod v accesibil din ns, calea din arborele de lime de la ns la v corespunde "celui mai scurt drum" de la ns la v, adic conine un numr minim de muchii. Traversarea grafurilor n lime sau Breadth-First este numit astfel pentru c lrgete, uniform, frontiera dintre nodurile descoperite i cele nedescoperite, pe limea frontierei. Aceasta nseamn c algoritmul descoper toate vrfurile aflate la distana k fa de ns nainte de a descoperi vreun vrf la distana k+1. Cu alte cuvinte traversarea n lime a grafurilor presupune faptul c dup vizitarea unui anumit nod v, sunt parcuri toi vecinii nevizitai ai acestuia, apoi toi vecinii nevizitai ai acestora din urm pn la vizitarea tuturor nodurilor grafului(spunem c dou noduri sunt vecine dac sunt adiacente). Implementarea acestei metode se face folosind o structur de date de tip coad. Cozile sunt structuri de date n care elementele sunt inserate la un capt (sfritul cozii) i sunt suprimate de la cellalt capt (nceputul cozii). Ele implementeaz politica "primul venit - primul servit". Asupra unei cozi acioneaz operatori specifici cum ar fi: iniializare coad, test de coad vid, adug un element la sfritul cozii, scoate un element de la nceputul cozii. Cozile pot fi implementate static(cu variabile de tip tablou unidimensional) sau dinamic.

n acest caz coada este iniializat cu un nod oarecare al grafului. La fiecare pas, pentru nodul aflat n vrful cozii, se adaug la coad toi vecinii nevizitai ai nodului respectiv dup care se terge din coad primul nod.Fie graful din figura urmtoare care are n = 8 noduri

Vom utiliza un vector v, cu un numr de elemente egal cu numrul de noduri din graf, iar fiecare element al su poate lua valoarea 1, dac i numai dac nodul a fost "vizitat", sau valoarea dac nodul nu a fost vizitat.

Algoritm de parcurgere in latime a unei singure componente conexe:

1. citirea datelor de intrare(numr de noduri si muchiile grafului) i construirea matricei de adiacen 2. afisarea pe ecran a matricei de adiacenta 3. citirea/determinarea unui nod de start 4. marcarea nodului de start ca fiind vizitat: v[i]=0 5. afisarea nodului de stat 6. adaug la coad n prima pozitie nodul de start:

o prim=1; //poziia primului nod din coad o ultim=1; // poziia ultimul nod aezat la coada o c[ultim]=ns; //adugarea nodului de start la coada

7. ct timp coada nu este vid execut o determin TOATE nodurile adiacente cu primul nod din coad i

nevizitate, iar pentru fiecare nod astfel gsit efectueaz urmtoarele operaii:

marcheaz-l vizitat afieaz-l adaug-l la coada

o elimin primul nod din coada

Aplicatii rezolvate ale algoritmului de parcurgere in latime

1.Determinarea componentelor conexe

n fierul text graf.in este memorat un graf neorientat neconex astfel:

pe prima linie un numr natural n, care reprezint numrul de noduri ale unui graf neorientat. pe urmtoarele linii sunt memorate cte dou numere naturale care reprezint muchiile grafului.

Scriei un program care s parcurg n lime fiecare componet conex a grafului dat. Componentele conexe vor fi numerotate, iar pentru fiecare component conex vor fi afiate nodurile care o alctuiesc.

Exemplu:

Continutul fiierului text graf.in Rezultate asteptate

8

1 3

1 2

1 5

2 5

2 6

4 8

Dac nodul de start este 1 atunci se vor afia urmtoarele rezultate: Componenta conex 1 conine nodurile: 1 2 3 5 6

Componenta conex 2 conine nodurile: 4 8 Componenta conex 3 conine nodurile:7

Graful este alctuit din 3 componente conexe.

Graful memorat n fierul text de mai sus are urmtorul aspect grafic:

Program C++: #include #include using namespace std; int a[20][20],c[20],v[20],ns,n,comp; int prim; int ultim;

// citirea grafului din fisier text si construirea matricei de adiacenta

void citire(int a[20][20], int &n)

{ ifstream f("graf.in"); int x,y; f>>n; while(f>>x>>y) a[x][y]=a[y][x]=1; f.close(); }

// afisarea pe ecran a matricei de adiacenta

void afisare(int a[20][20],int n) { cout

for( int i=1;i

return 0; }

2. Transformarea unui graf neconex intr-un graf conex

Enunt

n fierul text graf.in este memorat un graf neorientat neconex astfel:

pe prima linie un numr natural n, care reprezint numrul de noduri ale unui graf neorientat. pe urmtoarele linii sunt memorate cte dou numere naturale care reprezint muchiile grafului.

Scriei un program care s determine numrul minim de muchii care trebuiesc adugate la graf astfel nct graful s devin conex. Afiai i o posibil soluie.

Exemplu:

Continutul fiierului text graf.in Rezultate asteptate

8

1 3

1 2

1 5

2 5

2 6

4 8

Muchiile adugate sunt: (1,4) (1,7)

Numrul minim de muchii adugate este 2.

Graful memorat n fierul text de mai sus are aspectul grafic ca in exemplul anterior. Rezolvare: Graful ales ca exemplu este alctuit din trei componente conexe dup cum urmeaz::

Componenta conex 1 conine nodurile: 1 2 3 5 6 Componenta conex 2 conine nodurile: 4 8 Componenta conex 3 conine nodurile:7

Folosind algoritmul de parcurgere n lime se determin numrul de componente conexe. Numrul minim de muchii care trebuiesc adugate pentru a transforma un graf neconex ntr-un graf conex este dat de urmtoarea relaie:

numrul componentelor conexe-1 Muchiile care trebuiesc adugate vor fi formate din nodul de start i primul nod din fiecare componenta conex iar graful conex va arata astfel:

Programul C++ este:

#include #include using namespace std; int a[20][20],c[20],v[20],ns,n,comp; int prim; int ultim;

// citirea grafului din fisier text si construirea matricei de adiacenta

void citire(int a[20][20], int &n) { ifstream f("graf.in"); int x,y; f>>n; while(f>>x>>y) a[x][y]=a[y][x]=1; f.close(); }

// afisarea pe ecran a matricei de adiacenta

void afisare(int a[20][20],int n) { cout

} }

// functia principala main()

int main() { citire(a,n); afisare(a,n); ns=1; cout

return i;

return 0;

}

int main()

{ citire(a,n);

afisare(a,n);

for(int i=1;i