DFS (primer recorrido en profundidad) en la estructura de datos: qué es, pedidos y aplicaciones

Significado de DFS en la estructura de datos

DFS en estructura de datos, también conocido como recorrido primero en profundidad, es un algoritmo recursivo que se utiliza principalmente para buscar todos los vértices de una estructura de datos de gráfico o árbol. Recorrido es la visita de cada nodo de un gráfico. El algoritmo comienza desde el nodo raíz (que puede ser un nodo arbitrario como el nodo raíz en un gráfico) y llega tan lejos como puede a lo largo de cada rama antes de retroceder.

La idea es comenzar desde la raíz o el nodo arbitrario y mantener el nodo marcado. Después de esto, debe pasar al nodo adyacente que no está marcado y continuar este bucle hasta que no haya ningún nodo contiguo sin marcar. Luego retroceda y examine los otros nodos que no están marcados y atraviéselos. El paso final es imprimir los nodos dentro de la ruta.

Algoritmo

Formule una función recursiva que tomará el índice del nodo y una matriz visitada.

1. Mantenga el nodo actual marcado como visitado y luego imprímalo.
2. Recorra todas las notas contiguas y las no marcadas y llame a la función recursiva con el índice del nodo contiguo.

Explore nuestros cursos populares de ingeniería de software

Propiedades

El análisis de tiempo y espacio en los SFD en Estructura de Datos varía según su área de aplicación. Teóricamente, DFS se usa principalmente para cruzar un gráfico completo y toma el tiempo O(|V|+|E|) donde |V| representa el número de vértices y |E| representa el número de aristas. Este gráfico es lineal.

En estas aplicaciones, el espacio O(|V|) también se usa como último recurso para mantener la pila de vértices almacenada en la ruta de búsqueda y el conjunto de vértices que ya se visitaron. Por lo tanto, la configuración de los límites de tiempo y espacio es similar a la búsqueda en amplitud. Aquí, los dos algoritmos utilizados dependen menos de su complejidad y más de las diversas características de los órdenes de vértices producidos por los dos algoritmos.

Cuando se trata de aplicaciones de DFS en la estructura de datos relacionadas con dominios específicos, como encontrar soluciones en el rastreo web o la IA, el gráfico que requiere atravesar puede ser demasiado importante para visitarlo en su totalidad. En tales casos, la búsqueda solo se ejecuta a una profundidad restringida; debido a recursos finitos, como espacio en disco o memoria. Las estructuras de datos normalmente no se usan para rastrear el conjunto de todos los vértices visitados anteriormente. Una búsqueda realizada a una profundidad restringida todavía hace que el tiempo sea lineal cuando se trata de la unidad de aristas y vértices expandidos.

Sin embargo, recuerde que este número no tiene el mismo tamaño que el gráfico completo, ya que algunos de los vértices pueden buscarse varias veces y otros no.

En tales casos, DFS también recurre a métodos heurísticos para seleccionar una rama más prometedora. Finalmente, cuando no se puede determinar el límite de profundidad apropiado, se aplica repetidamente DFS de profundización iterativa a priori a través de una secuencia de límites crecientes.

Aprenda cursos de desarrollo de software en línea de las mejores universidades del mundo. Obtenga Programas PG Ejecutivos, Programas de Certificado Avanzado o Programas de Maestría para acelerar su carrera.

Algoritmo de búsqueda de profundidad primero

Cada vértice de un gráfico en una implementación DFS estándar se divide en dos categorías:

1. No visitado
2. Visitado

El algoritmo se utiliza para identificar cada vértice y marcarlos como visitados y al mismo tiempo evitar ciclos.

Así es como funciona el algoritmo DFS:

1. Coloque cualquier vértice particular del gráfico en una pila.
2. El elemento en la parte superior de la pila debe agregarse a la lista visitada.
3. Haga una lista de los nodos contiguos de ese vértice y agregue los que no están en la lista visitada en la parte superior de la pila.
4. Siga repitiendo los pasos anteriores hasta que la pila se vacíe.

pedidos de DFS

Ordenamiento de vértices: hay cuatro formas de ordenar linealmente los vértices de un gráfico o árbol en DFS:

1. La lista de los vértices organizados de la forma en que fueron visitados por primera vez por el algoritmo DFS se conoce como pedido previo. Es una forma concisa de describir el progreso de la búsqueda.
2. La lista de los vértices en el orden en que fueron visitados por última vez por el algoritmo se conoce como ordenación posterior.
3. La lista de los vértices en el orden opuesto a su primera visita es un orden previo inverso. Por lo tanto, no debe confundirse con pedidos posteriores.
4. La lista de los vértices en el orden opuesto a su última visita es un orden posterior inverso. No debe confundirse con un pedido anticipado.

Además, existe el orden interno y el orden interno inverso para los árboles binarios.

Primera búsqueda en profundidad o DFS para un gráfico

El DFS para un gráfico es casi el mismo que el DFS para un árbol. La única diferencia es que los gráficos pueden tener ciclos, a diferencia de los árboles. Un nodo puede ser visitado varias veces y para evitar procesar el nodo, se utiliza una matriz visitada booleana.

Salida de una primera búsqueda en profundidad

La búsqueda primero en profundidad se representa más fácilmente en términos de un árbol de expansión de los vértices que ya se alcanzaron en la búsqueda. Según este árbol de expansión, los bordes del gráfico original se dividen en tres clases: los bordes delanteros, donde el nodo del árbol apunta hacia uno de sus descendientes, los bordes posteriores, donde el nodo apunta hacia uno de sus ancestros, y los bordes cruzados , que no realiza ninguna de las funciones anteriores.

Aplicaciones de Profundidad Primero Traversal (DFS)

La búsqueda en profundidad se utiliza en los siguientes algoritmos como bloque de construcción:

• Búsqueda de componentes que están conectados.
• Encontrar componentes conectados en 2 (vértices o aristas).
• Encontrar los puentes del gráfico.
• Encontrar componentes conectados en 3 (vértices o aristas).
• Clasificación topológica.
• Encontrar componentes que estén fuertemente conectados.
• Averiguar si una especie es similar a una u otra especie en un árbol filogenético.
• Pruebas de planaridad.
• Producir palabras para determinar el conjunto límite de cualquier grupo.
• Resolver acertijos que tienen una sola solución, como laberintos.
• Generación de laberintos .
• Búsqueda de bi-conectividad en grafos.

Pseudocódigo DFS e implementación en Python

La función init() se ejecuta en cada nodo en el pseudocódigo a continuación para garantizar que se visiten todos los vértices. Esto es especialmente importante ya que los gráficos pueden tener varias áreas desconectadas.

Aquí está el pseudocódigo:

SLE(G, u)

u.visitado = verdadero

para cada v ∈ G.Adj[u]

si v.visitado == falso

SLE(G,v)

en eso() {

Para cada u ∈ G

u.visitado = false

Para cada u ∈ G

SLE(G, u)

}

Aquí está la implementación de DFS en Python:

gráfico = {

'5': ['3','7'],

'2' : ['1', '3'],

'6' : ['7'],

'3': [],

'4' : ['6'],

'7': []

}

visitado = conjunto ()

def dfs(visitado, gráfico, nodo):

si el nodo no está en visitado:

imprimir (nodo)

visitado.add(nodo)

para vecino en gráfico[nodo]:

dfs(visitado, gráfico, vecino)

imprimir ("Este es el DFS:")

dfs(visitado, gráfico, '5')

Producción:

Este es el DFS: 5

Explore nuestros cursos populares de ingeniería de software

La complejidad de la primera búsqueda en profundidad

John Reif exploró la complejidad computacional de Depth First Search. Para ser precisos, en un gráfico, el hecho dado es G, sea O el orden estándar determinado por el algoritmo DFS repetitivo. G representa el gráfico y O representa la salida de pedido del algoritmo DFS redundante. Esta salida se conoce como el orden lexicográfico DFS.

Conclusión

El objetivo principal del algoritmo DFS es visitar cada uno de los vértices que evita ciclos en los gráficos de destino. Si desea participar en implementaciones avanzadas de operaciones de búsqueda u operaciones de pedido, definitivamente debería considerar seguir un curso premium y holístico en Búsqueda profunda y estructura de datos.

upGrad tiene algunos cursos DFS de primer nivel como Maestría en Ciencias en Ciencias de la Computación y Especialización en Big Data .

Si tiene dificultades para dar el siguiente paso y busca el consejo de un experto, upGrad Mentorship busca brindarle sesiones individuales con los mejores asesores profesionales y expertos de la industria.