Complejidad Temporal
O(filas × columnas)
Este algoritmo usa Búsqueda en Anchura para encontrar el camino más corto a través de un laberinto desde el inicio hasta el final, navegando alrededor de muros.
Cómo funciona:
1. Iniciar BFS desde la celda de inicio
2. Explorar los 4 vecinos (arriba, abajo, izquierda, derecha)
3. Omitir muros y celdas ya visitadas
4. Marcar cada celda explorada y registrar su padre
5. Cuando se alcanza el final, rastrear hacia atrás a través de los padres para encontrar el camino
Complejidad Temporal: O(filas × columnas)
Complejidad Espacial: O(filas × columnas)
Propiedades:
- Garantiza el camino más corto
- Explora nivel por nivel (celdas más cercanas primero)
- Funciona en cuadrículas sin pesos
La búsqueda de caminos basada en BFS es fundamental en desarrollo de videojuegos, robótica y sistemas de navegación. Para cuadrículas ponderadas, se usaría Dijkstra o A* en su lugar.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Búsqueda de Camino en Laberinto (BFS)?
- Este algoritmo usa Búsqueda en Anchura para encontrar el camino más corto a través de un laberinto desde el inicio hasta el final, navegando alrededor de muros.
- ¿Cuál es la complejidad de Búsqueda de Camino en Laberinto (BFS)?
- Tiempo (promedio): O(filas × columnas) · Espacio: O(filas × columnas)
- ¿Para quién es este visualizador de Búsqueda de Camino en Laberinto (BFS)?
- La visualización de Búsqueda de Camino en Laberinto (BFS) está pensada para nivel intermedio, dentro de la categoría Backtracking. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Búsqueda de Camino en Laberinto (BFS)?
- En la misma categoría (Backtracking) puedes explorar: N-Queens Problem, Sudoku Solver. Todos tienen visualización interactiva.