El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Búsqueda en Grafos: BFS y DFS

Siguiente ►
►

Ya tenemos la red urbana de Rutalia en memoria como lista de adyacencia. La pregunta natural es: ¿cómo se recorre? Casi todo lo que haremos con grafos en este módulo —caminos mínimos, flujo, emparejamientos— se apoya en dos formas fundamentales de exploración: la búsqueda en anchura (BFS), que avanza por capas como una onda expansiva, y la búsqueda en profundidad (DFS), que se adentra por un camino hasta agotarlo antes de retroceder. Con solo estas dos herramientas responderemos preguntas operativas reales de Rutalia: a cuántos tramos está el punto de entrega más lejano, qué zonas quedan incomunicadas si unas obras cortan una calle, y en qué orden deben ejecutarse las tareas del almacén.

Contenido

  1. BFS: exploración por niveles con una cola
  2. Distancias en aristas y reconstrucción del camino con padre
  3. DFS: recursivo e iterativo
  4. Tabla comparativa BFS vs DFS
  5. Detección de ciclos
  6. Componentes conexas: BFS frente al union-find de 01-04
  7. Ordenación topológica en DAGs: el algoritmo de Kahn
  8. Aplicaciones en Rutalia: cortes de calle y excentricidad

BFS: exploración por niveles con una cola

BFS parte de un nodo origen y visita primero todos sus vecinos (nivel 1), luego los vecinos de estos (nivel 2), y así sucesivamente. La estructura que impone este orden es una cola FIFO: los nodos se procesan en el mismo orden en que se descubren.

from collections import deque

# Grafo canónico de Rutalia (03-01): {nodo: {vecino: minutos}}
RED = {
    "ALM": {"RIO": 3, "MER": 4, "EST": 7, "CEN": 12},
    "MER": {"ALM": 4, "CEN": 5, "UNI": 6},
    "EST": {"ALM": 7, "UNI": 3, "IND": 9},
    "UNI": {"MER": 6, "EST": 3, "CEN": 8, "HOS": 5},
    "RIO": {"ALM": 3, "CEN": 6, "PAR": 8},
    "CEN": {"ALM": 12, "MER": 5, "UNI": 8, "RIO": 6, "HOS": 4},
    "IND": {"EST": 9, "HOS": 6},
    "HOS": {"UNI": 5, "CEN": 4, "IND": 6, "PAR": 7},
    "PAR": {"RIO": 8, "HOS": 7},
}

def bfs(grafo, origen):
    """Devuelve (dist, padre): distancia en ARISTAS desde origen y árbol de padres."""
    dist = {origen: 0}
    padre = {origen: None}
    cola = deque([origen])
    while cola:
        u = cola.popleft()              # FIFO: sale el más antiguo
        for v in grafo[u]:
            if v not in dist:           # aún no descubierto
                dist[v] = dist[u] + 1   # está una capa más lejos que u
                padre[v] = u
                cola.append(v)
        # los pesos (minutos) se IGNORAN a propósito: BFS cuenta tramos
    return dist, padre

dist, padre = bfs(RED, "ALM")
print(dist)
# {'ALM': 0, 'RIO': 1, 'MER': 1, 'EST': 1, 'CEN': 1,
#  'PAR': 2, 'UNI': 2, 'IND': 2, 'HOS': 2}

Claves del código:

  • Marcamos un nodo como descubierto al encolarlo, no al desencolarlo. Si se marcara tarde, un mismo nodo podría entrar varias veces en la cola.
  • dist[v] = dist[u] + 1 funciona porque la cola procesa los niveles en orden: cuando sacamos a u, todos los nodos a distancia menor ya han salido. Esta es la garantía central de BFS: en grafos sin pesos (o con todas las aristas iguales), dist[v] es la longitud del camino más corto en número de aristas.
  • Complejidad: cada nodo entra y sale de la cola una vez, y cada arista se examina dos veces (una por extremo): O(n + m) con lista de adyacencia. Con matriz sería O(n²), otra razón para la elección de 03-01.

Lectura operativa inmediata: desde el Almacén, toda la ciudad está a como mucho 2 tramos. La excentricidad de ALM es 2. Pero ojo: "2 tramos" no significa "poco tiempo" — lo veremos al final.

Distancias en aristas y reconstrucción del camino con padre

padre guarda, para cada nodo, desde qué nodo fue descubierto. Ese diccionario define un árbol BFS enraizado en el origen, y permite reconstruir el camino más corto caminando hacia atrás — la misma técnica de reconstrucción que usamos en la PD de 01-03:

def reconstruir(padre, destino):
    camino = []
    while destino is not None:
        camino.append(destino)
        destino = padre[destino]   # retrocedemos un paso hacia el origen
    return camino[::-1]            # estaba del revés

print(reconstruir(padre, "HOS"))   # ['ALM', 'CEN', 'HOS']

BFS propone ir al Hospital por la avenida directa: ALM→CEN→HOS, 2 tramos. En minutos son 12 + 4 = 16. Sin embargo ALM→MER→CEN→HOS son 3 tramos pero 4 + 5 + 4 = 13 minutos. BFS optimiza tramos, no minutos: cuando los pesos importan, hace falta otra cosa (03-03). Guarda este ejemplo: es la motivación exacta de Dijkstra.

DFS: recursivo e iterativo

DFS explora "hacia dentro": desde un nodo elige un vecino, desde este otro, y solo cuando no puede avanzar más retrocede (backtracking — literalmente el mismo esquema explorar/deshacer de 02-03, aplicado a grafos).

Versión recursiva, la más natural:

def dfs_recursivo(grafo, u, visitados=None, orden=None):
    if visitados is None:
        visitados, orden = set(), []
    visitados.add(u)
    orden.append(u)                      # momento de DESCUBRIMIENTO
    for v in grafo[u]:
        if v not in visitados:
            dfs_recursivo(grafo, v, visitados, orden)
    return orden

print(dfs_recursivo(RED, "ALM"))
# ['ALM', 'RIO', 'CEN', 'MER', 'UNI', 'EST', 'IND', 'HOS', 'PAR']

Sigue el rastro: de ALM baja a RIO, de RIO a CEN, de CEN a MER, de MER a UNI, de UNI a EST, de EST a IND, de IND a HOS, de HOS a PAR. Un solo hilo que se hunde hasta el fondo; los retrocesos (por ejemplo, de PAR de vuelta hasta ALM) no visitan nada nuevo.

Versión iterativa con pila explícita (LIFO), imprescindible en grafos grandes donde la recursión desbordaría (el límite por defecto de Python ronda las 1.000 llamadas anidadas):

def dfs_iterativo(grafo, origen):
    visitados, orden = set(), []
    pila = [origen]
    while pila:
        u = pila.pop()                   # LIFO: sale el más reciente
        if u in visitados:
            continue                     # pudo entrar varias veces a la pila
        visitados.add(u)
        orden.append(u)
        # reversed() para imitar el orden de la versión recursiva
        for v in reversed(list(grafo[u])):
            if v not in visitados:
                pila.append(v)
    return orden

Diferencias sutiles que conviene interiorizar:

  • La única diferencia estructural con BFS es cola → pila. Ese cambio de estructura transforma la onda expansiva en un descenso en profundidad. (Adelanto: en 03-03, cambiar la pila por un heap dará Dijkstra. Toda esta familia de algoritmos es "la misma plantilla con distinta agenda".)
  • En la versión iterativa, un nodo puede estar varias veces en la pila; por eso se comprueba visitados al sacar, no al meter.
  • DFS no calcula distancias mínimas: el orden de descubrimiento depende del orden de los vecinos y puede llegar a un nodo por un camino larguísimo.

Tabla comparativa BFS vs DFS

BFS DFS
Estructura Cola (FIFO) Pila (LIFO) o recursión
Orden de visita Por niveles (cercanía) En profundidad (un hilo hasta el fondo)
Complejidad O(n + m) O(n + m)
Memoria en el peor caso O(n) (frontera ancha) O(n) (camino profundo)
Camino más corto sin pesos Sí (en aristas) No
Detección de ciclos Sí Sí (la formulación más cómoda en dirigidos)
Componentes conexas Sí Sí
Ordenación topológica Kahn (variante BFS) Orden de finalización invertido
Usos típicos en Rutalia Distancias en tramos, zonas alcanzables, capas de servicio Dependencias de tareas, detección de ciclos, backtracking

Detección de ciclos

En grafos no dirigidos: hay ciclo si durante la búsqueda encontramos un vecino ya visitado que no es el padre del nodo actual (el padre no cuenta: la arista de ida y vuelta no es un ciclo).

def tiene_ciclo_no_dirigido(grafo):
    visitados = set()
    def dfs(u, padre):
        visitados.add(u)
        for v in grafo[u]:
            if v not in visitados:
                if dfs(v, u):
                    return True
            elif v != padre:      # visitado y no es de donde venimos: ciclo
                return True
        return False
    return any(u not in visitados and dfs(u, None) for u in grafo)

print(tiene_ciclo_no_dirigido(RED))   # True (p.ej. ALM-MER-CEN-ALM)

En grafos dirigidos no basta "visitado antes": hay que distinguir si el nodo sigue en el camino actual. Se usan tres estados: blanco (sin visitar), gris (en curso, aún en la pila de recursión) y negro (terminado). Encontrar un vecino gris delata un ciclo dirigido:

def tiene_ciclo_dirigido(grafo):
    BLANCO, GRIS, NEGRO = 0, 1, 2
    color = {u: BLANCO for u in grafo}
    def dfs(u):
        color[u] = GRIS
        for v in grafo[u]:
            if color[v] == GRIS:              # arista hacia el camino actual
                return True
            if color[v] == BLANCO and dfs(v):
                return True
        color[u] = NEGRO
        return False
    return any(color[u] == BLANCO and dfs(u) for u in grafo)

Esto importa en Rutalia: si el plan de tareas del almacén tuviera un ciclo de dependencias ("cargar requiere etiquetar, etiquetar requiere cargar"), ningún orden de trabajo sería válido. Verificar que el grafo es un DAG es el paso previo a ordenarlo.

Componentes conexas: BFS frente al union-find de 01-04

Escenario Rutalia: unas obras cortan simultáneamente los tramos EST–IND y HOS–IND. ¿Queda alguna zona sin servicio? Basta lanzar BFS desde cada nodo aún no visitado; cada lanzamiento descubre una componente completa:

def componentes(grafo):
    visitados, comps = set(), []
    for inicio in grafo:
        if inicio in visitados:
            continue
        comp, cola = set(), deque([inicio])
        visitados.add(inicio)
        while cola:
            u = cola.popleft()
            comp.add(u)
            for v in grafo[u]:
                if v not in visitados:
                    visitados.add(v)
                    cola.append(v)
        comps.append(comp)
    return comps

recortada = {u: {v: p for v, p in vs.items()
                 if {u, v} not in [{"EST", "IND"}, {"HOS", "IND"}]}
             for u, vs in RED.items()}
print(componentes(recortada))
# [{'ALM','RIO','MER','EST','UNI','CEN','HOS','PAR'}, {'IND'}]

El Polígono Industrial queda aislado — coherente con lo que anticipamos en 03-01: con grado 2, era la zona más frágil.

¿Y el union-find de 01-04? Resuelve lo mismo: se recorre la lista de aristas haciendo union(u, v), y dos zonas están en la misma componente si find devuelve el mismo representante. Comparación honesta:

BFS/DFS Union-find
Coste O(n + m) una vez O(m · α(n)) ≈ lineal
Grafo estático Ideal Correcto pero sin ventaja
Aristas que se añaden en vivo Hay que relanzar la búsqueda Ideal: actualización O(α(n)) por arista
Aristas que se eliminan Relanzar También necesita reconstruir
Extras Da caminos, distancias, árbol Solo pertenencia a componente

Regla práctica: para una foto fija, BFS; para un grafo que crece arista a arista (exactamente lo que hará Kruskal en 03-04), union-find.

Ordenación topológica en DAGs: el algoritmo de Kahn

El almacén de Rutalia prepara cada furgoneta con tareas encadenadas: no se puede clasificar lo que no está escaneado ni cargar lo que no tiene ruta asignada. Modelamos cada dependencia como arista dirigida "antes → después":

graph LR
    recepcion --> escaneo
    escaneo --> clasificacion
    escaneo --> etiquetado
    clasificacion --> asignacion_ruta
    etiquetado --> carga
    asignacion_ruta --> carga
    carga --> salida

Una ordenación topológica es una lista de los nodos donde toda arista apunta hacia delante: un orden de ejecución válido. Solo existe si el grafo es un DAG. El algoritmo de Kahn es BFS con una idea extra: solo puede empezar una tarea cuyo grado de entrada pendiente sea 0.

from collections import deque

def kahn(grafo):
    entrada = {u: 0 for u in grafo}
    for u in grafo:
        for v in grafo[u]:
            entrada[v] += 1

    cola = deque(u for u in grafo if entrada[u] == 0)  # tareas listas ya
    orden = []
    while cola:
        u = cola.popleft()
        orden.append(u)
        for v in grafo[u]:
            entrada[v] -= 1          # u ya no bloquea a v
            if entrada[v] == 0:
                cola.append(v)       # v queda desbloqueada

    if len(orden) < len(grafo):      # quedaron nodos bloqueados entre sí
        raise ValueError("Hay un ciclo de dependencias: no existe orden válido")
    return orden

TAREAS = {
    "recepcion": ["escaneo"],
    "escaneo": ["clasificacion", "etiquetado"],
    "clasificacion": ["asignacion_ruta"],
    "etiquetado": ["carga"],
    "asignacion_ruta": ["carga"],
    "carga": ["salida"],
    "salida": [],
}
print(kahn(TAREAS))
# ['recepcion', 'escaneo', 'clasificacion', 'etiquetado',
#  'asignacion_ruta', 'carga', 'salida']

Dos detalles valiosos:

  • El orden no es único (clasificacion y etiquetado son intercambiables: son tareas paralelizables — información útil en sí misma para el jefe de almacén).
  • Kahn detecta ciclos gratis: si al terminar orden no contiene todos los nodos, los que faltan forman parte de (o dependen de) un ciclo. Es la versión "constructiva" del detector de ciclos gris/negro.

Aplicaciones en Rutalia: cortes de calle y excentricidad

Recapitulemos las dos preguntas operativas prometidas, ya con respuesta:

  • ¿Qué zonas quedan alcanzables si se corta una calle? Eliminar las aristas afectadas y relanzar BFS desde ALM: los nodos sin distancia asignada están incomunicados. Con el corte doble sobre IND vimos que el Polígono queda aislado; un corte simple (por ejemplo solo EST–IND) no aísla nada porque IND conserva la salida por HOS. Este análisis de robustez, sistematizado sobre grafos gigantes, reaparecerá en 06-02.
  • ¿A cuántos tramos está el punto de entrega más lejano? max(dist.values()) tras BFS desde ALM: 2 tramos (UNI, IND, PAR y HOS empatan). Es la excentricidad del almacén: útil para dimensionar "saltos" logísticos, pero engañosa como medida de tiempo — HOS está a 2 tramos y 16 minutos por ese camino, cuando existe uno de 13.

Esa grieta —tramos ≠ minutos— es exactamente lo que abre la puerta de la siguiente lección.

Errores Comunes y Consejos

  • Marcar visitado al desencolar en BFS: permite que un nodo entre en la cola muchas veces y, peor, puede asignarle una distancia incorrecta. En BFS se marca al encolar; en DFS iterativo, en cambio, lo cómodo es comprobar al sacar. No mezcles ambos patrones sin pensar.
  • Usar list.pop(0) como cola: desplaza toda la lista y convierte BFS en O(n·m). Usa collections.deque con popleft(), que es O(1).
  • Creer que BFS da el camino más rápido en minutos: da el mínimo en aristas. El ejemplo ALM→HOS (2 tramos/16 min frente a 3 tramos/13 min) debería vacunarte para siempre.
  • Recursión sin límite en DFS: un grafo-camino de 10.000 nodos revienta la pila de Python. Para producción, versión iterativa o sys.setrecursionlimit con mucho cuidado.
  • Detectar ciclos en dirigidos con un simple visitados: dos caminos distintos hacia el mismo nodo no son un ciclo. En dirigidos hacen falta los tres colores (o Kahn).
  • Consejo: cuando depures una búsqueda, imprime la cola/pila en cada iteración con un grafo de 5 nodos. El "vídeo mental" de cómo avanza la frontera vale más que cualquier definición.

Ejercicios

  1. Zonas por capas de servicio. Rutalia quiere agrupar las zonas por "anillos" de cercanía al almacén: anillo 0 = ALM, anillo 1 = a un tramo, etc. Escribe anillos(grafo, origen) que devuelva una lista de conjuntos, uno por nivel BFS, y aplícala a la red canónica.
  2. ¿Corte crítico? Escribe es_critica(grafo, u, v) que indique si eliminar la arista {u, v} desconecta el grafo (pista: quítala y compara el número de componentes). Encuentra todas las aristas críticas (puentes) de la red canónica probándolas una a una. ¿El resultado encaja con los grados que calculaste en 03-01?
  3. Plan de almacén con imprevisto. Añade al DAG de tareas la dependencia salida → recepcion (un error de configuración) y comprueba que kahn lanza la excepción. Después, escribe una variante kahn_paralelo(grafo) que devuelva las tareas agrupadas por "oleadas" ejecutables en paralelo (todas las desbloqueadas a la vez forman una oleada).

Soluciones

Ejercicio 1:

def anillos(grafo, origen):
    dist, _ = bfs(grafo, origen)
    niveles = [set() for _ in range(max(dist.values()) + 1)]
    for nodo, d in dist.items():
        niveles[d].add(nodo)
    return niveles

print(anillos(RED, "ALM"))
# [{'ALM'}, {'RIO', 'MER', 'EST', 'CEN'}, {'PAR', 'UNI', 'IND', 'HOS'}]

Reutilizamos bfs y solo reagrupamos por distancia: los anillos son las capas de la onda expansiva.

Ejercicio 2:

def sin_arista(grafo, u, v):
    return {a: {b: p for b, p in vs.items() if {a, b} != {u, v}}
            for a, vs in grafo.items()}

def es_critica(grafo, u, v):
    return len(componentes(sin_arista(grafo, u, v))) > len(componentes(grafo))

criticas = [(u, v) for u in RED for v in RED[u] if u < v and es_critica(RED, u, v)]
print(criticas)   # [] -> ninguna arista aislada desconecta la red

La red canónica no tiene puentes: toda zona tiene al menos dos salidas, así que ningún corte simple aísla nada (coherente con el ejercicio del corte doble sobre IND, que necesitó dos aristas). El filtro u < v evita examinar cada arista dos veces.

Ejercicio 3:

TAREAS_MAL = dict(TAREAS, salida=["recepcion"])
try:
    kahn(TAREAS_MAL)
except ValueError as e:
    print(e)   # Hay un ciclo de dependencias: no existe orden válido

def kahn_paralelo(grafo):
    entrada = {u: 0 for u in grafo}
    for u in grafo:
        for v in grafo[u]:
            entrada[v] += 1
    listos = [u for u in grafo if entrada[u] == 0]
    oleadas = []
    while listos:
        oleadas.append(listos)
        siguientes = []
        for u in listos:
            for v in grafo[u]:
                entrada[v] -= 1
                if entrada[v] == 0:
                    siguientes.append(v)
        listos = siguientes
    return oleadas

print(kahn_paralelo(TAREAS))
# [['recepcion'], ['escaneo'], ['clasificacion', 'etiquetado'],
#  ['asignacion_ruta'], ['carga'], ['salida']]

En lugar de una cola nodo a nodo, procesamos generaciones completas: cada oleada contiene tareas sin dependencias mutuas, ejecutables en paralelo. Nótese que etiquetado debe esperar a asignacion_ruta... no: espera solo a escaneo; quien espera a ambas ramas es carga. El DAG hace visible el paralelismo real del almacén.

Conclusión

BFS y DFS son la misma plantilla con distinta agenda: una cola produce una onda por niveles que da distancias mínimas en aristas y caminos reconstruibles con padre; una pila produce un descenso en profundidad ideal para ciclos, dependencias y backtracking. Con ellas hemos detectado ciclos (con tres colores en dirigidos), calculado componentes conexas (y delimitado cuándo conviene el union-find de 01-04), ordenado topológicamente las tareas del almacén con Kahn y respondido a los cortes de calle de Rutalia. Pero la lección deja una espina clavada: BFS jura que el Hospital está "a 2 tramos" por una avenida de 16 minutos, cuando hay un camino de 13. Contar aristas no basta cuando las aristas pesan. En 03-03 sustituiremos la cola por el heap que dejamos sembrado en 01-04 —es hora de cobrar esa semilla— y obtendremos Dijkstra, el algoritmo de caminos mínimos por excelencia, junto a Bellman-Ford y Floyd-Warshall.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados