El algoritmo Depth-First Search (DFS), conocido en español como Búsqueda en Profundidad, es uno de los pilares de la informática moderna. Se utiliza para recorrer grafos, árboles y redes, y su comprensión es fundamental para quienes estudian algoritmos, inteligencia artificial o estructuras de datos.
A su vez, DFS no solo permite encontrar caminos y conexiones, sino que también es la base de técnicas más avanzadas como la detección de ciclos, el ordenamiento topológico, los métodos de backtracking, o la generación procedural de laberintos. En este artículo, exploraremos su funcionamiento paso a paso con la correspondiente implementación en Python.
EN QUE CONSISTE.
El Depth-First Search es un método para explorar un grafo o árbol y visitar todos sus nodos siguiendo una estrategia que puede ser resumida de forma muy simple: Ir tan profundo como sea posible antes de retroceder. En otras palabras, el algoritmo elige un nodo inicial, lo visita, y luego sigue uno de sus caminos hasta el final, hasta llegar a un punto sin salida (un nodo sin vecinos no visitados), retrocediendo en ese caso al último punto con opciones disponibles para continuar desde allí. Este comportamiento lo convierte en una herramienta ideal para exploraciones exhaustivas, problemas de búsqueda de caminos, y análisis de conectividad.
EJEMPLO EN PYTHON.
Una vez visto someramente, en que consiste este algoritmo, vamos a ver un sencillo ejemplo de implementación en Python, que, a su vez, nos ayudará a entender mejor su forma de operar.
Para ello, deberemos empezar, definiendo el grafo que vamos a recorrer con nuestro algoritmo. Esto lo haremos mediante un diccionario cuyos pares clave – valor, vendrá a representar los nodos padre y los nodos hijos (aquellos que están conectados a los anteriores) respectivamente. Para nuestro ejemplo vamos a crear una variable a la que llamaremos ‘grafo‘ que representará el mostrado en la animación sobre estas líneas:
Tras esto, procederemos a definir la función ‘dfs()‘ mediante la que recorreremos nuestro grafo haciendo uso del referido algoritmo de ‘Búsqueda en Profundidad‘. Esto se hará de forma iterativa mediante la inicialización de un conjunto visitado (variable ‘visitado’) para registrar los nodos ya explorados y evitar visitas repetidas, y una lista (variable ‘pila’) que servirá como contenedor LIFO (último en entrar, primero en salir):
Así, El nodo inicial se marca como visitado y se añade a la pila. Luego, mientras la pila no esté vacía, se extrae el nodo superior y se imprime su valor. Tras ello, se recorren sus vecinos en orden inverso (con ‘reversed()‘), de modo que el primero en la lista original sea procesado antes cuando se apilen los nodos. Para cada vecino no visitado, se agrega al conjunto ‘visitado’ y se apila, repitiendo el proceso hasta que todos los nodos accesibles desde el nodo inicial hayan sido explorados. De este modo, el algoritmo sigue las ramas del grafo hasta llegar a sus extremos antes de retroceder, cumpliendo con la naturaleza recursiva en que el recorrido en profundidad consiste.
Finalmente, para la ejecución de nuestro algoritmo, simplemente tendremos que llamar a la función ‘dfs()‘ pasándole como argumentos, el grafo que pretendemos recorrer así como el nodo a partir queremos iniciar el proceso. La función ‘print()‘ incluida en ‘dfs()‘ nos irá imprimiendo cada nodo a medida que vaya siendo visitado:
OUTPUT:
CONCLUSIÓN:
El algoritmo Depth-First Search (DFS) es una herramienta fundamental en la informática y la teoría de grafos. Su implementación en Python resulta especialmente didáctica por la claridad del lenguaje y el uso de estructuras simples como listas y conjuntos. Ya sea mediante un enfoque iterativo con una pila o de forma recursiva, DFS permite recorrer de manera sistemática todos los nodos alcanzables desde un punto de partida, profundizando primero antes de explorar caminos alternativos. Comprender su funcionamiento no solo fortalece las bases de la programación algorítmica, sino que también sienta las bases para abordar técnicas más avanzadas como los recorridos BFS, los algoritmos de grafos ponderados o la búsqueda en inteligencia artificial.
Saludos.
El Programador Chapuzas 