Introduction

¡Bienvenidos de nuevo a la serie de Algoritmos de Grafos! Después de la Búsqueda en Profundidad (DFS), pasamos a la Búsqueda en Anchura (BFS), el otro recorrido fundamental de grafos.

Mientras que DFS se sumerge profundamente, BFS explora en capas: primero el vértice de inicio, luego todos sus vecinos, después todo lo que esté a dos pasos de distancia, y así sucesivamente. Este orden capa por capa es exactamente lo que hace que BFS encuentre caminos más cortos en grafos no ponderados.

Como en el resto de la serie, un grafo se da como n (conteo de vértices, de 0 a n - 1) y edges, un array plano de pares no dirigidos [u0, v0, u1, v1, ...].

¡Empecemos!