Complejidad Temporal
O(V + E)
BFS es un algoritmo de recorrido de grafos que explora todos los vértices en la profundidad actual antes de pasar a los vértices del siguiente nivel de profundidad. Utiliza una estructura de datos de cola.
Cómo funciona:
1. Comienza desde un nodo origen, márcalo como visitado, agrégalo a la cola
2. Desencola un nodo, procésalo
3. Encola todos los vecinos no visitados
4. Repite hasta que la cola esté vacía
Complejidad Temporal: O(V + E)
V = número de vértices, E = número de aristas
Complejidad Espacial: O(V) — para la cola y el conjunto de visitados
Aplicaciones:
- Camino más corto en grafos no ponderados
- Recorrido por niveles de árboles
- Encontrar componentes conexos
- Rastreo web (web crawling)
- Análisis de redes sociales (grados de separación)
BFS garantiza encontrar el camino más corto (menos aristas) entre dos nodos en un grafo no ponderado.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Búsqueda en Anchura (BFS)?
- BFS es un algoritmo de recorrido de grafos que explora todos los vértices en la profundidad actual antes de pasar a los vértices del siguiente nivel de profundidad. Utiliza una estructura de datos de cola.
- ¿Cuál es la complejidad de Búsqueda en Anchura (BFS)?
- Tiempo (promedio): O(V + E) · Espacio: O(V)
- ¿Para quién es este visualizador de Búsqueda en Anchura (BFS)?
- La visualización de Búsqueda en Anchura (BFS) 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 Anchura (BFS)?
- En la misma categoría (Grafos) puedes explorar: Depth-First Search, Dijkstra's Algorithm, Prim's Algorithm. Todos tienen visualización interactiva.