BFS explora un grafo nivel por nivel, visitando todos los vecinos de un nodo antes de avanzar más profundo. Utiliza una cola y encuentra el camino más corto (fewest edges) en grafos no ponderados.
Comience en una fuente, encolela, luego repita sacando un nodo de la cola, visitando sus vecinos no visitados y encolándolos. Un conjunto visited evita revisitas.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft() # FIFO: explore nearest first
order.append(node)
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
queue.append(nbr)
return order
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A') # -> ['A', 'B', 'C', 'D']
Use BFS para camino más corto en grafos no ponderados, recorrido por niveles y búsqueda de componentes conectadas. Usa más memoria que DFS (toda la frontera a la vez). Siempre siga la pista de visited o puede entrar en un bucle infinito en ciclos.
BFS es el algoritmo para caminos más cortos cuando cada arista cuenta por igual — enrutamiento, rastreo web, grados de separación en redes sociales.
Su estructura basada en colas, nivel a nivel, es un patrón de recorrido fundamental.
Conocer BFS vs DFS le permite elegir la herramienta correcta para problemas de alcanzabilidad, caminos y ordenamiento.