Note de curs, clasele 9-10, 5 decembrie 2013
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
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);
}
}
}
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:
- intervalele (d[u], f[u]) și (d[v], f[v]) sunt disjuncte; u și v fac parte din subarbori DFS diferiți
- d[u] < d[v] < f[v] < f[u] și v este urmaș al lui u în arborele DFS
- 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ă):
- Just Matrix de la sgu.ru
- http://www.infoarena.ro/problema/alpin