Domina la Búsqueda en Profundidad (DFS) en Grafos

La Búsqueda en Profundidad, conocida por sus siglas en inglés como DFS (Depth-First Search), es uno de los algoritmos de recorrido de grafos más fundamentales en ciencias de la computación. Su lógica, que imita la forma en que exploraríamos un laberinto, consiste en avanzar por un camino hasta el final antes de retroceder para probar otras rutas. Esta técnica es increíblemente poderosa y se utiliza en una variedad de aplicaciones, desde encontrar componentes conectados en una red hasta resolver acertijos y juegos. En esta guía completa, desglosaremos cómo funciona DFS, cómo implementarlo de forma iterativa en un grafo dirigido y te proporcionaremos todo lo que necesitas para dominarlo.

¿Qué es exactamente la Búsqueda en Profundidad (DFS)?

Imagina que estás en un laberinto. Una estrategia para encontrar la salida es elegir un camino y seguirlo tan profundo como puedas. Si llegas a un callejón sin salida, retrocedes (haces backtracking) hasta la última bifurcación y tomas un camino que no habías explorado antes. Repites este proceso hasta que encuentres la salida o hayas explorado todos los caminos posibles. Eso, en esencia, es la Búsqueda en Profundidad.

A nivel técnico, DFS es un algoritmo para recorrer o buscar en estructuras de datos de tipo árbol o grafo. El algoritmo comienza en un nodo raíz (o un nodo arbitrario en el caso de un grafo) y explora tan lejos como sea posible a lo largo de cada rama antes de retroceder. Para lograr esto, utiliza una estructura de datos clave: la pila (stack). Debido a su naturaleza LIFO (Last-In, First-Out), la pila es perfecta para recordar los nodos que debemos visitar cuando retrocedemos desde una ruta profunda.

¿Cómo funciona el algoritmo DFS iterativo?

Aunque DFS a menudo se enseña con una implementación recursiva por su elegancia, la versión iterativa nos da más control sobre la ejecución y evita posibles desbordamientos de la pila de llamadas del sistema (stack overflow) en grafos muy profundos. El enfoque iterativo gestiona explícitamente una pila para seguir el rastro de los nodos a visitar.

Aquí está el proceso paso a paso para un recorrido DFS iterativo en un grafo dirigido, comenzando desde un nodo fuente (generalmente el nodo 0):

• Paso 1: Inicialización. Crea una pila vacía para los nodos que visitaremos y un conjunto o array booleano para marcar los nodos ya visitados. Esto es crucial para evitar ciclos infinitos.
• Paso 2: Comenzar el recorrido. Empuja (push) el nodo de inicio a la pila.
• Paso 3: Bucle principal. Mientras la pila no esté vacía, realiza las siguientes acciones:
• a. Extraer un nodo: Saca (pop) un nodo de la cima de la pila. Llamémoslo `nodo_actual`.
• b. Verificar si ha sido visitado: Si `nodo_actual` ya ha sido visitado, sáltalo y continúa con la siguiente iteración del bucle. Esto evita procesar el mismo nodo varias veces.
• c. Marcar y procesar: Si no ha sido visitado, márcalo como visitado. Ahora puedes procesarlo (por ejemplo, añadirlo a tu lista de resultados).
• d. Apilar vecinos: Obtén todos los nodos adyacentes (vecinos) de `nodo_actual`. Recórrelos y, si un vecino no ha sido visitado, empújalo a la pila.

Un detalle importante: el orden en que empujas a los vecinos en la pila afecta el orden del recorrido. Si quieres visitar los vecinos en el orden en que aparecen en la lista de adyacencia, debes empujarlos a la pila en orden inverso. Esto se debe a que la pila es LIFO, por lo que el último elemento que añadas será el primero en ser procesado.

Ejemplo Práctico de Recorrido

Consideremos el siguiente grafo representado por una lista de adyacencia: adj = [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]] y empecemos desde el nodo 0.

1. Inicio: `pila = [0]`, `visitados = {}`, `resultado = []`.
2. Iteración 1: Sacamos el 0. Lo marcamos como visitado y lo añadimos al resultado. `visitados = {0}`, `resultado = [0]`. Los vecinos de 0 son 1 y 2. Los empujamos en orden inverso: `pila = [2, 1]`.
3. Iteración 2: Sacamos el 1. Lo marcamos como visitado y lo añadimos al resultado. `visitados = {0, 1}`, `resultado = [0, 1]`. Los vecinos de 1 son 0 y 2. El 0 ya está visitado. Empujamos el 2: `pila = [2, 2]`.
4. Iteración 3: Sacamos el 2 (el que acabamos de añadir). Lo marcamos como visitado y lo añadimos al resultado. `visitados = {0, 1, 2}`, `resultado = [0, 1, 2]`. Los vecinos de 2 son 0, 1, 3, 4. 0 y 1 ya están visitados. Empujamos 4 y 3 en orden inverso: `pila = [2, 4, 3]`.
5. Iteración 4: Sacamos el 3. Lo marcamos y lo añadimos. `visitados = {0, 1, 2, 3}`, `resultado = [0, 1, 2, 3]`. El vecino de 3 es 2, que ya está visitado. La pila es `pila = [2, 4]`.
6. Iteración 5: Sacamos el 4. Lo marcamos y lo añadimos. `visitados = {0, 1, 2, 3, 4}`, `resultado = [0, 1, 2, 3, 4]`. El vecino de 4 es 2, ya visitado. La pila es `pila = [2]`.
7. Iteración 6: Sacamos el 2. Ya está en `visitados`, así que lo ignoramos. La pila está vacía.

El bucle termina. El resultado final del recorrido es: [0, 1, 2, 3, 4].

Implementación de DFS Iterativo para Grafos Conexos

A continuación, se muestra el código para implementar el algoritmo DFS iterativo, asumiendo que el grafo es conexo y comenzamos desde el nodo 0.

Python

def dfs(adj): n = len(adj) visitados = [False] * n resultado = [] pila = [] # Empezamos el DFS desde el nodo 0 pila.append(0) while pila: nodo = pila.pop() # Si el nodo ya fue visitado, lo ignoramos if visitados[nodo]: continue # Marcamos el nodo como visitado y lo procesamos visitados[nodo] = True resultado.append(nodo) # Añadimos los vecinos no visitados a la pila en orden inverso # para mantener el orden de la lista de adyacencia. for vecino in reversed(adj[nodo]): if not visitados[vecino]: pila.append(vecino) return resultado

JavaScript

function dfs(adj) { const n = adj.length; const visitados = new Array(n).fill(false); const resultado = []; const pila = []; // Empezamos el DFS desde el nodo 0 pila.push(0); while (pila.length > 0) { const nodo = pila.pop(); // Si el nodo ya fue visitado, lo ignoramos if (visitados[nodo]) { continue; } // Marcamos el nodo como visitado y lo procesamos visitados[nodo] = true; resultado.push(nodo); // Añadimos los vecinos no visitados a la pila en orden inverso for (let i = adj[nodo].length - 1; i >= 0; i--) { const vecino = adj[nodo][i]; if (!visitados[vecino]) { pila.push(vecino); } } } return resultado;}

Java

import java.util.*;class Solucion { static ArrayList dfs(ArrayList> adj) { int n = adj.size(); boolean[] visitados = new boolean[n]; ArrayList resultado = new ArrayList<>(); Stack pila = new Stack<>(); // Empezamos el DFS desde el nodo 0 pila.push(0); while (!pila.isEmpty()) { int nodo = pila.pop(); // Si el nodo ya fue visitado, lo ignoramos if (visitados[nodo]) { continue; } // Marcamos el nodo como visitado y lo procesamos visitados[nodo] = true; resultado.add(nodo); // Añadimos los vecinos no visitados a la pila en orden inverso List vecinos = adj.get(nodo); for (int i = vecinos.size() - 1; i >= 0; i--) { int vecino = vecinos.get(i); if (!visitados[vecino]) { pila.push(vecino); } } } return resultado; }}

Manejando Grafos No Conexos

El código anterior funciona perfectamente si todos los nodos son alcanzables desde el nodo 0. Pero, ¿qué pasa si el grafo tiene múltiples componentes no conectados entre sí? En ese caso, un solo llamado a DFS no visitará todos los nodos. La solución es simple: iterar a través de todos los nodos del 0 al N-1 y, si encontramos un nodo que aún no ha sido visitado, iniciamos un nuevo recorrido DFS desde él. Esto garantiza que cada componente del grafo sea explorado.

La lógica se modifica ligeramente, encapsulando el recorrido en una función auxiliar y llamándola dentro de un bucle.

Python para Grafos No Conexos

def dfs_util(s, adj, visitados, resultado): pila = [] pila.append(s) while pila: nodo = pila.pop() if visitados[nodo]: continue visitados[nodo] = True resultado.append(nodo) for vecino in reversed(adj[nodo]): if not visitados[vecino]: pila.append(vecino)def dfs_completo(adj): n = len(adj) visitados = [False] * n resultado = [] for i in range(n): if not visitados[i]: dfs_util(i, adj, visitados, resultado) return resultado

DFS Recursivo vs. Iterativo: Una Comparación

Ambos enfoques tienen el mismo objetivo y complejidad, pero presentan diferencias importantes en su implementación y comportamiento.

Complejidad del Algoritmo DFS

Entender la eficiencia de un algoritmo es clave. Para DFS, la complejidad es bastante directa:

• Complejidad Temporal: O(V + E). Donde 'V' es el número de vértices (nodos) y 'E' es el número de aristas (conexiones). Esto se debe a que el algoritmo visita cada vértice una sola vez y recorre cada arista una vez (o dos veces en un grafo no dirigido).
• Complejidad Espacial: O(V). En el peor de los casos (un grafo que es una línea recta), la pila (ya sea la de llamadas o la explícita) podría contener todos los vértices. Además, el array `visitados` requiere un espacio proporcional al número de vértices.

Preguntas Frecuentes (FAQ)

¿Cuándo debería usar DFS en lugar de BFS (Búsqueda en Anchura)?

DFS es ideal para tareas como: encontrar si existe un camino entre dos nodos, detectar ciclos en un grafo, ordenamiento topológico y resolver problemas de tipo laberinto donde la solución puede estar muy profunda en el grafo. BFS, por otro lado, es mejor para encontrar el camino más corto en un grafo sin pesos.

¿Qué sucede si el grafo tiene ciclos?

El array o conjunto `visitados` es absolutamente esencial para manejar ciclos. Sin él, si el algoritmo entra en un ciclo, se quedaría atrapado en un bucle infinito, visitando los mismos nodos una y otra vez. Al marcar los nodos como visitados, nos aseguramos de que cada nodo se procese solo una vez.

¿El orden de recorrido de DFS es único?

No, el recorrido de DFS no es único. Depende de dos factores principales: el nodo de inicio elegido y el orden en que se exploran los vecinos de cada nodo. Diferentes implementaciones pueden producir secuencias de recorrido válidas pero distintas para el mismo grafo.

Conclusión

La Búsqueda en Profundidad es una herramienta poderosa y versátil en el arsenal de cualquier programador. Su enfoque de "profundizar primero" lo hace adecuado para una amplia gama de problemas. Si bien la versión recursiva es elegante, la implementación iterativa ofrece robustez y control, especialmente para grafos grandes. Al comprender su funcionamiento interno, cómo manejar grafos no conexos y sus complejidades, estarás bien equipado para aplicar DFS de manera efectiva en tus propios proyectos y desafíos de codificación.