¿Qué es búsqueda en profundidad (DFS)?

Question

Accepted Answer

**DFS** explora un grafo yendo lo más profundo posible en cada rama antes de retroceder. Utiliza una **pila** (a menudo la pila de llamadas a través de recursión) y visita un camino completo antes de explorar alternativas.

## La idea

Desde un nodo, recurre en un vecino no visitado y sigue profundizando; cuando te atascas, retrocede e intenta otra rama.

## Ejemplo

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS vs DFS

| | BFS | DFS |
|---|-----|-----|
| Estructura | cola | pila / recursión |
| Encuentra | más corto (sin pesos) | cualquier camino |
| Memoria | O(V) frontera | O(profundidad) |
| Bueno para | caminos más cortos, niveles | ciclos, orden topológico, componentes |

## Complejidad

- **Tiempo:** O(V + E). **Espacio:** O(V) (profundidad de recursión + visitados).

## Trampas

Grafos profundos pueden desbordar la pila de recursión — usa una pila explícita. Registra `visited` para manejar ciclos.

## Por qué es importante

DFS es fundamental para detección de ciclos, ordenamiento topológico, componentes conexas y generación de laberintos/caminos.

Su elegancia recursiva hace que el código de árboles y grafos sea conciso.

Saber cuándo la búsqueda en profundidad supera a la búsqueda en amplitud es fundamental para dominar algoritmos de grafos.

	BFS	DFS
Estructura	cola	pila / recursión
Encuentra	más corto (sin pesos)	cualquier camino
Memoria	O(V) frontera	O(profundidad)
Bueno para	caminos más cortos, niveles	ciclos, orden topológico, componentes