Complejidad Temporal
O(V + E)
DFS es un algoritmo de recorrido de grafos que explora lo más profundo posible a lo largo de cada rama antes de retroceder. Utiliza una pila (o recursión).
Cómo funciona:
1. Comienza desde un nodo origen, márcalo como visitado
2. Visita recursivamente cada vecino no visitado
3. Retrocede cuando no quedan vecinos sin visitar
4. Continúa hasta que todos los nodos alcanzables sean visitados
Complejidad Temporal: O(V + E)
V = número de vértices, E = número de aristas
Complejidad Espacial: O(V) — para la pila de recursión y el conjunto de visitados
Aplicaciones:
- Detección de ciclos en grafos
- Ordenamiento topológico
- Encontrar componentes conexos
- Resolver laberintos y puzzles
- Búsqueda de caminos
DFS explora caminos profundos primero, lo que lo hace útil para ordenamiento topológico y detección de ciclos, pero no garantiza caminos más cortos.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Búsqueda en Profundidad (DFS)?
- DFS es un algoritmo de recorrido de grafos que explora lo más profundo posible a lo largo de cada rama antes de retroceder. Utiliza una pila (o recursión).
- ¿Cuál es la complejidad de Búsqueda en Profundidad (DFS)?
- Tiempo (promedio): O(V + E) · Espacio: O(V)
- ¿Para quién es este visualizador de Búsqueda en Profundidad (DFS)?
- La visualización de Búsqueda en Profundidad (DFS) está pensada para nivel intermedio, dentro de la categoría Grafos. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Búsqueda en Profundidad (DFS)?
- En la misma categoría (Grafos) puedes explorar: Breadth-First Search, Dijkstra's Algorithm, Prim's Algorithm. Todos tienen visualización interactiva.