Căutare în adâncime

Căutarea sau parcurgerea în adâncime (denumită și ca în engleză depth-first search, abreviat DFS) este un algoritm pentru parcurgerea sau căutarea într-o structură de date de tip arbore sau graf. Se începe de la rădăcină^⁠(d) (sau alegând un nod arbitrar ca rădăcină în cazul unui graf) și se explorează cât mai mult posibil de-a lungul fiecărei ramuri înainte de a face pași înapoi.

O versiune a căutării în adâncime a fost cercetată în secolul al XIX-lea de către matematicianul francez Charles Pierre Trémaux^⁠(d)^[1] ca o strategie pentru rezolvarea de labirinturi^⁠(d).^[2]^[3]

Proprietăți

Analiza în timp și în spațiu^⁠(d) a DFS diferă în funcție de zona sa de aplicare. În informatica teoretică, DFS este de obicei folosit pentru a parcurge un întreg graf, și are nevoie de timp Θ(|V| + |E|),^[4] liniar în raport cu dimensiunile grafului. În aceste aplicații, el utilizează un spațiu de ordinul O(|V|), în cel mai rău caz pentru a stoca stiva de noduri pe actuala cale de căutare, precum și mulțimea de noduri deja vizitate. Astfel, în acest context, limitele în timp și spațiu sunt aceleași ca și pentru parcurgerea în lățime, iar alegerea unuia dintre acești doi algoritmi depinde mai puțin de complexitatea lor și mai mult de proprietățile diferite ale ordonărilor pe care le produc ele pentru mulțimea nodurilor.

Pentru aplicațiile DFS în legătură cu anumite domenii, cum ar fi căutarea de soluții în inteligența artificială sau web-crawling, graful de parcurs este de multe ori prea mare pentru a-l vizita în întregime, sau poate fi infinit (DFS poate suferi de neterminare^⁠(d)). În astfel de cazuri, căutarea se efectuează numai până la o adâncime limitată^⁠(d); din cauza resurselor limitate, cum ar fi memoria sau spațiul pe disc, de obicei nu se folosesc structuri de date pentru a ține evidența tuturor nodurilor vizitate anterior. Când căutarea este efectuată pe o adâncime limitată, timpul este încă liniar în raport cu numărul de noduri și muchii expandate (deși acest număr nu este același ca și mărimea întregului graf, deoarece unele noduri pot fi căutate de mai multe ori, iar altele deloc), dar de complexitatea în spațiu a acestei variante de DFS este doar proporțională cu adâncimea limită, și, ca urmare, este mult mai mică decât spațiul necesar pentru căutarea până la aceeași adâncime, folosind căutarea în lățime. Pentru astfel de aplicații, DFS se pretează mult mai bine și la metode euristice^⁠(d) de alegere a unei ramuri probabile. Atunci când nu se știe priori o limită de adâncime, iterative deepening depth-first search^⁠(d) aplică DFS în mod repetat, crescând la fiecare pas limita. În modul de analiză din inteligența artificială, cu un factor de ramificare^⁠(d) mai mare decât unu, iterative deepening crește timpul de funcționare doar cu un factor constant față de cazul când limita corectă de adâncime este cunoscută datorită creșterii geometrice a numărului de noduri de pe fiecare nivel.

DFS poate fi folosit și pentru a colecta un eșantion^⁠(d) de noduri din graf. Cu toate acestea, DFS incomplet, similar BFS incomplet, favorizează nodurile de grad înalt.

Exemplu

Pentru următorul graf:

o căutare în adâncime pornind de la A, presupunând că muchiile din stânga din graful prezentat sunt alese înaintea celor din dreapta, și presupunând că sunt reținute nodurile vizitate anterior și că nu se repetă (deoarece graful este mic), se vor vizita nodurile în următoarea ordine: A, B, D, F, E, C, G. Muchiile traversate în această căutare formează un arbore Trémaux^⁠(d), o structură cu importante aplicații în teoria grafurilor.

Efectuând aceeași căutare, fără a reține nodurile vizitate anterior conduce la vizitarea nodurilor în ordinea A, B, D, F, E, A, B, D, F, E etc. în ciclu infinit A, B, D, F, E neajungând niciodată la C sau la G.

Iterative deepening^⁠(d) este una din tehnicile de a evita această buclă infinită și ar ajunge la toate nodurile.

Rezultatul unei căutări în adâncime

Cele patru tipuri de muchii definite într-un arbore de acoperire

O descriere convenabilă a unei căutări în adâncime într-un graf este în termeni de arbore de acoperire^⁠(d) a nodurilor atinse în timpul căutării. Pe baza acestui arbore de acoperire, muchiile grafului inițial pot fi împărțite în trei clase: muchii înainte, care duc de la un nod al arborelui la unul dintre urmașii săi, muchii înapoi, care duc de la un nod la unul din strămoșii săi, și muchii laterale, care nu fac niciuna dintre acestea. Uneori, muchiile de arbore, adică cele care aparțin arborelui de parcurgere în sine, sunt clasificate separat față de muchiile înainte. Dacă graful inițial este neorientat, atunci toate muchiile sale sunt fie muchii de arbore, fie muchii înapoi.

Ordonare DFS

O enumerare a nodurilor unui graf este declarată a fi o ordine DFS dacă este o ieșire posibilă a aplicării DFS asupra grafului.

Fie $G=(V,E)$ un graf cu $n$ noduri. Pentru $\sigma =(v_{1},\dots ,v_{m})$ fie o listă de elemente distincte din $V$ , pentru $v\in V\setminus \{v_{1},\dots ,v_{m}\}$ , fie $\nu _{\sigma }(v)$ cel mai mare $i$ astfel încât $v_{i}$ este un vecin cu $v$ , dacă un astfel de $i$ există, și $0$ în caz contrar.

Fie $\sigma =(v_{1},\dots ,v_{n})$ o enumerare a nodurilor lui $V$ . Enumerarea $\sigma$ se spune că este ordonare DFS (cu sursa $v_{1}$ ) dacă, oricare ar fi $1<i\leq n$ , $v_{i}$ este nodul $w\in V\setminus \{v_{1},\dots ,v_{i-1}\}$ cu proprietatea că $\nu _{(v_{1},\dots ,v_{i-1})}(w)$ este maximal. De reținut că $N(v)$ este mulțimea vecinilor lui $v$ . Echivalent, $\sigma$ este o ordonare DFS dacă, oricare ar fi $1\leq i<j<k\leq n$ cu $v_{i}\in N(v_{k})\setminus N(v_{j})$ , există un vecin $v_{m}$ al lui $v_{j}$ astfel încât $i<m<j$ .

Ordonările nodurilor

Căutarea în adâncime se poate folosi și pentru a ordona liniar nodurile grafului (sau arborelui) inițial. Există trei modalități comune de a face acest lucru:

În preordine: o listă a nodurilor în ordinea în care au fost vizitate pentru prima dată algoritmul de căutare în adâncime. Aceasta este o modalitate compactă și naturală de a descrie progresul căutării, cum s-a făcut mai devreme în acest articol. O sortare în preordine a arborelui unei de expresii^⁠(d) este expresia în formă poloneză.
În postordine: o listă a nodurilor în ordinea în care acestea au fost ultimele vizitate de algoritm. Sortarea în postordine a arborelui unei expresii este expresia în forma poloneză inversă.
O sortare în postordine inversă este inversul unei sortări în postordine, adică o listă a nodurilor în ordine inversă de la ultima lor vizită. Ea nu este aceeași cu sortarea în preordine. De exemplu, atunci când se parcurge în preordine graful orientat

începând de la nodul A, se vizitează nodurile în ordine, pentru a produce liste, fie A B D B A C A, fie A C D C A B A (în funcție de alegerea algoritmului de a viztita mai întâi B sau C). Vizitele repetate în sensul pasului înapoi la un nod, pentru a verifica dacă acesta mai are vecini nevizitați, sunt incluse aici (chiar dacă nu se găsește niciun vecin). Astfel, sortările posibile în preordine sunt A B D C și A C D B (după apariția cea mai din stânga a nodului în lista de mai sus), în timp ce sortările în postordine inversă sunt A C B D și A B C D (după cea mai din dreapta apariție în lista de mai sus). Postordinea inversă produce o sortare topologică^⁠(d) a oricărui graf aciclic orientat^⁠(d). (Sortările posibile în postordine sunt D B C A și D C B A.) Această ordonare este utilă și în analiza fluxului de control^⁠(d), reprezentând adesea o liniarizare naturală a fluxurilor de control. Graful de mai sus ar putea reprezenta fluxul de control într-un fragment de cod ca

if (O) then {
 B
} else {
 C
}
D

și este firesc să ia în considerare acest cod în ordinea A B C D sau A C B D, dar nu este natural să se utilizeze ordinea A B D C sau A C D B.

Pseudocod

Intrare: Un graf G și un nod v din G

Ieșire: Toate nodurile accesibile din v etichetate pe măsură ce sunt descoperite

O implementare recursivă a lui DFS:^[5]

1 procedure DFS(G,v):
2   etichetează v ca descoperit
3   for all muchie de la v la w in G.adjacentEdges(v) do
4     if nodul w nu este etichetat ca descoperit then
5       apelează recursiv DFS(G,w)

Ordinea în care nodurile sunt descoperite prin acest algoritm se numește ordine lexicografică^⁠(d).

O implementare nerecursivă a DFS cu complexitatea în spațiun în cel mai rău caz O(|E|):^[6]

1 procedure DFS-iterativ(G,v):
2   fie S o stivă
3   S.push(v)
4   while S nu este vidă
5     v = S.pop()
6     if v nu este etichetat ca descoperit:
7       etichetează v ca descoperit
8       for all muchie de la v la w in G.adjacentEdges(v) do
9         S.push(w)

Aceste două variante de DFS vizitează vecinii fiecărui nod în ordine inversă: primul vecin al lui v este vizitat de varianta recursivă este primul din lista de muchii adiacente, în timp ce în cea iterativă, primul vizitat vecinul este ultimul din lista de muchii adiacente. Implementarea recursivă va vizita nodurile din graful din exemplu în următoarea ordine: A, B, D, F, E, C, G. Implementarea nerecursivă va vizita nodurile: A, E, F, B, D, C, G.

Implementarea nerecursivă este similară cu căutarea în lățime, dar diferă de acesta în două moduri:

utilizează o stivă în loc de coadă, și
amână verificarea dacă un nod a fost descoperit până când se scoate nodul din stivă, în loc să facă verificarea înainte de adăugarea nodului.

Aplicații

Algoritmi care folosesc căutarea în adâncime ca element constitutiv sunt:

Găsirea componentelor conexe.
Sortarea topologică^⁠(d).
Găsirea de componente 2-(muchie sau nod)-conexe.
Găsirea de componente 3-(muchie sau nod)-conexe.
Găsirea de punți într-un graf.
Generarea de cuvinte, pentru mulțimea limită a unui grup.
Găsirea componentelor tare conexe^⁠(d).
Testarea planarității^⁠(d)^[7]^[8]
Rezolvarea puzzle-urilor cu o singură soluție, cum ar fi labirinturile. (DFS poate fi adaptat pentru a găsi toate soluțiile la un labirint incluzând doar nodurile de pe calea curentă în mulțimea de noduri vizitate.)
Generarea de labirinturi^⁠(d) poate folosi o căutare în adâncime randomizată.
Găsirea biconexității în grafuri^⁠(d).

Complexitatea

Complexitatea computațională^⁠(d) a DFS a fost cercetată de către John H. Reif^⁠(d). Mai precis, având un graf $G$ , fie $O=(v_{1},\dots ,v_{n})$ ordonarea calculată prin algoritmul DFS standard recursiv. Această ordonare se numește ordonare lexicografică a parcurgerii în adâncime. John Reif a considerat complexitatea calculului ordonării lexicografice a parcurgerii în adâncime, având un graf și o sursă. O versiune de decizie^⁠(d) a problemei (testarea dacă un nod u apare înaintea unui alt nod v în această ordonare) este P-completă^⁠(d),^[9] în sensul că acesta este „un coșmar pentru prelucrarea paralelă”.^[10]^:189

O ordonare (nu neapărat lexicografică) dată de căutarea în adâncime poate fi calculată printr-un algoritm paralel din clasa de complexitate RNC^⁠(d).^[11] În 1997, nu se știa încă dacă se poate construi o parcurgere în adâncime de către un algoritm paralel determinist din clasa de complexitate DD^⁠(d).^[12]

Note

^ Charles Pierre Trémaux^⁠(d) (1859–1882) École polytechnique of Paris (X:1876), French engineer of the telegraph
in Public conference, 2 decembrie 2010 – by professor Jean Pelletier-Thibert^⁠(en)^[traduceți] in Académie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – ISSN 0980-6032)
^ Even, Shimon (2011), Graph Algorithms (ed. 2nd), Cambridge University Press, pp. 46–48, ISBN 978-0-521-73653-4
^ Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (ed. 3rd), Pearson Education, ISBN 978-0-201-36118-6
^ Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. p.606
^ Goodrich and Tamassia; Cormen, Leiserson, Rivest, and Stein
^ Page 93, Algorithm Design, Kleinberg and Tardos
^ Hopcroft, John; Tarjan, Robert E. (1974), „Efficient planarity testing”, Journal of the Association for Computing Machinery^⁠(d), 21 (4): 549–568, doi:10.1145/321850.321852 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
^ de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), „Trémaux Trees and Planarity”, International Journal of Foundations of Computer Science, 17 (5): 1017–1030, doi:10.1142/S0129054106004248 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
^ Reif, John H. (1985). „Depth-first search is inherently sequential”. Information Processing Letters. 20 (5). doi:10.1016/0020-0190(85)90024-9. Mai multe valori specificate pentru |DOI= și |doi= (ajutor)
^ Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer.
^ Aggarwal, A.; Anderson, R. J. (1988), „A random NC algorithm for depth first search”, Combinatorica^⁠(d), 8 (1): 1–12, doi:10.1007/BF02122548 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
^ Karger, David R.; Motwani, Rajeev (1997), „An NC algorithm for minimum cuts”, SIAM Journal on Computing^⁠(d), 26 (1): 255–272, doi:10.1137/S0097539794273083 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

Bibliografie

Thomas H. Cormen^⁠(d), Charles E. Leiserson^⁠(d), Ronald L. Rivest, și Clifford Stein^⁠(d). Introduction to Algorithms^⁠(d), Second Edition. MIT Press and McGraw-Hill, 2001. ISBN: 0-262-03293-7. Section 22.3: Depth-first search, pp. 540–549.
Goodrich, Michael T.; Tamassia, Roberto (2001), Algorithm Design: Foundations, Analysis, and Internet Examples, Wiley, ISBN 0-471-38365-1
Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design, Addison Wesley, pp. 92–94
Knuth, Donald E. (1997), The Art of Computer Programming Vol 1. 3rd ed, Boston: Addison-Wesley, ISBN 0-201-89683-4, OCLC 155842391, arhivat din original la 4 septembrie 2008, accesat în 19 iulie 2017

Legături externe

[1] Charles Pierre Trémaux^⁠(d) (1859–1882) École polytechnique of Paris (X:1876), French engineer of the telegraph
in Public conference, 2 decembrie 2010 – by professor Jean Pelletier-Thibert^⁠(en)^[traduceți] in Académie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – ISSN 0980-6032)

[2] Even, Shimon (2011), Graph Algorithms (ed. 2nd), Cambridge University Press, pp. 46–48, ISBN 978-0-521-73653-4

[3] Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (ed. 3rd), Pearson Education, ISBN 978-0-201-36118-6

[4] Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. p.606

[5] Goodrich and Tamassia; Cormen, Leiserson, Rivest, and Stein

[6] Page 93, Algorithm Design, Kleinberg and Tardos

[7] Hopcroft, John; Tarjan, Robert E. (1974), „Efficient planarity testing”, Journal of the Association for Computing Machinery^⁠(d), 21 (4): 549–568, doi:10.1145/321850.321852 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[8] Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), „Trémaux Trees and Planarity”, International Journal of Foundations of Computer Science, 17 (5): 1017–1030, doi:10.1142/S0129054106004248 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[9] Reif, John H. (1985). „Depth-first search is inherently sequential”. Information Processing Letters. 20 (5). doi:10.1016/0020-0190(85)90024-9. Mai multe valori specificate pentru |DOI= și |doi= (ajutor)

[mehlhorn-10] Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer.

[11] Aggarwal, A.; Anderson, R. J. (1988), „A random NC algorithm for depth first search”, Combinatorica^⁠(d), 8 (1): 1–12, doi:10.1007/BF02122548 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[12] Karger, David R.; Motwani, Rajeev (1997), „An NC algorithm for minimum cuts”, SIAM Journal on Computing^⁠(d), 26 (1): 255–272, doi:10.1137/S0097539794273083 Mai multe valori specificate pentru |DOI= și |doi= (ajutor).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]