La búsqueda en profundidad ( DFS ) es un algoritmo para atravesar o buscar estructuras de datos de árboles o gráficos . El algoritmo comienza en el nodo raíz (seleccionando algún nodo arbitrario como nodo raíz en el caso de un gráfico) y explora lo más posible a lo largo de cada rama antes de retroceder. Se necesita memoria adicional, generalmente una pila , para realizar un seguimiento de los nodos descubiertos hasta el momento a lo largo de una rama específica, lo que ayuda a retroceder en el gráfico.
En el siglo XIX, el matemático francés Charles Pierre Trémaux [1] investigó una versión de búsqueda en profundidad como estrategia para resolver laberintos . [2] [3]
El análisis temporal y espacial de DFS difiere según su área de aplicación. En informática teórica, DFS se utiliza normalmente para recorrer un gráfico completo y lleva tiempo , [4] donde es el número de vértices y el número de aristas . Esto es lineal en el tamaño del gráfico. En estas aplicaciones, también utiliza espacio en el peor de los casos para almacenar la pila de vértices en la ruta de búsqueda actual, así como el conjunto de vértices ya visitados. Por lo tanto, en esta configuración, los límites de tiempo y espacio son los mismos que para la búsqueda en amplitud y la elección de cuál de estos dos algoritmos usar depende menos de su complejidad y más de las diferentes propiedades de los ordenamientos de los vértices que producen los dos algoritmos. .
Para aplicaciones de DFS en relación con dominios específicos, como la búsqueda de soluciones en inteligencia artificial o el rastreo web, el gráfico que se debe recorrer suele ser demasiado grande para visitarlo en su totalidad o infinito (DFS puede sufrir de no terminación ). En tales casos, la búsqueda sólo se realiza hasta una profundidad limitada ; Debido a recursos limitados, como memoria o espacio en disco, normalmente no se utilizan estructuras de datos para realizar un seguimiento del conjunto de todos los vértices visitados anteriormente. Cuando la búsqueda se realiza a una profundidad limitada, el tiempo sigue siendo lineal en términos del número de vértices y aristas expandidas (aunque este número no es lo mismo que el tamaño de todo el gráfico porque algunos vértices se pueden buscar más de una vez y otros en absoluto), pero la complejidad espacial de esta variante de DFS es solo proporcional al límite de profundidad y, como resultado, es mucho menor que el espacio necesario para buscar a la misma profundidad usando la búsqueda en amplitud. Para tales aplicaciones, DFS también se presta mucho mejor a los métodos heurísticos para elegir una rama que parezca probable. Cuando no se conoce a priori un límite de profundidad apropiado, la búsqueda iterativa de profundidad primero aplica DFS repetidamente con una secuencia de límites crecientes. En el modo de análisis de inteligencia artificial, con un factor de ramificación mayor que uno, la profundización iterativa aumenta el tiempo de ejecución solo en un factor constante en el caso en que se conoce el límite de profundidad correcto debido al crecimiento geométrico del número de nodos por nivel. .
DFS también se puede utilizar para recopilar una muestra de nodos del gráfico. Sin embargo, la DFS incompleta, al igual que la BFS incompleta , está sesgada hacia nodos de alto grado .
Para el siguiente gráfico:
una búsqueda en profundidad que comienza en el nodo A, suponiendo que los bordes izquierdos en el gráfico mostrado se eligen antes que los bordes derechos, y suponiendo que la búsqueda recuerda los nodos visitados anteriormente y no los repetirá (ya que este es un gráfico pequeño), visitará los nodos en el siguiente orden: A, B, D, F, E, C, G. Las aristas atravesadas en esta búsqueda forman un árbol de Trémaux , una estructura con importantes aplicaciones en teoría de grafos . Realizar la misma búsqueda sin recordar los nodos visitados anteriormente da como resultado visitar los nodos en el orden A, B, D, F, E, A, B, D, F, E, etc. para siempre, atrapados en A, B, D, Ciclo F, E y nunca llega a C o G.
La profundización iterativa es una técnica para evitar este bucle infinito y llegaría a todos los nodos.
El resultado de una búsqueda en profundidad de un gráfico se puede describir convenientemente en términos de un árbol de expansión de los vértices alcanzados durante la búsqueda. Con base en este árbol de expansión, los bordes del gráfico original se pueden dividir en tres clases: bordes delanteros , que apuntan desde un nodo del árbol a uno de sus descendientes, bordes posteriores , que apuntan desde un nodo a uno de sus antepasados, y bordes cruzados , que no hacen ninguna de las dos cosas. A veces, los bordes del árbol , que pertenecen al propio árbol de expansión, se clasifican por separado de los bordes delanteros. Si el gráfico original no está dirigido, entonces todos sus bordes son bordes de árbol o bordes posteriores.
También es posible utilizar la búsqueda en profundidad para ordenar linealmente los vértices de un gráfico o árbol. Hay cuatro formas posibles de hacer esto:
Para los árboles binarios, existe además el ordenamiento inverso y el ordenamiento inverso .
Por ejemplo, cuando se busca el gráfico dirigido a continuación comenzando en el nodo A, la secuencia de recorridos es ABDBACA o ACDCABA (la elección de visitar primero B o C desde A depende del algoritmo). Tenga en cuenta que aquí se incluyen las visitas repetidas en forma de retroceder a un nodo, para comprobar si aún tiene vecinos no visitados (incluso si no tiene ninguno). Por lo tanto, los posibles pedidos previos son ABDC y ACDB, mientras que los posibles pedidos posteriores son DBCA y DCBA, y los posibles pedidos posteriores inversos son ACBD y ABC D.
El postordenamiento inverso produce una clasificación topológica de cualquier gráfico acíclico dirigido . Este orden también es útil en el análisis de flujo de control , ya que a menudo representa una linealización natural de los flujos de control. El gráfico anterior podría representar el flujo de control en el fragmento de código siguiente, y es natural considerar este código en el orden ABCD o ACBD, pero no es natural usar el orden ABDC o ACD B.
si ( A ) entonces { B} demás { C}DEntrada : Salida : Una implementación recursiva de DFS: [5]
El procedimiento DFS( G , v ) es etiqueta v como descubierto para todos los bordes dirigidos de v a w que están en G .adjacentEdges( v ) si el vértice w no está etiquetado como descubierto entonces llame recursivamente a DFS( G , w )
Una implementación no recursiva de DFS con la peor complejidad espacial , con la posibilidad de duplicar vértices en la pila: [6]
El procedimiento DFS_iterative( G , v ) es dejar que S sea una pila S .push( v ) mientras que S no esté vacío do v = S .pop() si v no está etiquetado como descubierto, entonces etiquete v como descubierto para todos los bordes desde v hasta w en G .adjacentEdges( v ) hacer S .push( w )
Estas dos variaciones de DFS visitan a los vecinos de cada vértice en orden opuesto entre sí: el primer vecino de v visitado por la variación recursiva es el primero en la lista de aristas adyacentes, mientras que en la variación iterativa el primer vecino visitado es el último en la lista de bordes adyacentes. La implementación recursiva visitará los nodos del gráfico de ejemplo en el siguiente orden: A, B, D, F, E, C, G. La implementación no recursiva visitará los nodos como: A, E, F, B, D , C, G.
La implementación no recursiva es similar a la búsqueda en amplitud , pero se diferencia de ella en dos formas:
Si G es un árbol , reemplazar la cola del algoritmo de búsqueda en amplitud con una pila producirá un algoritmo de búsqueda en profundidad. Para gráficos generales, reemplazar la pila de la implementación iterativa de búsqueda en profundidad con una cola también produciría un algoritmo de búsqueda en amplitud, aunque algo no estándar. [7]
Otra posible implementación de la búsqueda iterativa en profundidad utiliza una pila de iteradores de la lista de vecinos de un nodo, en lugar de una pila de nodos. Esto produce el mismo recorrido que el DFS recursivo. [8]
El procedimiento DFS_iterative ( G , v ) es dejar que S sea una pila. etiqueta v como se descubrió S .push(iterador de G .adjacentEdges( v )) mientras S no está vacío , hazlo si S .peek().hasNext() entonces w = S .peek().next() si w no está etiquetado como se descubrió, entonces la etiqueta fue descubierta S .push(iterador de G .adjacentEdges( w )) else S .pop()
Los algoritmos que utilizan la búsqueda en profundidad como componente básico incluyen:
John Reif investigó la complejidad computacional de DFS . Más precisamente, dado un gráfico , sea el orden calculado por el algoritmo DFS recursivo estándar. Este orden se denomina orden lexicográfico de búsqueda en profundidad. John Reif consideró la complejidad de calcular el orden de búsqueda lexicográfica en profundidad, dado un gráfico y una fuente. Una versión de decisión del problema (probar si algún vértice u ocurre antes de algún vértice v en este orden) es P -completa , [12] lo que significa que es "una pesadilla para el procesamiento paralelo ". [13] : 189
Un orden de búsqueda en profundidad (no necesariamente lexicográfico) puede calcularse mediante un algoritmo paralelo aleatorio en la clase de complejidad RNC . [14] En 1997, aún se desconocía si un recorrido en profundidad podría construirse mediante un algoritmo paralelo determinista, en la clase de complejidad NC . [15]
