Back البحث المتعمق الأول Arabic Diafnsuach BAR Обхождане в дълбочина Bulgarian Prohledávání do hloubky Czech Tiefensuche German Αναζήτηση κατά βάθος Greek Depth-first search English Búsqueda en profundidad Spanish Sügavuti otsing Estonian Sakonera bilaketa Basque
Una cerca en profunditat (en anglès Depth First Search, DFS) és un algorisme que permet recórrer tots els nodes d'un arbre o graf de manera ordenada, però no uniforme. El seu funcionament es basa a anar expandint cada node que troba, de manera recursiva, recorrent tots els nodes d'un camí concret. Quan ja no queden més nodes per visitar d'aquest camí, es realitza un pas enrere (Backtracking), que permet que pugui tornar a començar el mateix procés amb cadascun dels germans d'un node ja processat.
De la mateixa manera, existeix l'algorisme de cerca en amplada (BFS - breadth first search).
El segle xix, el matemàtic francès Charles Pierre Trémaux investigà una versió de l'algorisme de cerca en profunditat com a estratègia per a la resolució de laberints.[1][2]
- ↑ Even, Shimon. Graph Algorithms. 2a edició. Cambridge University Press, 2011, p. 46–48. ISBN 978-0-521-73653-4.
- ↑ Sedgewick, Robert. Algorithms in C++: Graph Algorithms. 3a edició. Pearson Education, 2002. ISBN 978-0-201-36118-6.