Búsqueda en profundidad (DFS)
Entra en un laberinto, sigue hasta dar con un callejón sin salida, vuelve a la última bifurcación y prueba el siguiente camino. La búsqueda en profundidad explora un grafo de la misma forma. Es uno de los algoritmos de grafos más sencillos, y la pila que mantiene dice más de lo que cabría esperar.
La idea
Un grafo es un conjunto de nodos unidos por aristas: habitaciones y puertas, páginas web y enlaces, tareas y las tareas de las que dependen. La búsqueda en profundidad visita todos los nodos que puede alcanzar desde un origen, pero en un orden concreto: siempre sigue desde el nodo que alcanzó más recientemente. Mantiene una pila de los nodos en los que está. Un nodo nuevo va a la cima, y un nodo solo sale cuando se ha explorado todo lo que lo rodea.
Paso a paso
Pon el origen en la pila y dale el número de visita 1. Mira el siguiente vecino del nodo de la cima. Si no se ha visto, dale el siguiente número de visita, recuerda el nodo desde el que se alcanzó y ponlo en la cima de la pila. Si ya se vio, sáltalo. Cuando el nodo de la cima no tiene más vecinos que revisar, está terminado: sácalo y sigue con el nodo de debajo. Para cuando la pila esté vacía o cuando alcances el destino.
Un ejemplo
Toma un grafo con las aristas A–B, A–C, B–D, C–D, C–E y D–F, empieza en A y revisa los vecinos en orden alfabético. Desde A la búsqueda va a B, desde B a D, desde D a C y desde C a E, así que la pila es A, B, D, C, E. Por el camino, C ve a A, que sigue en la pila: la arista C–A cierra el ciclo A, B, D, C. E no tiene nada nuevo, así que termina, luego C, y la búsqueda vuelve a D, que aún tiene a F. El orden de visita es A, B, D, C, E, F. Con E como destino, la DFS se detiene con el camino A → B → D → C → E, cuatro aristas, aunque A → C → E solo necesita dos.
Para qué sirve
La pila es siempre un camino desde el origen hasta el nodo actual, lo que hace a la DFS natural para laberintos y rompecabezas: es la idea del backtracking (vuelta atrás). En un grafo no dirigido, una arista hacia un nodo que sigue en la pila cierra un ciclo. En un grafo dirigido, listar los nodos en el orden inverso al que terminan da un orden topológico, de modo que cada tarea va después de las tareas de las que depende. La búsqueda en profundidad también encuentra componentes conexas, puentes y puntos de articulación, y su versión aleatoria es una forma clásica de generar laberintos.
Historia
En el siglo XIX, el matemático francés Charles Pierre Trémaux describió una forma de salir de cualquier laberinto marcando los pasillos, que es una búsqueda en profundidad hecha con tiza. En 1972 y 1973, Robert Tarjan y John Hopcroft mostraron que la DFS resuelve muchos problemas de grafos en tiempo lineal, desde las componentes fuertemente conexas hasta comprobar si un grafo se puede dibujar sin cruces. En parte por ese trabajo recibieron el Premio Turing de 1986.
Explóralo
Abre la app y pulsa Paso. El nodo cuyos vecinos se están revisando aparece resaltado, los nodos de la pila son azules y los terminados, verdes, cada uno con su número de visita. La pila se muestra bajo el grafo, desde el origen hasta el nodo de la cima. Fíjate en la línea de estado para ver las aristas que cierran un ciclo, y elige un destino para ver lo largo que puede ser el camino encontrado en comparación con la búsqueda en anchura.
Preguntas frecuentes
¿Cuál es la complejidad temporal de la DFS?
O(V + E) para V nodos (vértices) y E aristas (en inglés, edges): cada nodo entra y sale de la pila una vez, y cada arista se examina desde sus dos extremos. Necesita O(V) de memoria adicional para la pila y las marcas.
¿Por qué la DFS usa una pila?
Porque con la regla de que el último en entrar es el primero en salir, la búsqueda sigue desde el nodo más reciente y luego vuelve al anterior. La recursión hace lo mismo con la pila de llamadas del programa. Con una cola en su lugar, la búsqueda se extendería anillo a anillo: eso es la búsqueda en anchura.
¿Es un problema la DFS recursiva en grafos grandes?
Puede serlo: un camino largo implica una recursión profunda, y muchos lenguajes limitan la profundidad de las llamadas. Una pila explícita en un bucle evita ese límite y visita los nodos en el mismo orden.
¿Dónde se usa la DFS?
Para resolver laberintos y rompecabezas con backtracking, encontrar ciclos, ordenar tareas según sus dependencias (ordenamiento topológico), encontrar componentes conexas y fuertemente conexas, generar laberintos, y en compiladores y herramientas de compilación que recorren grafos de dependencias.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba la búsqueda en profundidad