Grafuri-conexitate-parcurgerea in latime

Parcurgerea grafurilor presupune examinarea în vederea prelucrării tuturor vârfurilor acelui graf într-o anumită ordine, ordine care să permită prelucrarea optimă a informaţiilor ataşate grafului. În acest scop s-au dezvoltat două tehnici fundamentale de traversare a grafurilor, una bazată pe căutarea în adâncime, cealaltă bazată pe căutarea prin cuprindere. Ambele tehnici constituie nuclee de bază pornind de la care se pot dezvolta numeroşi algoritmi eficienţi de prelucrare a grafurilor.

Parcurgerea în lăţime a fost descoperită de către Moore în contextul căutării de drumuri în labirinturi. Lee a descoperit, în mod independent, acelaşi algoritm în contextul stabilirii firelor de pe plăcile de circuite. Hopcroft şi Tarjan au argumentat folosirea reprezentării prin liste de adiacenţă în defavoarea reprezentării prin matrice de adiacenţă, pentru grafurile rare, şi au fost primii care au recunoscut importanţa algoritmică a parcurgerii în adâncime. Parcurgerea în adâncime a fost folosită pe scară largă începând cu anul sfârşitul anului 1950, în special în programele din domeniul inteligenţei 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ă.

Căutarea prin cuprindere sau traversarea grafurilor în lăţime este unul dintre cei mai simpli algoritmi de căutare într-un graf şi arhetipul pentru mulţi algoritmi de grafuri importanţi. Algoritmul lui Dijkstra pentru determinarea drumurilor minime de la un nod sursă la toate celelalte şi algoritmul lui Prim pentru determinarea arborelui parţial de cost minim folosesc idei similare din algoritmul de căutare în lăţime

Această metodă se bazează pe următoarea tehnică:

- fie un graf G = (X,U) cu n noduri şi un nod de plecare ns numit şi nod sursă

- căutarea în lăţime explorează sistematic muchiile grafului G pentru a "descoperi" fiecare nod accesibil din ns. Algoritmul calculează distanţa (cel mai mic număr de muchii) de la ns la toate vârfurile accesibile lui. El produce un "arbore de lăţime" cu rădăcina în ns, care conţine toate nodurile accesibile. Pentru fiecare nod v accesibil din ns, calea din arborele de lăţime de la ns la v corespunde "celui mai scurt drum" de la ns la v, adică conţine un număr minim de muchii.

Traversarea grafurilor în lăţime sau Breadth-First este numită astfel pentru că lărgeşte, uniform, frontiera dintre nodurile descoperite şi cele nedescoperite, pe lăţimea frontierei. Aceasta înseamnă că algoritmul descoperă toate vârfurile aflate la distanţa k faţă de ns înainte de a descoperi vreun vârf la distanţa k+1. Cu alte cuvinte traversarea în lăţime a grafurilor presupune faptul că după vizitarea unui anumit nod v, sunt parcurşi toţi vecinii nevizitaţi ai acestuia, apoi toţi vecinii nevizitaţi ai acestora din urmă până 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 capăt (sfârşitul cozii) şi sunt suprimate de la celălalt capăt (începutul cozii). Ele implementează politica "primul venit - primul servit". Asupra unei cozi acţionează operatori specifici cum ar fi: iniţializare coadă, test de coadă vidă, adăugă un element la sfârşitul 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 iniţializată cu un nod oarecare al grafului. La fiecare pas, pentru nodul aflat în vârful cozii, se adaugă la coadă toţi vecinii nevizitaţi ai nodului respectiv după care se şterge din coadă primul nod.Fie graful din figura următoare care are n = 8 noduri

Vom utiliza un vector v, cu un număr de elemente egal cu numărul de noduri din graf, iar fiecare element al său 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(număr 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

   1. adaug la coadă în prima pozitie nodul de start:

• • prim=1; //poziţia primului nod din coadă

  • ultim=1; // poziţia ultimul nod aşezat la coada

  • c[ultim]=ns; //adăugarea nodului de start la coada

• 1. cât timp coada nu este vidă execută

     • determină TOATE nodurile adiacente cu primul nod din coadă şi nevizitate, iar pentru fiecare nod astfel găsit efectuează următoarele operaţii:

       • marchează-l vizitat

       • afişează-l

       • adaugă-l la coada

     • elimină primul nod din coada

Aplicatii rezolvate ale algoritmului de parcurgere in latime:

1. Verifica daca un graf este conex

2. Determinarea componentelor conexe ale unui graf norientat

3. Transformarea unui graf neconex în graf conex

4. Algoritmul lui Lee

5. Verifică dacă un graf conex este bipartit.