Búsqueda en profundidad

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 lejos 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 investigó una versión de la búsqueda en profundidad como estrategia para resolver laberintos.

Propiedades

El análisis de tiempo y espacio del DFS difiere según su área de aplicación. En la ciencia informática teórica, el DFS se utiliza típicamente para atravesar un gráfico entero, y toma tiempo O()SilencioVSilencio+SilencioESilencio){displaystyle O(vivienda), Donde SilencioVSilencio{displaystyle Silencioso es el número de vértices y SilencioESilencio{displaystyle Silencioso el número de bordes. Esto es lineal en el tamaño del gráfico. En estas aplicaciones también utiliza espacio O()SilencioVSilencio){displaystyle O(vivienda)} en el peor caso para almacenar la pila de vértices en el camino de búsqueda actual, así como el conjunto de vértices ya vistos. Así, en este entorno, el tiempo y los límites del espacio son los mismos que para la búsqueda de la primera y la elección de cuál de estos dos algoritmos a utilizar depende menos de su complejidad y más de las diferentes propiedades del vértice que ordena los dos algoritmos producen.

Para las 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 va a recorrer suele ser demasiado grande para visitarlo en su totalidad o infinito (DFS puede sufrir 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 del gráfico completo porque algunos vértices pueden buscarse más de una vez y otros en absoluto), pero la complejidad del espacio de esta variante de DFS es solo proporcional al límite de profundidad y, como resultado, es mucho más pequeño que el espacio necesario para buscar a la misma profundidad utilizando la búsqueda en anchura. 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 apropiado, la búsqueda primero en profundidad iterativa 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..

DFS también se puede usar para recopilar una muestra de nodos de gráfico. Sin embargo, el DFS incompleto, al igual que el BFS incompleto, está sesgado hacia nodos de alto grado.

Ejemplo

Ejemplo animado de una búsqueda de profundidad

Para el siguiente gráfico:

una búsqueda en profundidad que comienza en el nodo A, suponiendo que los bordes izquierdos del 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á (dado que se trata de un gráfico pequeño), visitará los nodos en el siguiente orden: A, B, D, F, E, C, G. Las aristas recorridas 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 llegando a C o G.

La profundización iterativa es una técnica para evitar este ciclo infinito y llegaría a todos los nodos.

Resultado de una búsqueda en profundidad

Los cuatro tipos de bordes definidos por un árbol de azotes

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. Según 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 ancestros, y aristas cruzadas, que no lo hacen. A veces, los bordes de árbol, que pertenecen al propio árbol de expansión, se clasifican por separado de los bordes anteriores. Si el gráfico original no está dirigido, todos sus bordes son bordes de árbol o bordes posteriores.

Ordenamiento de vértices

También es posible utilizar la búsqueda en profundidad para ordenar linealmente los vértices de un gráfico o árbol. Hay cuatro maneras posibles de hacer esto:

• A preordenación es una lista de los vértices en el orden que fueron visitados por primera vez por el algoritmo de búsqueda de profundidad primero. Esta es una forma compacta y natural de describir el progreso de la búsqueda, como se hizo anteriormente en este artículo. Un preordenamiento de un árbol de expresión es la expresión en la notación polaca.
• A postordenación es una lista de los vértices en el orden que eran último visitado por el algoritmo. Un postordenamiento de un árbol de expresión es la expresión en la notación polaca inversa.
• A preordenación inversa es el reverso de un preordenamiento, es decir, una lista de los vértices en el orden opuesto de su primera visita. El preordenamiento inverso no es el mismo que el postordenamiento.
• A postordenación inversa es el reverso de un postordenamiento, es decir, una lista de los vértices en el orden opuesto de su última visita. La postordenación inversa no es lo mismo que la preordenación.

Para los árboles binarios existe además ordenamiento interno y ordenamiento interno inverso.

Por ejemplo, al buscar el siguiente gráfico dirigido que comienza en el nodo A, la secuencia de recorridos es A B D B A C A o A C D C A B A (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 todavía tiene vecinos no visitados, se incluyen aquí (incluso si se descubre que no tiene ninguno). Así, los posibles pedidos previos son A B D C y A C D B, mientras que los posibles pedidos posteriores son D B C A y D C B A, y los posibles pedidos posteriores inversos son A C B D y A B C D.

La ordenación posterior inversa produce una ordenació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 A B C D o A C B D, pero no es natural usar el orden A B D C o A C D B.

siAEntonces...
 B. ♫... {
 C}
D

Pseudocódigo

Entrada: Salida: Una implementación recursiva de DFS:

procedimiento DFS(G, v) esetiqueta v como descubierto
 para todos bordes dirigidos desde v a que son dentro G.adjacentEdges(v) do si vertex w no está etiquetado como descubierto entoncesrecurrentemente llame a DFS(G, w)

Aplicación no recursiva del DAAT con la peor complejidad espacial O()SilencioESilencio){displaystyle O(viviendas)}, con la posibilidad de vertices duplicados en la pila:

procedimiento DFS_iterative(G, v) esDeja S ser una pila
 S.push(v)
 mientras S no está vacío do v = S.pop()
 si v no está etiquetado como descubierto entoncesetiqueta v como descubierto
 para todos bordes de v a w dentro G.adjacentEdges(v) do S.push(w)

Estas dos variaciones de DFS visitan los vecinos de cada vértice en orden opuesto: 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:

1. usa una pila en lugar de una cola, y
2. retrasa comprobar si un vértice ha sido descubierto hasta que el vértice se salta de la pila en lugar de hacer este cheque antes de añadir el vértice.

Si G es un árbol, reemplazar la cola del algoritmo de búsqueda en anchura con una pila producirá una profundidad- primer algoritmo de búsqueda. Para gráficos generales, reemplazar la pila de la implementación iterativa de búsqueda primero en profundidad con una cola también produciría un algoritmo de búsqueda primero en amplitud, aunque algo no estándar.

Otra posible implementación de la búsqueda primero 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 el DFS recursivo.

procedimiento DFS_iterative(G, v) esDeja S ser una pila
etiqueta v como descubierto
 S.push G.adjacentEdges(v)
 mientras S no está vacío do si S.peek().hasNext() entonces w = S.peek().next()
 si w no está etiquetado como descubierto entoncesetiqueta w como descubierto
 S.push G.adjacentEdges(w)
 más S.pop()

Aplicaciones

Los algoritmos que utilizan la búsqueda primero en profundidad como bloque de construcción incluyen:

• Encontrar componentes conectados.
• Clasificación topológica.
• Encontrar componentes conectados con 2-(edge o vertex).
• Encontrar componentes conectados con 3-(edge o vertex).
• Encontrar los puentes de un gráfico.
• Generar palabras para trazar el conjunto límite de un grupo.
• Encontrar componentes fuertemente conectados.
• Determinar si una especie está más cerca de una especie u otra en un árbol filogenético.
• Pruebas de Planaridad.
• Solución de rompecabezas con una sola solución, como laberintos. (Las Fuerzas de Defensa pueden adaptarse para encontrar todas las soluciones a un laberinto incluyendo solamente los nodos en el camino actual en el conjunto visitado.)
• La generación de laberinto puede utilizar un DFS aleatorizado.
• Encontrar biconectividad en gráficos.
• Sucesión al trono compartida por los reinos del Commonwealth.

Complejidad

John Reif investigó la complejidad computacional del DFS. Más precisamente, dado un gráfico G{displaystyle G., vamos O=()v1,...... ,vn){displaystyle O=(v_{1},dotsv_{n}} ser el pedido computado por el algoritmo DFS recursivo estándar. Este pedido se llama la orden de búsqueda de profundidad léxicográfica. John. Reif consideró la complejidad de la computación de la orden de búsqueda de profundidad léxicográfica, dada un gráfico y una fuente. Una versión de decisión del problema (prueba si algún vértice u ocurre antes de un vértice v en este orden) es P-completo, lo que significa que es "una pesadilla para el procesamiento paralelo".

Se puede calcular un orden de búsqueda en profundidad (no necesariamente lexicográfico) mediante un algoritmo paralelo aleatorio en la clase de complejidad RNC. A partir de 1997, se desconocía si un recorrido de profundidad primero podría construirse mediante un algoritmo paralelo determinista, en la clase de complejidad NC.