Búsqueda en profundidad primero

La búsqueda en profundidad ( DFS ) es un algoritmo para recorrer o buscar estructuras de datos de árbol o gráfico . 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 en la medida de lo posible a lo largo de cada rama antes de retroceder.

Búsqueda en profundidad primero

Orden en que se visitan los nodos
Clase	Algoritmo de búsqueda
Estructura de datos	Grafico
Rendimiento en el peor de los casos	${\displaystyle O(|V|+|E|)}$ para gráficos explícitos recorridos sin repetición, ${\displaystyle O(b^{d})}$para gráficos implícitos con factor de ramificación b buscado a profundidad d
Complejidad espacial en el peor de los casos	${\displaystyle O(|V|)}$ si se recorre todo el gráfico sin repetición, O (longitud de ruta más larga buscada) = ${\displaystyle O(bd)}$para gráficos implícitos sin eliminación de nodos duplicados

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 estrategia para resolver laberintos . ^{[2] [3]}

Propiedades

El análisis de tiempo y espacio 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${\displaystyle O(|V|+|E|)}$, ^[4] lineal en el tamaño del gráfico. En estas aplicaciones también utiliza el espacio.${\displaystyle O(|V|)}$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 de amplitud primero 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 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 rastreo web, el gráfico que se va a 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 expandidos (aunque este número no es el 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 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 primero en amplitud. Para tales aplicaciones, DFS también se presta mucho mejor a métodos heurísticos para elegir una rama de apariencia probable. Cuando no se conoce a priori un límite de profundidad apropiado, la búsqueda iterativa de profundización 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 sobre 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 utilizar para recopilar una muestra de nodos de gráficos. Sin embargo, incompleta DFS, de manera similar a incompletas BFS , está sesgada hacia los nodos de alto grado .

Ejemplo

Ejemplo animado de una búsqueda en profundidad

Para el siguiente gráfico:

una búsqueda en profundidad que comienza en el nodo A, asumiendo que los bordes izquierdos en el gráfico mostrado se eligen antes que los bordes derechos, y asumiendo 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 la 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 llegar a C o G.

La profundización iterativa es una técnica para evitar este bucle 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 expansión

Una descripción conveniente de una búsqueda en profundidad de un gráfico es 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 transversales , que no lo hacen. A veces, los bordes de los árboles , los bordes que pertenecen al árbol de expansión en sí, se clasifican por separado de los bordes delanteros. Si el gráfico original no está dirigido, todos sus bordes son bordes de árbol o bordes posteriores.

Pedido DFS

Se dice que una enumeración de los vértices de un gráfico es una ordenación DFS si es el resultado posible de la aplicación de DFS a este gráfico.

Dejar ${\displaystyle G=(V,E)}$ ser un gráfico con ${\displaystyle n}$vértices. Para${\displaystyle \sigma =(v_{1},\dots ,v_{m})}$ ser una lista de elementos distintos de ${\displaystyle V}$, por ${\displaystyle v\in V\setminus \{v_{1},\dots ,v_{m}\}}$, dejar ${\displaystyle \nu _{\sigma }(v)}$ ser el mejor ${\displaystyle i}$ tal que ${\displaystyle v_{i}}$ es vecino de ${\displaystyle v}$, si tal ${\displaystyle i}$ existe y ser ${\displaystyle 0}$ de lo contrario.

Dejar ${\displaystyle \sigma =(v_{1},\dots ,v_{n})}$ ser una enumeración de los vértices de ${\displaystyle V}$. La enumeración${\displaystyle \sigma }$ se dice que es un pedido DFS (con fuente ${\displaystyle v_{1}}$) si, para todos ${\displaystyle 1<i\leq n}$, ${\displaystyle v_{i}}$ es el vértice ${\displaystyle w\in V\setminus \{v_{1},\dots ,v_{i-1}\}}$ tal que ${\displaystyle \nu _{(v_{1},\dots ,v_{i-1})}(w)}$es máxima. Recordar que${\displaystyle N(v)}$ es el conjunto de vecinos de ${\displaystyle v}$. Equivalentemente,${\displaystyle \sigma }$ es un pedido DFS si, para todos ${\displaystyle 1\leq i<j<k\leq n}$ con ${\displaystyle v_{i}\in N(v_{k})\setminus N(v_{j})}$, existe un vecino ${\displaystyle v_{m}}$ de ${\displaystyle v_{j}}$ tal que ${\displaystyle i<m<j}$.

Ordenaciones 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 formas posibles de hacer esto:

• Un preorden es una lista de los vértices en el orden en que fueron visitados por primera vez por el algoritmo de búsqueda en profundidad. Esta es una forma compacta y natural de describir el progreso de la búsqueda, como se hizo anteriormente en este artículo. Un preorden de un árbol de expresión es la expresión en notación polaca .
• Un postordering es una lista de los vértices en el orden en que fueron visitados por última vez por el algoritmo. Una posordenación de un árbol de expresión es la expresión en notación polaca inversa .
• Un preorden inverso es el inverso de un preorden, es decir, una lista de los vértices en el orden opuesto de su primera visita. El pedido anticipado inverso no es lo mismo que el pedido posterior.
• Un postordering inverso es el reverso de un postordering, es decir, una lista de los vértices en el orden opuesto de su última visita. Postorder inverso no es lo mismo que preordenar.

En el caso de los árboles binarios, existe además el orden y el orden inverso .

Por ejemplo, cuando se busca en el gráfico dirigido a continuación comenzando en el nodo A, la secuencia de recorridos es ABDBACA o ACDCABA (elegir 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 comprobar si todavía tiene vecinos no visitados, se incluyen aquí (incluso si se encuentra que no tiene ninguno). Por lo tanto, los posibles pedidos anticipados son ABDC y ACDB, mientras que los posibles pedidos anticipados son DBCA y DCBA, y los posibles pedidos anticipados son ACBD y ABC D.

El posordenamiento 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 puede representar el flujo de control en el fragmento de código a continuación, 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}D

Pseudocódigo

Entrada : un gráfico G y un vértice v de G

Salida : todos los vértices accesibles desde v etiquetados como descubiertos

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

procedimiento DFS ( G , v ) es la etiqueta v como descubrió para todos los bordes dirigidos de v a w que son  en  G .adjacentEdges ( v ) hacer  si vértice w no se etiqueta como descubierto luego recursivamente llamar DFS ( G , w )

El orden en que este algoritmo descubre los vértices se denomina orden lexicográfico . ^{[ cita requerida ]}

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

procedimiento DFS_iterative ( G , v ) es vamos S ser una pila S .push ( v ) , mientras que  S no está vacío do  v = S .pop () si  v no está etiquetado como descubierto entonces etiqueta v como descubrió para todos los bordes de v a w  en  G .adjacentEdges ( v ) hacer  S .push ( w )

Estas dos variaciones de DFS visitan a los vecinos de cada vértice en el orden opuesto entre sí: el primer vecino de v visitado por la variación recursiva es el primero en la lista de bordes 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 de dos maneras:

1. usa una pila en lugar de una cola, y
2. 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 agregar el vértice.

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 primero 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]

procedimiento DFS_iterative ( G , v ) es dejar que S sea ​​una pila S .push (iterador de G .adjectedEdges ( v )) mientras que  S no está vacío hacer  si  S .peek (). hasNext () entonces  w = S .peek () .next () si  w no está etiquetado como descubierto, entonces etiquete w como descubierto S .push (iterador de G .adjectedEdges ( w )) else  S .pop () 

Aplicaciones

"> Reproducir medios

Algoritmo aleatorio similar a la búsqueda en profundidad que se utiliza para generar un laberinto.