Grafos: BFS y DFS explicados con ejemplos en Python

Los grafos son la base de algoritmos de rutas (GPS), redes sociales, motores de búsqueda y compiladores. BFS y DFS son los dos algoritmos fundamentales para recorrerlos — y aparecen en el 80% de las entrevistas técnicas.

Representación: lista de adyacencia

grafo = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

BFS — Búsqueda en Anchura

BFS explora nivel por nivel usando una cola. Garantiza el camino más corto en grafos no ponderados.

from collections import deque

def bfs(grafo, inicio):
    visitados = set([inicio])
    cola = deque([inicio])
    orden = []
    
    while cola:
        nodo = cola.popleft()
        orden.append(nodo)
        for vecino in grafo[nodo]:
            if vecino not in visitados:
                visitados.add(vecino)
                cola.append(vecino)
    
    return orden

print(bfs(grafo, "A"))  # [A, B, C, D, E, F]

DFS — Búsqueda en Profundidad

DFS va tan profundo como puede antes de retroceder. Usa recursión o una pila.

def dfs(grafo, nodo, visitados=None):
    if visitados is None:
        visitados = set()
    visitados.add(nodo)
    print(nodo, end=" ")
    for vecino in grafo[nodo]:
        if vecino not in visitados:
            dfs(grafo, vecino, visitados)

BFS vs DFS

Regla práctica: BFS para caminos más cortos, DFS para ciclos, topología y backtracking.