Estimados lectores, en este artículo los guiaré a través del concepto de Búsqueda en Profundidad Primero (DFS). Este es un concepto de gráfico que es un problema común en muchos exámenes de codificación competitivos. Por lo tanto, veamos la creación de un recorrido DFS usando Python.
Tabla de Contenidos
¿Qué es la Búsqueda en Profundidad Primero?
La búsqueda en profundidad es un algoritmo que hace uso de la estructura de datos de pila para recorrer gráficos y árboles. El concepto de búsqueda en profundidad viene de la palabra «profundidad». El árbol atraviesa hasta la profundidad de una rama y luego regresa al resto de los nodos.
Considere una «pila» vacía que contenga los nodos visitados para cada iteración. Nuestra tarea aquí es la siguiente:
- Comience en el nodo raíz y empújelo a la pila.
- Compruebe si hay nodos adyacentes del árbol y seleccione un nodo.
- Atravesar toda la rama del nodo seleccionado y empujar todos los nodos en la pila.
- Al llegar al final de una rama (no más nodos adyacentes), es decir, enésimo nodo de hoja, retroceda un solo paso y busque nodos adyacentes del nodo n-1.
- Si hay nodos adyacentes para el nodo n-1, atraviese esas ramas y empuje nodos a la pila.
Concepto de Profundidad Primera búsqueda Ilustrada
Echemos un vistazo a nuestro gráfico de ejemplo a continuación:
A es el nodo raíz. Así que desde que A es visitado, empujamos esto a la pila.
Stack : A
Vamos a la rama A-B. B no es visitada, así que vamos a B y empujamos B a la pila.
Stack : A B
Ahora, hemos llegado al final de nuestra rama A-B y nos movemos al nodo n-1 que es A. Ahora miraremos el nodo adyacente de A que es S. Visitamos S y lo empujamos a la pila. Ahora tienes que atravesar la rama S-C-D, hasta la profundidad es decir hasta D y marcar S, C, D como visitado.
Stack: A B S C D
Dado que D no tiene otros nodos adyacentes, regrese a C y atraviese su rama adyacente E-H-G hasta la profundidad y empújelos hacia la pila.
Stack : A B S C D E H G
Al llegar a D, solo hay un nodo adyacente, es decir, F, que no se visita. Empuje F en la pila también.
Stack : A B S C D E H G F
Esta pila en sí es el recorrido del DFS.
Profundidad de codificación Primer algoritmo de búsqueda en Python
Como debe saber, hay muchos métodos para representar un gráfico que es la lista de adyacencia y la matriz de adyacencia.
Así que en el siguiente ejemplo, he definido una lista de adyacencia para cada uno de los nodos de nuestro gráfico.
graph1 = { 'A' : , 'B' : , 'C' : , 'D' : , 'E' : , 'F' : , 'G' : , 'H' : , 'S' : }
Nota: Esta lista de adyacencia se puede introducir desde el usuario y no es necesario que esté codificada.
Ahora, definiremos nuestra función DFS que toma 3 parámetros como entrada: el gráfico (lista de adyacencia), un nodo y una lista de nodos visitados.
Si el nodo actual no está visitado, es decir, no está presente en la lista visitada, márquelo como visitado y añádalo a la lista visitada.
Pasar al siguiente nodo y, a continuación, pasar recursivamente este nodo a la función DFS. De esta manera, cada nodo se mueve hasta la profundidad y lo imprime como la salida DFS.
def dfs(graph, node, visited): if node not in visited: visited.append(node) for k in graph: dfs(graph,k, visited) return visitedvisited = dfs(graph1,'A', )print(visited)
Código Completo y Salida
graph1 = { 'A' : , 'B' : , 'C' : , 'D' : , 'E' : , 'F' : , 'G' : , 'H' : , 'S' : }def dfs(graph, node, visited): if node not in visited: visited.append(node) for k in graph: dfs(graph,k, visited) return visitedvisited = dfs(graph1,'A', )print(visited)
La salida del código anterior es el siguiente:
Conclusión
espero que haya seguido este tutorial en el algoritmo DFS y han sido capaces de entender el código y el ejemplo así. Pruébelo usando lápiz y papel a su lado para comprender mejor los traversals.