Búsqueda en Profundidad (DFS) explora un grafo yéndose lo más lejos posible por cada rama antes de retroceder — como un laberinto donde sigues una pared hasta chocar y luego regresas.
Implementado con una pila explícita o recursión (que usa la pila de llamadas), DFS es la herramienta para problemas donde el orden de descubrimiento importa: ciclos, componentes conexos, orden topológico y caminos específicos.
Cómo Funciona
- Inicializa: marca todos los nodos como no visitados.
- Elige un nodo fuente, visita sus vecinos no visitados en profundidad antes de considerar alternativas.
- Retrocede cuando no hay más vecinos sin visitar.
- Repite para cualquier componente no visitado (grafo no conexo).
Idea Clave
DFS no garantiza el camino más corto — prioriza la profundidad sobre la amplitud. Su superpoder es la clasificación de aristas durante el retroceso: con temporizadores discovery y finish, puedes distinguir árbol, retroceso, adelante y cruzada. Esa estructura resuelve ciclos, componentes fuertemente conexos y orden topológico en una sola pasada.
Ejemplo Trabajado
Fuente S en el visualizador:
| Fase | Nodo | Vecinos explorados | Acción |
|---|---|---|---|
| 1 | S | A, B | Visita A |
| 2 | A | C, D | Visita C |
| 3 | C | E | Visita E |
| 4 | E | — | Backtrack a C |
| 5 | C | D | Visita D |
| 6 | D | — | Backtrack a A → S |
| 7 | S | B | Visita B |
| 8 | B | F | Visita F |
| 9 | F | — | Backtrack a B → S |
Orden discovery: S, A, C, E, D, B, F. Observa el visualizador colorear aristas por tipo y mostrar la pila creciendo/decreciendo.
Casos Extremos y Trampas
- Grafos con ciclos — sin visitados, DFS gira infinitamente.
- Grafos muy profundos — la recursión puede desbordar la pila; usa una pila explícita.
- Grafos muy anchos —
O(V)de memoria en la pila/llamadas. - Múltiples componentes — itera sobre todos los nodos para cubrir componentes no alcanzados desde la fuente.
Comparación con BFS
| Aspecto | DFS | BFS |
|---|---|---|
| Estructura | Pila (LIFO / recursión) | Cola (FIFO) |
| Camino más corto | No garantizado | Sí (no ponderado) |
| Memoria | O(h) altura | O(V) ancho |
| Natural para | Ciclos, topológico, SCC | Caminos mínimos, niveles |
Aplicaciones
- Detección de ciclos — aristas de retroceso en directed graphs
- Orden topológico — salida en orden
finishdecreciente - Componentes fuertemente conexos — Kosaraju / Tarjan
- Resolución de laberintos — backtracking hasta hallar salida
- Generación de laberintos — DFS recursivo back-tracker
Trayectoria de Práctica
- Ejecuta DFS a mano desde S en el grafo del visualizador, dibujando el árbol DFS y clasificando cada arista.
- Identifica las aristas de retroceso y explica por qué equivalen a ciclos en grafos dirigidos.
- Genera un orden topológico desde el orden
finishdecreciente de DFS en un DAG. - Extiende DFS para contar componentes conexos en un grafo no dirigido.