Overview
La búsqueda en profundidad (DFS) explora tan lejos como sea posible por cada rama antes de retroceder.
Analogy
Como explorar un laberinto: vas hacia adelante sin parar hasta un callejón sin salida, luego retrocedes y pruebas otro camino.
Step-by-step
- Comienza en el nodo de inicio (o primer nodo)
- Marca el nodo actual como visitado
- Visita recursivamente cada vecino no visitado
- Retrocede cuando no hay vecinos no visitados
Visual
1
/ \
2 3
/ \
4 5
DFS: 1→2→4→5→3
Common mistakes
- No rastrear los nodos visitados → ciclos infinitos
- Confundir el orden de visita pre/in/post-orden
Practice questions
- Detecta ciclos en un grafo dirigido con DFS
- Encuentra todos los caminos entre dos nodos
Time
O(V+E) — cada vértice y arista se visita una vez
Space
O(V) — para la pila de recursión o pila explícita