1. Conceptos básicos

• Definición: DFS recorre un grafo siguiendo un camino tan profundo como sea posible antes de retroceder.
• Tipos de grafos: dirigido, no dirigido, ponderado, cíclico o acíclico.
• Estructura de apoyo: pila (implícita con recursión o explícita con list).

Complejidad temporal y espacial

DFS vs BFS (Comparativa)

2. Implementaciones en Python

2.1. Versión recursiva (más legible)

def dfs_recursive(graph, start, visited=None):
    """Recorre el grafo usando recursión.
    Args:
        graph (dict): Representación de lista de adyacencia.
        start (hashable): Nodo inicial.
        visited (set, optional): Conjunto de nodos visitados.
    """
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Acción: aquí puedes procesar el nodo
    for neighbour in graph.get(start, []):
        if neighbour not in visited:
            dfs_recursive(graph, neighbour, visited)
    return visited
# Ejemplo de uso
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
dfs_recursive(graph, 'A')

⚠️ En Python el límite de recursión por defecto es 1000. Para grafos profundos, considera sys.setrecursionlimit() o la versión iterativa.

2.2. Versión iterativa con pila explícita

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)  # Acción sobre el nodo
            # Añadimos los vecinos en orden inverso para mantener el mismo recorrido que la recursiva
            stack.extend(reversed(graph.get(node, [])))
    return visited
# Uso
dfs_iterative(graph, 'A')

2.3. DFS con generador (lazy evaluation)

def dfs_generator(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    yield start
    for neighbour in graph.get(start, []):
        if neighbour not in visited:
            yield from dfs_generator(graph, neighbour, visited)
# Consumir el generador
for node in dfs_generator(graph, 'A'):
    print(node)

3. Casos de uso reales

• Detección de ciclos: Si durante el recorrido encuentras un nodo ya en la pila de llamadas, el grafo contiene un ciclo.
• Orden topológico: En DAGs, ejecutar DFS y apilar los nodos al terminar permite obtener un orden lineal.
• Componentes fuertemente conectados (Kosaraju): Se basa en dos pasadas de DFS (original y transpuesta).
• Resolución de puzzles (laberintos, Sudoku): La exploración profunda es ideal para buscar soluciones en espacios de estado.

4. Buenas prácticas y trucos de rendimiento

• Evita la mutación de estructuras compartidas: Pasa una copia de visited cuando trabajes con funciones recursivas paralelas.
• Control de profundidad: Usa un parámetro opcional max_depth para limitar la recursión y prevenir ataques de denegación de servicio en grafos maliciosos.
• Uso de deque para la pila: collections.deque tiene pop() y append() O(1) y es ligeramente más rápido que una lista.
• Optimiza la representación del grafo: Para grafos muy grandes, considera networkx con Graph() o matrices de adyacencia dispersas (scipy.sparse).
• Profiling: Usa cProfile o timeit para identificar cuellos de botella cuando el número de vértices supera los millones.

5. Depuración y troubleshooting

Algunas situaciones típicas y cómo abordarlas:

• Recursión infinita: Verifica que cada llamada recursiva marque el nodo como visitado antes de llamar a los vecinos.
• StackOverflow en Python: Incrementa el límite con sys.setrecursionlimit(10000) o cambia a la versión iterativa.
• Nodos perdidos: Asegúrate de que la lista de adyacencia incluya todas las claves, incluso aquellas sin vecinos (valor []).
• Orden inesperado: El orden de los vecinos afecta el recorrido. Usa sorted() o reversed() para obtener un orden determinístico.

6. Compatibilidad, rendimiento y escalabilidad

DFS se adapta bien a diferentes entornos:

• Entornos de scripting (Python, Ruby, JavaScript): La versión recursiva es suficiente para grafos moderados (< 10⁴ nodos).
• Big Data (Spark, Dask): Implementa DFS como algoritmo de map‑reduce utilizando GraphFrames o GraphX para evitar la recursión.
• Contenedores (Docker, Podman): Empaqueta tu script con python:3.12-slim y expón un endpoint HTTP que reciba la lista de aristas y devuelva el recorrido DFS.
• Entornos con recursos limitados (IoT, Edge): La versión iterativa con deque consume menos pila y es más predecible en memoria.