Time and Space Complexity
Lección 7 de 9 del curso Búsqueda en anchura - Algoritmos de grafos de Coddy.
Complejidad Temporal:
- O(V + E)
- Cada vértice se encola y desencola una vez, y cada arista se examina un número constante de veces.
Complejidad Espacial:
- O(V + E)
- La lista de adyacencia almacena cada arista, y la cola y el arreglo de visitados contienen hasta V vértices.
Resumen:
- BFS explora en capas utilizando una cola, visitando los vértices más cercanos antes que los más lejanos.
- Ese orden por capas lo convierte en el algoritmo de referencia para encontrar los caminos más cortos en grafos no ponderados.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Búsqueda en anchura - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity