Back البحث المتعمق الأول Arabic Diafnsuach BAR Обхождане в дълбочина Bulgarian Cerca en profunditat Catalan Prohledávání do hloubky Czech Tiefensuche German Αναζήτηση κατά βάθος Greek Depth-first search English Búsqueda en profundidad Spanish Sügavuti otsing Estonian
Na teoria dos grafos, busca em profundidade (ou busca em profundidade-primeiro, também conhecido em inglês por Depth-First Search - DFS) é um algoritmo usado para realizar uma busca ou travessia numa árvore, estrutura de árvore ou grafo. Intuitivamente, o algoritmo começa num nó raiz (selecionando algum nó como sendo o raiz, no caso de um grafo) e explora tanto quanto possível cada um dos seus ramos, antes de retroceder(backtracking).
Uma versão da busca em profundidade foi investigada no século XIX pelo matemático francês Charles Pierre Trémaux[1] como estratégia para solucionar labirintos.[2][3]
- ↑ Charles Pierre Trémaux (1859–1882) École Polytechnique of Paris (X:1876)
Conferência pública, 2 de dezembro de 2010 – pelo professor Jean Pelletier-Thibert na Académie de Macon (Borgonha – França) – (Abstrato publicado nos anais da Academia, Março de 2011 – ISSN: 0980-6032) - ↑ Even, Shimon (2011), Graph Algorithms, ISBN 978-0-521-73653-4 2nd ed. , Cambridge University Press, pp. 46–48.
- ↑ Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms, ISBN 978-0-201-36118-6 3rd ed. , Pearson Education.