10 - Búsqueda en anchura (BFS)

BFS (breadth-first search) recorre el grafo en rondas: arranca en un vértice, usa una cola y visita primero sus vecinos, luego los vecinos de ellos, y así hasta cubrir todo. En grafos sin pesos garantiza llegar en la menor cantidad de aristas y registra quién descubrió a cada nodo para armar el camino.

10.1 Concepto y funcionamiento

Partimos de un origen, lo marcamos como visitado y lo encolamos. Luego, repetimos: desencolar un vértice, procesar sus vecinos no visitados, marcarlos y encolarlos. Se avanza capa por capa.

10.2 Aplicaciones principales

  • Encontrar caminos más cortos en grafos sin pesos.
  • Detectar componentes y comprobar si el grafo es bipartito (sus vértices se pueden pintar con dos colores sin que se toquen colores iguales).
  • Armar árboles de recorrido por niveles.
  • Simular propagación o relleno (flood fill, difusión).

10.3 Implementación de la cola en Python

Usamos deque para mantener O(1) por operación.

from collections import deque

cola = deque()
cola.append(0)
v = cola.popleft()

10.4 Algoritmo paso a paso

  1. Inicializar visitado en False.
  2. Marcar origen y encolarlo.
  3. Mientras la cola no esté vacía: desencolar u, visitar vecinos v no marcados, marcarlos y encolarlos.
  4. Registrar el padre de cada v si se necesita reconstruir caminos.

10.5 BFS usando matriz y lista de adyacencia

from collections import deque

def bfs_matriz(matriz, origen):
  n = len(matriz)
  visitado = [False] * n
  cola = deque([origen])
  visitado[origen] = True
  while cola:
    u = cola.popleft()
    print(u, end=" ")
    for v in range(n):
      if matriz[u][v] != 0 and not visitado[v]:
        visitado[v] = True
        cola.append(v)
from collections import deque

def bfs_lista(g, origen):
  visitado = {v: False for v in g}
  cola = deque([origen])
  visitado[origen] = True
  while cola:
    u = cola.popleft()
    print(u, end=" ")
    for v, _ in g[u]:
      if not visitado[v]:
        visitado[v] = True
        cola.append(v)

10.6 Generación del árbol BFS

Para reconstruir caminos mínimos, guarda un diccionario padre y asigna padre[v] = u cuando se encola v desde u. Al finalizar, padre define el árbol de BFS.

from collections import deque

def bfs_con_padres(g, origen):
  visitado = {v: False for v in g}
  padre = {v: None for v in g}
  cola = deque([origen])
  visitado[origen] = True

  while cola:
    u = cola.popleft()
    for v, _ in g[u]:
      if not visitado[v]:
        visitado[v] = True
        padre[v] = u
        cola.append(v)
  return padre

Con padre poblado, reconstruye un camino desde cualquier destino siguiendo padres hasta llegar al origen. El siguiente fragmento arma el camino en orden origen a destino:

def reconstruir_camino(padre, origen, destino):
  camino = []
  actual = destino
  while actual is not None:
    camino.append(actual)
    if actual == origen:
      break
    actual = padre[actual]
  if not camino or camino[-1] != origen:
    print(f"No hay camino de {origen} a {destino}")
    return
  camino.reverse()
  print(f"Camino {origen} -> {destino}: " + " -> ".join(map(str, camino)))

10.7 Aplicación completa para probar en VSCode

Programa autocontenido que construye un grafo, ejecuta BFS y muestra el árbol de padres.

from collections import deque

def bfs_con_padres(g, origen):
  visitado = {v: False for v in g}
  padre = {v: None for v in g}
  cola = deque([origen])
  visitado[origen] = True

  while cola:
    u = cola.popleft()
    for v, _ in g[u]:
      if not visitado[v]:
        visitado[v] = True
        padre[v] = u
        cola.append(v)
  return padre

def reconstruir_camino(padre, origen, destino):
  camino = []
  actual = destino
  while actual is not None:
    camino.append(actual)
    if actual == origen:
      break
    actual = padre[actual]
  if not camino or camino[-1] != origen:
    print(f"No hay camino de {origen} a {destino}")
    return
  camino.reverse()
  print(f"Camino {origen} -> {destino}: " + " -> ".join(map(str, camino)))

def main():
  g = {
    0: [(1, 1), (2, 1)],
    1: [(0, 1), (3, 1)],
    2: [(0, 1), (3, 1)],
    3: [(1, 1), (2, 1), (4, 1)],
    4: [(3, 1)]
  }

  padre = bfs_con_padres(g, 0)
  print("Padres en el arbol BFS desde 0:")
  for v in sorted(padre.keys()):
    print(f"{v} -> {padre[v] if padre[v] is not None else -1}")

  reconstruir_camino(padre, 0, 4)

if __name__ == "__main__":
  main()
Editor online

Ejecuta el programa para ver cómo se forma el árbol de BFS y modifica las aristas para probar distintas topologías. Con la configuración incluida, la salida esperada es:

Padres en el arbol BFS desde 0:
0 -> -1
1 -> 0
2 -> 0
3 -> 1
4 -> 3
Camino 0 -> 4: 0 -> 1 -> 3 -> 4

Abrir visualizador BFS interactivo

Retornar