Aplicații ale parcurgerii grafurilor

Parcurgerea grafurilor neorientate poate fi folosită în rezolvarea unei game largi de probleme: verificarea conexității unui graf, determinarea componentelor conexe ale unui graf, determinarea unor lanțuri în graf, verificarea faptului că un graf este bipartit, etc.

Verificarea conexității

Definiție: Un graf se numește conex dacă între oricare două vârfuri există cel puțin un lanț.

Pentru a verifica dacă un graf este conex, putem folosi oricare metodă de parcurgere, astfel:

• stabilim un vârf de start
• realizăm o parcurgere pornind din vârful de start
• la final verificăm dacă au fost parcurse toate vârfurile, folosind vectorul v de mai sus; în caz afirmativ, graful este conex, altfel graful nu este conex.

Determinarea componentelor conexe

Definiție: Se numește componentă conexă într-un graf neorientat un subgraf conex și maximal cu această proprietate.

Determinarea componentelor conexe se poate face folosind un algoritm de parcurgere. În vectorul v vârfurile vizitate se vor marca cu valori 1, 2, etc. Fiecare valoare v[i] reprezintă componenta conexă din care face parte vârful i.

• nrc = 0
• parcurgem vârfurile
  • dacă vârful curent nu este vizitat
    • incrementăm nrc cu 1
    • parcurgem graful pornind din vârful curent și marcăm în vectorul v[] vârfurile parcurse cu nrc
• la final, nrc reprezintă numărul de componente conexe, și toate vârfurile din aceiași componentă sunt marcate în v[] cu aceiași valoare.

Determinarea unor lanțuri

Pentru a determina un lanț cu extremitățile în nodurile x y, vom realiza o parcurgere pornind de exemplu din x. Dacă se cere un lanț de lungime minimă, vom realiza neapărat o parcurgere în lățime.

Pentru determinarea lanțului vom construi și arborele de parcurgere.

În timpul parcurgerii, când avem nodul curent k și am stabilit că nodul p este adiacent cu k și nevizitat (deci urmează a fi parcurs), vom realiza și operația: t[p] = k;, unde t este vectorul de tați al arborelui de parcurgere.

Lanțul propriu-zis se va reconstitui din vectorul de tați al arborelui. În secvența de mai jos considerăm că parcurgerea a început din vârful x. Nodurile sunt afișate de la y spre rădăcina x, deci ar putea fi necesar să fie afișate în ordine inversă (de exemplu, să le memorăm într-un tablou și să afișăm invers elementele tabloului).

int p = y;
while(p != 0)
{
    cout << p;
    p = t[p];
}

Verificarea proprietății de graf bipartit

Un graf este bipartit dacă și numai dacă nu are cicluri de lungime impară. Pentru verificare, vom realiza o parcurgere în adâncime pornind dintr-un vârf oarecare, de exemplu 1. Pentru a identifica existența unui ciclu de lungime impară, vom marca nodurile vizitate alternativ cu 1 sau 2, astfel:

• marcăm nodul curent cu valoare x
• identificăm vecinii nodului curent
  • dacă nodul vecin nu a fost încă vizitat, îl marcăm cu cealaltă valoare (3-x) și continuăm parcurgerea cu el
  • dacă nodul vecin a fost deja vizitat, acolo se închide un ciclu. Dacă la vizitare acest nod a fost marcat tot cu valoarea x, atunci acel ciclu are lungime impară, deci graful nu este bipartit.

Dacă graful nu este conex, procedăm similar pentru fiecare componentă conexă.

La final, dacă graful este bipartit, modul în care am marcat nodurile ne dau și cele două submulțimi de noduri ale grafului bipartit. Mai precis, nodurile marcate cu 1 fac parte din prima submulțime, iar cele marcate cu 2 fac parte din a doua submulțime.