Parcurgerea în adâncime

Parcurgerea în adâncime reprezintă explorarea “naturală” a unui graf neorientat. Este foarte asemănătoare cu modul în care un turist vizitează un oraș în care sunt obiective turistice (vârfurile grafului) și căi de acces între obiective (muchiile). Vizitarea orașului va avea loc din aproape în aproape: se pleacă de la un obiectiv de pornire, se continuă cu un obiectiv învecinat cu acesta, apoi unul învecinat cu al doilea, etc.

Parcurgerea în adâncime se face astfel:

• Se începe cu un vârf inițial x, care este în acest moment vârf curent.
• Vârful x se vizitează. Se determină primul său vecin nevizitat y al lui x, care devine vârf curent.
• Apoi se vizitează primul vecin nevizitat al lui y, şi aşa mai departe, mergând în adâncime, până când ajungem la un vârf care nu mai are vecini nevizitați. Când ajungem într-un astfel de vârf, ne întoarcem la “părintele” acestuia – vârful din care am ajuns în acesta.
• Dacă acest vârf mai are vecini nevizitați, alegem următorul vecin nevizitat al său și continuam parcurgerea în același mod.
• Dacă nici acest vârf nu mai are vecini nevizitați, revenim în vârful său părinte și continuăm în același mod, până când toate vârfurile accesibile din vârful de start sunt vizitate.

Observație

Dacă graful nu este conex, nu se vor vizita toate vârfurile.

Exemplu

Parcurgerea din nodul 5: 5 2 1 4 6 3 7 8 9

Alte exemple de parcurgere pe acest graf:

• Parcurgerea din nodul 1: 1 2 3 5 4 6 7 8 9
• Parcurgerea din nodul 2: 2 1 4 5 7 8 9 6 3
• Parcurgerea din nodul 9: 9 7 5 2 1 4 6 3 8

Animație configurabilă pentru parcurgerea DFS

Pentru implementarea algoritmului se foloseşte un vector caracteristic pentru memorarea faptului că un anume vârf a fost sau nu vizitat, la un anumit moment al parcurgerii:

• v[i] = 0, vârful i nu a fost (încă) vizitat
• v[i] = 1, vârful i a fost vizitat

Pentru a determina ordinea în care se parcurg nodurile care pot fi vizitate, se folosește o stivă:

• se analizează mereu nodurile adiacente cu nodul din vârful stivei
• dacă pentru nodul din vârful stivei găsim un vecin nevizitat, adăugăm nodul vecin pe stivă
• dacă pentru nodul din vârful stivei nu mai găsim niciun vecin nevizitat, îl eliminăm de pe stivă

Pentru implementare se poate folosi ca stivă memoria STACK, prin intermediul recursivității.

Implementare C++

Presupunem că graful are n noduri și este prezentat prin matricea de adiacență a. Starea unui vârf (vizitat sau nu) este memorată în vectorul caracteristic v. Toate aceste variabile sunt globale.

void dfs(int k)
{
  v[k]=1; //vizitam varful curent x
  for(int i=1;i<=n;i++) // determinam vecinii nevizitati ai lui x
    if(a[k][i]==1 && v[i]==0)
    {
      dfs(i); // continuam parcurgerea cu vecinul curent i
    }
}

Alte informații determinate prin parcurgerea în adâncime

Arborele de parcurgere

În urma parcurgerii în adâncime, muchiile folosite pentru parcurgere formează un arbore. Acest arbore este graf parțial al grafului dat (dacă graful este conex), și se numește arbore parțial de parcurgere. Arborii de parcurgere ai unui graf sunt diferiți, în funcție de vârful de start.

Exemplu:

Arborele de parcurgere pentru vârful de start 5	Arborele de parcurgere pentru vârful de start 9

Acest arbore poate fi privit ca arbore cu rădăcină, rădăcina fiind vârful de start. Pentru graful de mai sus, parcurgerea în adâncime pornind din vârful 5 produce următorul arbore de parcurgere:

Acest arbore poate fi stocat în memorie prin intermediul unui vector de tați:

• t[k] = 0, vârful k este rădăcina arborelui
• t[k] = x, vârful x este tatăl vârfului k

Pentru arborele de mai sus vectorul de tați este:

k	1	2	3	4	5	6	7	8	9
t[k]	2	5	2	1	0	4	5	7	8

Următoarea secvență C++ realizează parcurgerea în adâncime cu determinarea vectorului de tați. Acesta este declarat global, t[]:

void dfs(int k, int tata)
{
  v[k]=1; //vizitam varful curent x
  t[k] = tata; // completăm vectorul de tați
  for(int i=1;i<=n;i++) // determinam vecinii nevizitati ai lui x
    if(a[k][i]==1 && v[i]==0)
    {
      dfs(i , k); // continuam parcurgerea cu vecinul curent i; acesta il va avea ca tată pe k
    }
}

Clasificarea muchiilor

Muchiile grafului se pot clasifica în urma parcurgerii în adâncime în:

• muchii de arbore: muchiile care sunt folosite la parcurgere și fac parte din arborele de parcurgere;
• muchii de întoarcere (muchii înapoi): toate celelalte – o muchie de întoarcere unește un vârf x cu un strămoș y al lui în arbore, diferit de t[x] – nodul x este valoarea din vârful stivei iar y este o valoare din stivă – diferită de tatăl lui x.

În figura de mai jos este redesenat graful din exemplu. Muchiile de arbore sunt desenate cu linii continue, iar cele de întoarcere cu linii punctate.

Muchiile de întoarcere vor închide cicluri în graf.

Timpii de descoperire și finalizare ai vârfurilor

În timpul parcurgerii în adâncime a unui graf se pot atașa fiecărui vârf două marcaje de timp:

• d[x] – momentul când vârful x este descoperit și adăugat pe stivă
• f[x] – momentul când se termină de vizitat vecinii lui x (si toți descendenții lor), iar vârful x se elimină de pe stivă

Aceste momente de timp vor fi numere naturale între 1 și 2*n, unde n este numărul de vârfuri din graf.

Exemplu:

Redesenăm graful de mai sus formă de arbore, precizând și cele două marcaje de timp (timpul de descoperire este scris cu verde, cel de finalizare cu protocaliu):

k	1	2	3	4	5	6	7	8	9
d[k]	3	2	9	4	1	5	12	13	14
f[k]	8	11	10	7	18	6	12	13	14

Observații:

• pentru orice vârf x, are loc relația d[x] < f[x];
• pentru oricare două vârfuri x și y, are loc exact una dintre următoarele condiții:
  • intervalele [d[x],f[x]] și [d[y],f[y]] sunt total disjuncte;
  • intervalul [d[x],f[x]] este conținut în întregime în intervalul [d[y],f[y]], iar x este descendent al lui y în arborele de parcurgere;
  • intervalul [d[y],f[y]] este conținut în întregime în intervalul [d[x],f[x]], iar y este descendent al lui x în arborele de parcurgere;