Búsqueda en profundidad

En informática , la búsqueda en profundidad ( DFS ) es un algoritmo para recorrer o buscar en estructuras de datos de árboles o grafos . El algoritmo comienza en el nodo raíz (seleccionando un nodo arbitrario como raíz en el caso de un grafo) y explora lo más lejos posible a lo largo de cada rama antes de retroceder. Se necesita memoria adicional, generalmente una pila , para mantener un registro de los nodos descubiertos hasta el momento a lo largo de una rama específica, lo que facilita el retroceso en el grafo.

Una versión de la búsqueda en profundidad fue investigada en el siglo XIX por el matemático francés Charles Pierre Trémaux ^{[ 1 ]} como una estrategia para resolver laberintos . ^{[ 2 ] [ 3 ]}

El análisis de tiempo y espacio de DFS difiere según su área de aplicación. En la informática teórica, DFS se utiliza normalmente para recorrer un grafo completo y requiere tiempo.${\displaystyle O(|V|+|E|)}$, ^{[ 4 ]} donde${\displaystyle |V|}$es el número de vértices y${\displaystyle |E|}$el número de aristas . Esto es lineal en el tamaño del grafo. En estas aplicaciones también utiliza espacio.${\displaystyle O(|V|)}$En el peor de los casos, se almacena 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 este contexto, 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 utilizar depende menos de su complejidad y más de las diferentes propiedades de los ordenamientos de vértices que producen.

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 grafo a recorrer suele ser demasiado grande para visitarlo por completo o infinito (DFS puede sufrir de no terminación ). En tales casos, la búsqueda se realiza solo hasta una profundidad limitada ; debido a los recursos limitados, como la memoria o el espacio en disco, normalmente no se utilizan estructuras de datos para mantener un registro del conjunto de todos los vértices visitados previamente. Cuando la búsqueda se realiza hasta una profundidad limitada, el tiempo sigue siendo lineal en términos del número de vértices y aristas expandidos (aunque este número no es igual al tamaño del grafo completo, ya que algunos vértices pueden buscarse más de una vez y otros ninguna), 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 anchura. 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 de antemano un límite de profundidad adecuado, la búsqueda en profundidad iterativa aplica repetidamente la DFS 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 búsqueda en profundidad iterativa aumenta el tiempo de ejecución solo en un factor constante con respecto al 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 puede utilizarse para recopilar una muestra de nodos de un grafo. Sin embargo, el DFS incompleto, al igual que el BFS incompleto , está sesgado hacia nodos de alto grado .

Para el siguiente gráfico:

Una búsqueda en profundidad que comience en el nodo A, suponiendo que las aristas izquierdas del grafo mostrado se eligen antes que las derechas, y suponiendo que la búsqueda recuerde los nodos visitados previamente y no los repita (ya que se trata de un grafo 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 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., indefinidamente, quedando atrapado en el ciclo A, B, D, F, E y sin llegar nunca a C o G.

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

El resultado de una búsqueda en profundidad de un grafo se puede describir convenientemente mediante un árbol de expansión formado por los vértices alcanzados durante la búsqueda. A partir de este árbol de expansión, las aristas del grafo original se pueden clasificar en tres tipos: aristas directas , que apuntan desde un nodo del árbol a uno de sus descendientes; aristas inversas , que apuntan desde un nodo a uno de sus ancestros; y aristas cruzadas , que no realizan ninguna de las dos funciones. En ocasiones, las aristas del árbol , que pertenecen al propio árbol de expansión, se clasifican por separado de las aristas directas. Si el grafo original no está dirigido, todas sus aristas son del árbol o inversas.

si ( A ) entonces { B } demás { do } D

Una implementación recursiva de DFS: ^{[ 5 ]}

El procedimiento DFS( G , v ) etiqueta v como descubierto para todos los bordes dirigidos de v a w que están en G .adjacentEdges( v ) hacer si el vértice w no está etiquetado como descubierto entonces llamar recursivamente a DFS( G , w )

Una implementación no recursiva de DFS con complejidad espacial en el peor de los casos.${\displaystyle O(|E|)}$, con la posibilidad de vértices duplicados en la pila: ^{[ 6 ]}

El procedimiento DFS_iterative( G , v ) es: sea S 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 de v a w en G .adjacentEdges( v ) hacer S .push( w )

Estas dos variantes de DFS visitan los vecinos de cada vértice en orden inverso: 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 grafo de ejemplo en el siguiente orden: A, B, D, F, E, C, G. La implementación no recursiva visitará los nodos en el siguiente orden: A, E, F, B, D, C, G.

La implementación no recursiva es similar a la búsqueda en anchura, pero difiere de ella en dos aspectos:

1. utiliza una pila en lugar de una cola, y
2. Esto retrasa la comprobación de si se ha descubierto un vértice hasta que el vértice se extrae de la pila, en lugar de realizar esta comprobación 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 dará como resultado un algoritmo de búsqueda en profundidad. Para grafos 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 anchura, aunque algo 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 sea S una pila etiqueta v como descubierto 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 )) sino S .pop()

Los algoritmos que utilizan la búsqueda en profundidad como elemento básico incluyen:

• Encontrar componentes conectados .
• Ordenación topológica .
• Encontrar componentes 2-(aristas o vértices)-conexas.
• Encontrar componentes conexas de 3 (aristas o vértices).
• Encontrar los puentes de un grafo.
• 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 o de otra en un árbol filogenético.
• Prueba de planaridad . ^{[ 9 ] [ 10 ]}
• Resolver rompecabezas con una sola solución, como laberintos . (El algoritmo DFS se puede adaptar para encontrar todas las soluciones de un laberinto incluyendo solo los nodos del camino actual en el conjunto visitado).
• La generación de laberintos puede utilizar un DFS aleatorio.
• Cómo encontrar biconectividad en grafos .
• Sucesión al trono compartida por los reinos de la Commonwealth . ^{[ 11 ]}

La complejidad computacional de DFS fue investigada por John Reif . Más precisamente, dado un grafo${\displaystyle G}$, dejar${\displaystyle O=(v_{1},\dots,v_{n})}$sea ​​el ordenamiento calculado por el algoritmo DFS recursivo estándar. Este ordenamiento se denomina 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 grafo y una fuente. Una versión de decisión del problema (probar si algún vértice u aparece antes que 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 ordenamiento de búsqueda en profundidad (no necesariamente el lexicográfico) puede ser calculado por un algoritmo paralelo aleatorio en la clase de complejidad RNC . ^{[ 14 ]} Hasta 1997, seguía siendo desconocido si un recorrido en profundidad podía ser construido por un algoritmo paralelo determinista, en la clase de complejidad NC . ^{[ 15 ]}

• Búsqueda en anchura : algoritmo para buscar en los nodos de un grafo. 
• Búsqueda en profundidad iterativa: estrategia de búsqueda en árbol. 
• Juego de búsqueda : juego de suma cero para dos personas 
• Recorrido de árboles : para obtener detalles sobre el recorrido en profundidad en preorden, en orden y en postorden

• Estructuras de datos abiertas - Sección 12.3.2 - Búsqueda en profundidad , Pat Morin
• Biblioteca C++ Boost Graph: Búsqueda en profundidad
• Animación de búsqueda en profundidad (para un grafo dirigido)
• Búsqueda en profundidad y búsqueda en amplitud: explicación y código.
• Explicación ilustrada del algoritmo de búsqueda en profundidad (implementaciones en Java y C++)
• YAGSBPL: una biblioteca C++ basada en plantillas para la búsqueda y planificación de grafos.
• Visualización de la búsqueda en profundidad