Depth first Search o Depth first traversal es un algoritmo recursivo para buscar todos los vértices de un gráfico o estructura de datos de árbol. Traversal significa visitar todos los nodos de un gráfico.

algoritmo de búsqueda de profundidad

una implementación DFS estándar coloca cada vértice del gráfico en una de dos categorías:

1. Visited
2. Not Visited

el propósito del algoritmo es marcar cada vértice como visitado evitando ciclos.,

el algoritmo DFS funciona de la siguiente manera:

1. comience poniendo cualquiera de los vértices del gráfico sobre una pila.
2. Tome el elemento superior de la pila y agréguelo a la lista visitada.
3. Crear una lista de los nodos adyacentes de ese vértice. Agregue los que no están en la lista visitada a la parte superior de la pila.
4. siga repitiendo los pasos 2 y 3 hasta que la pila esté vacía.

ejemplo de búsqueda de profundidad primero

veamos cómo funciona el algoritmo de búsqueda de profundidad primero con un ejemplo. Usamos un grafo no dirigido con 5 vértices.,

comenzamos desde el vértice 0, el algoritmo DFS comienza poniéndolo en la lista visitada y poniendo todos sus vértices adyacentes en la pila.

a continuación, visitamos el elemento en la parte superior de la pila es decir, 1 e ir a sus nodos adyacentes. Como 0 ya ha sido visitado, visitamos 2 en su lugar.,

Vértice 2 tiene un poco visitada adyacentes vértice en 4, por eso añadimos a la parte superior de la pila y lo visite.

después de visitar el último elemento 3, no tiene nodos adyacentes no visitados, por lo que hemos completado el primer recorrido de profundidad del gráfico.,

pseudocódigo DFS (implementación recursiva)

el pseudocódigo para DFS se muestra a continuación. En la función init (), observe que ejecutamos la función DFS en cada nodo. Esto se debe a que el gráfico puede tener dos partes desconectadas diferentes, por lo que para asegurarnos de que cubrimos cada vértice, también podemos ejecutar el algoritmo DFS en cada nodo.,

DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}

implementación de DFS en Python, Java y C/C++

a continuación se muestra el código para el algoritmo Depth First Search con un ejemplo. El código se ha simplificado para que podamos centrarnos en el algoritmo en lugar de otros detalles.

complejidad de la profundidad primera búsqueda

la complejidad temporal del algoritmo DFS se representa en forma deO(V + E), dondeVes el número de nodos yE es el número de bordes.

la complejidad espacial del algoritmo es O(V).,

aplicación del algoritmo DFS

1. para encontrar la ruta
2. Para probar si el gráfico es bipartito
3. para encontrar los componentes fuertemente conectados de un gráfico
4. para detectar ciclos en un gráfico