Note de curs, clasele 9-10, 5 decembrie 2013

From Algopedia
Jump to: navigation, search

Parcurgerea în adâncime (depth-first search - DFS)

Parcurgerea în adâncime, după cum subliniază și numele ei, preferă să parcurgă nodul în adâncime.

Începem cu pseudocodul, ca să vedem exact despre ce vorbim

<source> DFS(nod u) {

 culoare[u] = gri;
 d[u] = ++timp;
 foreach (v vecin al lui u) {
   if (culoare[v] == alb) {
     p[v] = u;
     DFS(v);
   }
 }
 culoare[u] = negru;
 f[u] = ++timp;

}

DFS-master(graf G) {

 for (u nod în G) {
   d[u] = f[u] = ∞;
   p[u] = NIL;
   culoare[u] = alb;
 }
 timp = 0;
 for (u nod în G) {
   if (culoare[u] == alb) {
     DFS(u);
   }
 }  

} </source>

Observații despre acest cod:

  • Este recursiv. :-)
  • Funcționează pe grafuri orientate sau neorientate.
  • El calculează o mulțime de informații care sunt utile din punct de vedere teoretic, dar de obicei nu sunt necesare la implementare.
  • Timpul este o variabilă globală care crește la fiecare „eveniment”
  • d[u] și f[u] rețin descoperirea, respectiv terminarea explorării unui nod.
  • p[u] reține părintele fiecărui nod, respectiv nodul prin care s-a ajuns la acel nod.
  • Nodurile sunt inițial albe, devin gri în timpul explorării, apoi negre când sunt explorate complet.
  • În fapt, nodurile gri reprezintă nodurile de pe stiva recursivității.
  • Algoritmul nu promite o ordine aparte de vizitare. Noduri foarte apropiate de sursă pot fi vizitate ultimele.
  • Dacă graful nu este conex, DFS() va înnegri doar o parte din graf. Dacă dorim să-l explorăm complet, avem nevoie de funcția DFS-master().

Complexitate

DFS-master() este evident O(n). DFS() execută bucla for de m ori în total (căci inspectează fiecare muchie exact o dată pentru grafuri orientate, respectiv de două ori pentru grafuri neorientate). Așadar, complexitatea este O(m + n), ca și pentru BFS.

Comparație între BFS și DFS

  • DFS se implementează mult mai ușor decât BFS.
  • BFS este adesea o problemă în sine, pe când DFS este doar o metodă sistematică de a explora graful, servind ca suport pentru alte probleme.
  • BFS calculează distanțele minime de la sursă, pe când DFS nu poate garanta decât accesibilitatea, nu și distanțele.
  • Atât BFS cât și DFS pot avea nevoie de memorie suplimentară O(n).
    • Dați exemple de grafuri pe care BFS, respectiv DFS necesită memorie O(n).
  • Conceptual, atât BFS cât și BFS folosesc trei culori pentru noduri (alb, gri și negru).

Proprietăți ale DFS

Vectorul p stochează, în fapt, un arbore, căci muchiile (p[u], u) nu închid cicluri. Acest arbore se numește arborele parcurgerii sau arbore DFS și coincide cu arborele de apeluri recursive.

În urma parcurgerii în adâncime a unui graf orientat, muchiile grafului se împart în patru categorii importante:

  • muchiile de arbore (tree) sunt acele muchii pe care DFS() se reapelează recursiv. Ele sunt stocate în vectorul p. Ele duc de la un nod gri la unul alb.
  • muchiile înapoi (back) sunt muchii care ar închide un ciclu între nodurile de pe stivă. Ele duc de la un nod gri la alt nod gri.
  • muchiile înainte (forward) sunt muchii care duc de la un nod gri la un nod negru din subarborele lui DFS.
  • muchiile transversale (cross) sunt muchii care duc de la un nod gri la un nod negru dintr-un subarbore DFS parcurs anterior.

În grafurile orientate, parcurgerea DFS generează doar muchii de arbore și înapoi, niciodată înainte sau transversale.

Timpii de vizitare d și f dau indicii despre raporturile dintre noduri în arborele DFS. Două noduri u și v vor fi mereu în unul din aceste cazuri:

  1. intervalele (d[u], f[u]) și (d[v], f[v]) sunt disjuncte; u și v fac parte din subarbori DFS diferiți
  2. d[u] < d[v] < f[v] < f[u] și v este urmaș al lui u în arborele DFS
  3. d[v] < d[u] < f[u] < f[v] și u este urmaș al lui v în arborele DFS

Cazuri ca d[u] < d[v] < f[u] < f[v] sunt imposibile. Demonstrație: presupunem că d[u] < d[v] și vedem unde poate fi f[u].

Aplicații ale parcurgerii în adâncime

Determinarea componentelor conexe într-un graf neorientat

Sortare topologică

Definiție; se aplică grafurilor orientate aciclice (dag).

Exemple:

  • lista de sarcini sau de buguri într-un proiect;
  • lista de dependențe între cursuri la o universitate;
  • lista de moșteniri la clasele din C++/Java (compilatorul trebuie să știe);
  • cum se îmbracă un om.

Sortarea topologică este o relație de ordine parțială, spre deosebire de relația "<" pe numere, care este o relație de ordine totală.

Un algoritm simplu folosește o coadă de noduri de grad la intrare 0. Algoritmul are complexitate O(V + E).

Al doilea algoritm este o aplicație directă a DFS: nodurile sunt afișate în ordine descrescătoare a lui f. Echivalent, la terminarea vizitării unui nod, îl adăugăm la începutul listei-soluție (din nou, vectorul f nu este explicit necesar).

În ambele cazuri, când știm că graful nu admite o sortare topologică? Hint: un graf orientat este aciclic ⇔ în DFS nu există back edges.

Demonstrație că DFS sortează topologic:

  • trebuie să arătăm că, pentru orice muchie (u,v), f[v] < f[u]
  • când muchia (u,v) este explorată, v nu poate fi gri, căci (u,v) ar fi back edge
    • dacă v este alb, el devine urmaș al lui u și va fi înnegrit înainte de a reveni la u
    • dacă v este negru, f[v] era deja setat, pe când f[u] va fi setat la un moment viitor

Probleme

Probleme teoretice:

  • Este adevărat? dacă u ~~> v și d[u] < d[v], atunci v este urmaș al lui u în DFS.
  • Este adevărat? dacă u ~~> v atunci d[v] <= f[u]
  • Este adevărat? dacă u are muchii care intră și muchii care ies, atunci u nu poate fi singur în arborele lui DFS.
  • Cum clasificăm muchiile grafului în cele patru categorii? (Notă: distincția interesantă este între muchii forward și cross)
  • Găsirea unui ciclu într-un graf, O(n)

Probleme de implementare (DFS):

Probleme de implementare (sortare topologică):