Saltar al contenido principal

Breadth-First Search (BFS)

Breadth-First Search (BFS) es un algoritmo para recorrer o buscar en grafos (o árboles) que explora los nodos por capas: primero todos los nodos a distancia 1 del origen, luego todos a distancia 2, etc. Usa una cola (queue) para gestionar el orden de visita.

Uso clave: encuentra el camino mínimo (en número de aristas) en grafos no ponderados.

Algoritmo​

  1. Empezamos en un nodo inicial start.
  2. Marcamos start como visitado y lo metemos en la cola.
  3. Mientras la cola no esté vacía: sacamos el nodo del frente, procesamos sus vecinos no visitados (los marcamos como visitados y los añadimos al final de la cola).
  4. Repetimos hasta recorrer todo lo alcanzable.

Paso a paso con un ejemplo​

Grafo (no dirigido), representado visualmente:

Lista de adyacencia conceptual:

A: [B, C]
B: [A, D, E]
C: [A, F]
D: [B]
E: [B]
F: [C]

Empezamos en A.

Estado inicial:

  • Cola: [A]
  • Visitados: {A}
  • Orden visitado: []

Iteración 1:

  • Sacamos A → procesamos.
  • Encolamos sus vecinos no visitados B, C.
  • Cola: [B, C]
  • Visitados: {A, B, C}
  • Orden: [A]

Iteración 2:

  • Sacamos B.
  • Vecinos: A (ya visitado), D, E → encolamos D, E.
  • Cola: [C, D, E]
  • Visitados: {A, B, C, D, E}
  • Orden: [A, B]

Iteración 3:

  • Sacamos C.
  • Vecinos: A (visitado), F → encolamos F.
  • Cola: [D, E, F]
  • Visitados: {A, B, C, D, E, F}
  • Orden: [A, B, C]

Iteración 4:

  • Sacamos D → no nuevos vecinos.
  • Cola: [E, F]
  • Orden: [A, B, C, D]

Iteración 5:

  • Sacamos E → no nuevos vecinos.
  • Cola: [F]
  • Orden: [A, B, C, D, E]

Iteración 6:

  • Sacamos F → no nuevos vecinos.
  • Cola: []
  • Orden: [A, B, C, D, E, F]

Resultado: BFS visita en orden por capas: A, B, C, D, E, F.

Si queremos el camino más corto de A a F, BFS también nos lo da: A → C → F (2 aristas).

Complejidad y usos​

  • Tiempo: O(V+E)O(V + E) (V = nodos, E = aristas).
  • Espacio: O(V)O(V) (cola + visited + posibles padres).
  • Usos: rutas más cortas en grafos no ponderados, crawlers (por ejemplo webs por niveles), análisis por niveles en árboles (recorrido por niveles), detección de componentes conexas.

Notas y variantes​

  • En grafos dirigidos funciona igual (usar la lista de salida).
  • No sirve para encontrar caminos mínimos en grafos ponderados (usar Dijkstra para pesos ≥ 0).
  • Comparado con DFS, BFS explora por niveles (mejor para encontrar caminos cortos), DFS se adentra en profundidad (útil para componentes, topológico, backtracking).