Busca en profunditat

Archiu:Depth-first-tree.svg

Busca en profunditat.(Orde en el que es visiten els nodos)

Una Busca en profunditat (en anglés DFS o Depth First Search) és un algoritme de busca no informada utilisat per a recórrer tots els nodos d'un grafo o arbre (teoria de grafos) de manera ordenada, pero no uniforme. El seu funcionament consistix en anar expandint tots i cada u dels nodos que va localisant, de forma recurrent, en un camí concret. Quan ya no queden més nodos que visitar en dit camí, retorna (Backtracking), de modo que repetix el mateix procés en cada u dels germans del nodo ya processat.

Análogamente existix l'algoritme de busca en esgambi (BFS o Breadth First Search).

Evaluació

Completitud: DFS és complet si i solament si usem busca basada en grafos en espais d'estat finitos, puix tots els nodos seran expandits.

Optimalidad: DFS en cap cas assegura la optimalidad, puix pot trobar una solució més profunda que una atra en una branca que encara no ha segut expandida.

Complexitat temporal: en el pijor cas, és $O(b^m)$, sent b el factor de ramificació (número promig de ramificacions per nodo) i m la màxima profunditat del espai d'estats.

Complexitat espacial: $O(b^d)$, sent b el factor de ramificació i d la profunditat de la solució menys costosa, puix cada nodo generat permaneix en memòria, almagasenant-se la major cantitat de nodos en el nivell fique.

Eixemple

Per al grafo següent:

Archiu:Graph.traversal.example.svg

una busca en profunditat escomençant en el nodo A, en la suposició que les arestes a l'esquerra són triades abans de les arestes a la dreta, l'algoritme va a visitar els nodos en esta orde: A, B, D, F, I, C, G. Es pot notar llavors que, si l'algoritme no aplegara a recordar els nodos ya visitats, llavors podria continuar en un bucle infinit: A, B, D, F, I, A, B, D, F, I, etc. sense visitar C o G.

Per a evitar este bucle infinit, es poden utilisar tècniques com la busca en profunditat iterativa.

Vore també

• Arbre (estructura de senyes)
• Recorregut d'arbres
• Busca en esgambi

• Lema: Un grafo dirigit és cíclico si i només si en eixecutar DFS(G) produïx a lo manco un arc cap a arrere.

Referències

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.3: Depth-first search, pp.540–549.

Commons

• Wikimedia Commons alberga contingut multimèdia sobre Busca en profunditat.