La búsqueda en profundidad ( DFS ) es un algoritmo para recorrer o buscar estructuras de datos en forma de árbol o gráfico . El algoritmo comienza en el nodo raíz (seleccionando un nodo arbitrario como nodo raíz en el caso de un gráfico) y explora lo más lejos posible a lo largo de cada rama antes de volver atrás. 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 volver atrás en el gráfico.
En el siglo XIX, el matemático francés Charles Pierre Trémaux [1] investigó una versión de la 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 grafo entero 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 grafo. 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 tanto, en este entorno, los límites temporales y espaciales son los mismos que para la búsqueda en amplitud y la elección de cuál de estos dos algoritmos utilizar depende menos de su complejidad y más de las diferentes propiedades de los ordenamientos de vértices que producen los dos algoritmos.
Para las aplicaciones de DFS en relación con dominios específicos, como la búsqueda de soluciones en inteligencia artificial o rastreo web, el gráfico que se debe recorrer es a menudo demasiado grande para visitarlo en su totalidad o infinito (DFS puede sufrir de no terminación ). En tales casos, la búsqueda solo se realiza a una profundidad limitada ; debido a los recursos limitados, como la memoria o el 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 el mismo que el tamaño de todo el gráfico porque algunos vértices pueden buscarse más de una vez y otros no 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 utilizando 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 de aspecto probable. Cuando no se conoce a priori un límite de profundidad adecuado, la búsqueda iterativa de profundización en profundidad 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 el que se conoce el límite de profundidad correcto debido al crecimiento geométrico del número de nodos por nivel.
El DFS también se puede utilizar para recopilar una muestra de nodos de gráficos. Sin embargo, el DFS incompleto, de manera similar al BFS incompleto , está sesgado hacia los 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 previamente 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. Los bordes recorridos en esta búsqueda forman un árbol Trémaux , una estructura con importantes aplicaciones en la teoría de grafos . Realizar la misma búsqueda sin recordar los nodos visitados previamente da como resultado visitar los nodos en el orden A, B, D, F, E, A, B, D, F, E, etc. para siempre, atrapado en el ciclo A, B, D, F, E y nunca llegando a C o G.
La profundización iterativa es una técnica para evitar este bucle infinito y alcanzaría todos los nodos.
El resultado de una búsqueda en profundidad de un grafo 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, las aristas del grafo original se pueden dividir en tres clases: aristas delanteras , que apuntan desde un nodo del árbol a uno de sus descendientes, aristas traseras , que apuntan desde un nodo a uno de sus ancestros, y aristas cruzadas , que no hacen ninguna de las dos cosas. A veces, las aristas del árbol , aristas que pertenecen al propio árbol de expansión, se clasifican por separado de las aristas delanteras. Si el grafo original no está dirigido, entonces todas sus aristas son aristas del árbol o aristas traseras.
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 hacerlo:
Para los árboles binarios existe además el ordenamiento interno y el ordenamiento inverso .
Por ejemplo, al buscar el gráfico dirigido que se muestra 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 las visitas repetidas en forma de retroceso a un nodo, para verificar si aún tiene vecinos sin visitar, se incluyen aquí (incluso si se descubre que no tiene ninguno). Por lo tanto, los posibles preordenamientos son ABDC y ACDB, mientras que los posibles posordenamientos son DBCA y DCBA, y los posibles posordenamientos inversos son ACBD y ABC D.
El ordenamiento posterior inverso produce una clasificación topológica de cualquier gráfico acíclico dirigido . Este ordenamiento también es útil en el análisis del 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 { do}DUna implementación recursiva de DFS: [5]
procedimiento DFS( G , v ) es etiqueta v como descubierto para todos los bordes dirigidos desde v hasta w que están en G.adjacentEdges ( v ) si el vértice w no está etiquetado como descubierto, entonces llama recursivamente a DFS( G , w )
Una implementación no recursiva de DFS con la complejidad espacial del peor caso , con la posibilidad de vértices duplicados en la pila: [6]
procedimiento DFS_iterative( G , v ) es dejar que S sea una pila S .push( v ) mientras S no esté vacía hacer v = S .pop() si v no está etiquetado como descubierto entonces etiquetar v como descubierto para todos los bordes desde v hasta w en G .adjacentEdges( v ) hacer S .push( w )
Estas dos variantes de DFS visitan a los vecinos de cada vértice en orden opuesto entre sí: el primer vecino de v visitado por la variante recursiva es el primero en la lista de aristas adyacentes, mientras que en la variante iterativa el primer vecino visitado es el último en la lista de aristas 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 por una pila producirá un algoritmo de búsqueda en profundidad. Para los grafos generales, reemplazar la pila de la implementación iterativa de búsqueda en profundidad por una cola también produciría un algoritmo de búsqueda en amplitud, aunque uno un tanto no estándar. [7]
Otra posible implementación de la búsqueda en profundidad iterativa 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 la búsqueda en profundidad recursiva. [8]
El procedimiento DFS_iterative( G , v ) es dejar que S sea una pila etiqueta v como descubierta S .push(iterador de G .adjacentEdges( v )) mientras S no esté vacío hacer si S .peek().hasNext() entonces w = S .peek().next() si w no está etiquetado como descubierto entonces etiqueta w como descubierto S .push(iterador de G .adjacentEdges( w )) de lo contrario S .pop()
Los algoritmos que utilizan la búsqueda en profundidad como elemento fundamental incluyen:
La complejidad computacional de DFS fue investigada por John Reif . Más precisamente, dado un gráfico , sea el orden calculado por el algoritmo DFS recursivo estándar. Este orden se llama ordenamiento de búsqueda en profundidad lexicográfica. John Reif consideró la complejidad de calcular el ordenamiento de búsqueda en profundidad lexicográfica, 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
Se puede calcular un ordenamiento de búsqueda en profundidad (no necesariamente lexicográfico) mediante un algoritmo paralelo aleatorio en la clase de complejidad RNC . [14] Hasta 1997, seguía sin saberse si se podía construir un recorrido en profundidad mediante un algoritmo paralelo determinista, en la clase de complejidad NC . [15]
