Motivation
Lección 2 de 9 del curso Búsqueda en anchura - Algoritmos de grafos de Coddy.
BFS utiliza una cola (primero en entrar, primero en salir) para que los vértices se procesen en el orden exacto en que se descubren, lo que produce la exploración capa por capa.
¿Por qué aprender BFS?
- Caminos más cortos: en un grafo no ponderado, BFS encuentra el camino con menos aristas desde el inicio hasta cada uno de los demás vértices.
- Simple y lineal: se ejecuta en O(V + E) con una cola y un marcador de visitados.
- En todas partes: los saltos más cortos en redes, escaleras de palabras, resolución de laberintos y el recorrido de árboles por niveles son todos BFS.
Al igual que con DFS, encolamos los vecinos de un vértice en orden ascendente para que los resultados sean predecibles.
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.
