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

Algoritmos de Búsqueda en Grafos

Siguiente ►
►

Esta es la lección donde el curso cobra todas sus deudas. En el módulo 5 prometimos que el patrón "¿lo he visto ya?" con set sería el visitados de BFS; en el módulo 6 dijimos que el recorrido por niveles con deque "es un BFS que saltará a grafos"; y desde el módulo 3 sabemos que toda recursión esconde una pila. Aquí convergen las tres piezas: BFS (búsqueda en anchura) y DFS (búsqueda en profundidad), los dos recorridos fundamentales sobre grafos. Con ellos responderemos preguntas reales de TaskFlow: qué tareas se desbloquean al terminar una, si el proyecto tiene ciclos de dependencias, y en qué orden ejecutar las tareas. Trabajamos sobre la clase Grafo y el grafo dependencias de la lección anterior.

Contenido

  1. Por qué visitados ahora es imprescindible
  2. BFS: búsqueda en anchura con deque
  3. Traza de BFS sobre el grafo de dependencias
  4. DFS: búsqueda en profundidad, recursiva e iterativa
  5. Traza de DFS y comparación BFS/DFS
  6. Aplicación 1: ¿qué desbloquea terminar una tarea? (alcanzables)
  7. Aplicación 2: detección de ciclos con estados blanco/gris/negro
  8. Aplicación 3: orden topológico (algoritmo de Kahn)
  9. Componentes conexas

Por qué visitados ahora es imprescindible

En el recorrido por niveles de un árbol (módulo 6) no llevábamos ningún conjunto de visitados. No hacía falta: en un árbol cada nodo tiene un solo padre, así que solo se puede llegar a él por un camino y es imposible encolarlo dos veces. Los grafos rompen esa garantía dos veces:

  • Varios padres: a desplegar_api se llega desde migrar_bd y desde configurar_servidor. Sin control, la procesaríamos dos veces (y todo lo que hay detrás, cuatro; crecimiento exponencial).
  • Ciclos: en A → B → C → A, un recorrido ingenuo no termina jamás.

La solución es el patrón del módulo 5: un set llamado visitados con pertenencia e inserción en O(1) medio. Regla de oro: marcar al encolar/apilar, no al desencolar — si esperas a marcar cuando procesas el vértice, puede colarse dos veces en la cola entre medias.

BFS: búsqueda en anchura con deque

BFS explora el grafo por capas de distancia: primero el origen (distancia 0), luego sus vecinos (distancia 1), luego los vecinos de estos (distancia 2)... Es literalmente el recorrido por niveles del módulo 6, con deque como cola (append por la derecha, popleft por la izquierda, ambos O(1), módulo 4), más el visitados:

from collections import deque

def bfs(grafo, origen):
    """Recorre el grafo desde origen por capas. Devuelve el orden de visita."""
    visitados = {origen}          # marcado YA, antes de entrar en la cola
    cola = deque([origen])
    orden = []
    while cola:
        actual = cola.popleft()   # FIFO: sale el más antiguo -> por capas
        orden.append(actual)
        for vecino in grafo.vecinos(actual):
            if vecino not in visitados:   # el "¿lo he visto ya?" del módulo 5
                visitados.add(vecino)     # marcar al encolar
                cola.append(vecino)
    return orden

Cada vértice entra en la cola como mucho una vez y cada arista se examina una vez: coste O(n + a) en tiempo y O(n) en espacio. Compáralo con el árbol del módulo 6: el código es casi idéntico; solo hemos añadido tres líneas de visitados. Esa es la continuidad prometida.

La propiedad estrella de BFS: como avanza por capas, la primera vez que alcanza un vértice lo hace por un camino con el mínimo número de aristas. En grafos no ponderados, BFS es el algoritmo de camino más corto (con pesos ya no bastará: lección 07-04).

Traza de BFS sobre el grafo de dependencias

Ejecutemos bfs(dependencias, "disenar_esquema") paso a paso:

graph LR
    A[disenar_esquema] --> B[migrar_bd]
    B --> C[desplegar_api]
    S[configurar_servidor] --> C
    C --> D[pruebas_integracion]
    U[disenar_ui] --> I[implementar_ui]
    I --> D
    D --> L[lanzamiento]
Paso Sale de la cola Vecinos nuevos que entran Cola tras el paso Visitados
1 disenar_esquema migrar_bd [migrar_bd] {d_e, mig}
2 migrar_bd desplegar_api [desplegar_api] + api
3 desplegar_api pruebas_integracion [pruebas_integracion] + pru
4 pruebas_integracion lanzamiento [lanzamiento] + lan
5 lanzamiento — [] —

Resultado: ['disenar_esquema', 'migrar_bd', 'desplegar_api', 'pruebas_integracion', 'lanzamiento']. Dos observaciones:

  • BFS solo visita lo alcanzable siguiendo las flechas: ni configurar_servidor, ni disenar_ui, ni implementar_ui aparecen, porque ninguna flecha lleva de disenar_esquema a ellas. En un grafo dirigido, "alcanzable" depende del origen.
  • Las capas son las distancias: migrar_bd a 1 arista, desplegar_api a 2, etc.

DFS: búsqueda en profundidad, recursiva e iterativa

DFS toma la decisión contraria: en lugar de agotar la capa actual, se lanza por un camino hasta el fondo y solo retrocede (backtracking) cuando no puede seguir. Versión recursiva, donde la "pila" es la pila de llamadas del módulo 3:

def dfs_recursivo(grafo, origen, visitados=None, orden=None):
    if visitados is None:
        visitados, orden = set(), []
    visitados.add(origen)
    orden.append(origen)
    for vecino in grafo.vecinos(origen):
        if vecino not in visitados:
            dfs_recursivo(grafo, vecino, visitados, orden)  # bajar un nivel
    return orden

Y la versión iterativa, aplicando la equivalencia recursión ↔ pila explícita del módulo 3 (útil cuando el grafo es profundo y la pila de llamadas de Python, limitada a ~1000 niveles, se queda corta):

def dfs_iterativo(grafo, origen):
    visitados = set()
    pila = [origen]               # una list como pila: append/pop por el final
    orden = []
    while pila:
        actual = pila.pop()       # LIFO: sale el más RECIENTE -> profundidad
        if actual in visitados:   # puede haber entrado dos veces antes de salir
            continue
        visitados.add(actual)
        orden.append(actual)
        for vecino in grafo.vecinos(actual):
            if vecino not in visitados:
                pila.append(vecino)
    return orden

Compara dfs_iterativo con bfs: son el mismo algoritmo cambiando la estructura de apoyo. Cola (FIFO) → anchura; pila (LIFO) → profundidad. Es la simetría pila↔DFS / cola↔BFS anunciada en el módulo 6, ahora en código real.

Traza de DFS y comparación BFS/DFS

dfs_recursivo(dependencias, "disenar_ui"): visita disenar_ui, baja a implementar_ui, baja a pruebas_integracion, baja a lanzamiento; sin vecinos nuevos, deshace llamadas hasta el origen. Resultado: ['disenar_ui', 'implementar_ui', 'pruebas_integracion', 'lanzamiento'] — un camino en picado, frente al avance por capas de BFS.

Criterio BFS DFS
Estructura de apoyo Cola (deque, módulo 4) Pila (llamadas o list, módulo 3)
Orden de exploración Por capas de distancia Un camino hasta el fondo, luego retrocede
Encuentra El camino con menos aristas Exploración exhaustiva; caminos, no necesariamente cortos
Memoria en el peor caso O(n) (una capa ancha) O(n) (un camino largo)
Coste en tiempo O(n + a) O(n + a)
Usos típicos Distancias, "a N pasos de", niveles Ciclos, orden topológico, backtracking

Aplicación 1: ¿qué desbloquea terminar una tarea? (alcanzables)

Pregunta de TaskFlow: "si termino migrar_bd, ¿qué tareas se acercan a su desbloqueo?" Con nuestra convención (la flecha apunta a lo que se desbloquea), son exactamente los vértices alcanzables desde ella — BFS y quitar el origen:

def tareas_afectadas(grafo, id_tarea):
    """Tareas que dependen, directa o transitivamente, de id_tarea."""
    return bfs(grafo, id_tarea)[1:]     # todo lo alcanzable, menos ella misma

print(tareas_afectadas(dependencias, "migrar_bd"))
# ['desplegar_api', 'pruebas_integracion', 'lanzamiento']

Retrasar migrar_bd retrasa potencialmente esas tres tareas: acabamos de implementar el análisis de impacto de un gestor de proyectos en cinco líneas.

Aplicación 2: detección de ciclos con estados blanco/gris/negro

En el módulo 2 detectamos ciclos en listas enlazadas con Floyd (dos punteros a distinta velocidad). Aquella técnica servía porque en una lista solo hay un camino posible; en un grafo con bifurcaciones necesitamos otra idea, pero el problema es el mismo: ¿puedo volver a un sitio donde ya estoy? La técnica clásica usa DFS con tres estados por vértice:

  • Blanco: no visitado aún.
  • Gris: en proceso — está en el camino actual de la recursión (en la pila de llamadas).
  • Negro: terminado — él y todos sus descendientes, explorados.

La clave: si DFS encuentra una arista hacia un vértice gris, ha encontrado una arista que vuelve al camino actual: un ciclo. Llegar a uno negro no es ciclo, solo un cruce de caminos (varios padres).

def hay_ciclo(grafo):
    BLANCO, GRIS, NEGRO = 0, 1, 2
    color = {v: BLANCO for v in grafo.vertices()}

    def visitar(v):
        color[v] = GRIS
        for vecino in grafo.vecinos(v):
            if color[vecino] == GRIS:      # arista hacia el camino actual
                return True
            if color[vecino] == BLANCO and visitar(vecino):
                return True
        color[v] = NEGRO                   # v cerrado: nada bajo él forma ciclo
        return False

    # el grafo puede no ser conexo: hay que intentar desde cada vértice blanco
    return any(color[v] == BLANCO and visitar(v) for v in grafo.vertices())

print(hay_ciclo(dependencias))    # False: nuestro proyecto es un DAG

# Rompámoslo a propósito: "disenar_ui depende de pruebas_integracion"
dependencias.anadir_arista("pruebas_integracion", "disenar_ui")
print(hay_ciclo(dependencias))    # True
dependencias.eliminar_arista("pruebas_integracion", "disenar_ui")  # ej. 2 de 07-02

Esto es exactamente lo que TaskFlow debe ejecutar antes de aceptar una nueva dependencia: si al añadirla hay_ciclo devuelve True, se rechaza y se avisa al usuario. En los ejercicios de 07-07 iremos más lejos: no solo detectar el ciclo, sino listarlo para mostrárselo.

Aplicación 3: orden topológico (algoritmo de Kahn)

La gran pregunta del proyecto: ¿en qué orden ejecuto las tareas de forma que ninguna empiece antes que sus dependencias? Ese orden se llama orden topológico y solo existe en DAGs. El algoritmo de Kahn lo construye con dos piezas que ya tenemos: los grados_entrada() de 07-02 y una cola:

  1. Calcula el grado de entrada de cada vértice.
  2. Mete en la cola los de grado 0 (ejecutables ya).
  3. Saca uno, añádelo al orden y "termínalo": resta 1 al grado de cada vecino. Si alguno llega a 0, a la cola.
  4. Repite hasta vaciar la cola.
def orden_topologico(grafo):
    grados = grafo.grados_entrada()
    cola = deque(v for v, g in grados.items() if g == 0)
    orden = []
    while cola:
        actual = cola.popleft()
        orden.append(actual)
        for vecino in grafo.vecinos(actual):
            grados[vecino] -= 1        # una dependencia menos
            if grados[vecino] == 0:    # todas cumplidas: ejecutable
                cola.append(vecino)
    if len(orden) < len(grados):       # quedaron vértices con grado > 0
        raise ValueError("Hay un ciclo de dependencias: no existe orden válido")
    return orden

print(orden_topologico(dependencias))
# ['disenar_esquema', 'configurar_servidor', 'disenar_ui', 'migrar_bd',
#  'implementar_ui', 'desplegar_api', 'pruebas_integracion', 'lanzamiento']

Detalles importantes:

  • Aquí no hay visitados: el propio contador de grados hace su papel — un vértice solo entra en la cola cuando su grado llega exactamente a 0, y eso ocurre una sola vez.
  • La comprobación final regala una segunda detección de ciclos: si hay ciclo, sus vértices nunca bajan a grado 0 y el orden sale incompleto. Kahn detecta ciclos "de propina", sin colores.
  • El orden no es único (los tres grados-0 iniciales podían salir en cualquier orden). En 07-07 desempataremos por prioridad sustituyendo la deque por el heapq del módulo 4.
  • Coste: O(n + a), como todo lo de hoy.

Componentes conexas

Última herramienta: detectar las "islas" del grafo. Para ello ignoramos el sentido de las flechas (dos tareas están relacionadas si comparten dependencias en cualquier dirección) y lanzamos BFS desde cada vértice aún sin visitar; cada lanzamiento descubre una componente entera:

def componentes_conexas(grafo):
    # versión no dirigida del grafo: cada arista, en ambos sentidos
    nd = Grafo(dirigido=False)
    for v in grafo.vertices():
        nd.anadir_vertice(v)
        for destino in grafo.vecinos(v):
            nd.anadir_arista(v, destino)

    visitados, componentes = set(), []
    for v in nd.vertices():
        if v not in visitados:
            comp = bfs(nd, v)              # descubre toda la isla de v
            visitados.update(comp)
            componentes.append(comp)
    return componentes

dependencias.anadir_arista("escribir_blog", "publicar_blog")  # mini-proyecto aparte
print(len(componentes_conexas(dependencias)))   # 2: el proyecto principal y el blog

En TaskFlow, cada componente es un subproyecto independiente: puede planificarse, asignarse y ejecutarse sin mirar a las demás. Volveremos sobre ello en los ejercicios (07-07) con "islas de tareas".

Errores Comunes y Consejos

  • Marcar como visitado al desencolar en lugar de al encolar. El algoritmo termina igual, pero un mismo vértice puede entrar varias veces en la cola y el coste se dispara. En BFS, marca al encolar; en DFS iterativo, el continue tras el pop cubre el caso equivalente.
  • Usar una list como cola en BFS (pop(0)): es O(n) por extracción, como machacamos en el módulo 4. deque.popleft() es O(1).
  • Detectar ciclos comprobando "vecino ya visitado" con un solo set. En grafos dirigidos, llegar a un vértice negro (terminado) por otro camino no es un ciclo, es un rombo de dependencias perfectamente legal. Sin el estado gris, darás falsos positivos.
  • Olvidar que el grafo puede no ser conexo. hay_ciclo y componentes_conexas iteran sobre todos los vértices; si solo lanzas desde uno, las islas quedan sin explorar.
  • DFS recursivo sobre grafos enormes: la pila de llamadas de Python se agota (~1000 niveles, módulo 3). Para grafos profundos, la versión iterativa.
  • Consejo: cuando dudes entre BFS y DFS, pregúntate qué buscas. ¿Distancias o "lo más cercano"? BFS. ¿Ciclos, órdenes, explorar todo sin importar el orden? DFS suele ser más natural.

Ejercicios

Ejercicio 1: BFS con distancias

Modifica bfs para que devuelva un dict vertice → distancia (número mínimo de aristas desde el origen). Úsalo para responder: ¿a cuántos "saltos" de disenar_esquema está lanzamiento?

Ejercicio 2: ¿de qué depende esta tarea?

tareas_afectadas mira hacia delante. Escribe prerequisitos(grafo, id_tarea) que devuelva todas las tareas de las que id_tarea depende, directa o transitivamente. Pista: o inviertes el grafo, o buscas desde cada vértice.

Ejercicio 3: traza de Kahn

Sin ejecutar código, traza el orden_topologico del grafo de dependencias en una tabla (cola, extraído, grados que cambian) y verifica que coincide con la salida mostrada en la lección.

Soluciones

Solución 1:

def bfs_distancias(grafo, origen):
    distancias = {origen: 0}          # hace también de visitados
    cola = deque([origen])
    while cola:
        actual = cola.popleft()
        for vecino in grafo.vecinos(actual):
            if vecino not in distancias:
                distancias[vecino] = distancias[actual] + 1
                cola.append(vecino)
    return distancias

print(bfs_distancias(dependencias, "disenar_esquema")["lanzamiento"])  # 4

El dict de distancias sustituye al set de visitados: estar en él ya significa "visto". lanzamiento está a 4 saltos, como en la traza.

Solución 2:

def invertir(grafo):
    inv = Grafo(dirigido=True)
    for v in grafo.vertices():
        inv.anadir_vertice(v)
        for destino, peso in grafo.vecinos(v).items():
            inv.anadir_arista(destino, v, peso)   # la flecha, del revés
    return inv

def prerequisitos(grafo, id_tarea):
    return bfs(invertir(grafo), id_tarea)[1:]

print(prerequisitos(dependencias, "desplegar_api"))
# ['migrar_bd', 'configurar_servidor', 'disenar_esquema']

Invertir el grafo cuesta O(n + a) y convierte "¿quién depende de mí?" en "¿de quién dependo?": el mismo BFS responde ambas preguntas según el sentido de las flechas.

Solución 3:

Paso Cola antes Extraído Grados que bajan Nuevos grado-0
1 [d_esquema, c_servidor, d_ui] disenar_esquema migrar_bd: 1→0 migrar_bd
2 [c_servidor, d_ui, migrar_bd] configurar_servidor desplegar_api: 2→1 —
3 [d_ui, migrar_bd] disenar_ui implementar_ui: 1→0 implementar_ui
4 [migrar_bd, implementar_ui] migrar_bd desplegar_api: 1→0 desplegar_api
5 [implementar_ui, desplegar_api] implementar_ui pruebas: 2→1 —
6 [desplegar_api] desplegar_api pruebas: 1→0 pruebas_integracion
7 [pruebas_integracion] pruebas_integracion lanzamiento: 1→0 lanzamiento
8 [lanzamiento] lanzamiento — —

Orden final: el de la lección. Observa cómo ninguna tarea sale antes de que todas sus dependencias hayan salido: esa es la garantía del orden topológico.

Conclusión

BFS y DFS son los dos motores de exploración de grafos: misma maquinaria, distinta estructura de apoyo (cola → capas y distancias mínimas en aristas; pila → profundidad, ciclos y órdenes), ambos en O(n + a) gracias al visitados que el módulo 5 dejó preparado. Sobre ellos hemos construido las tres operaciones que TaskFlow necesitaba: análisis de impacto (alcanzables), rechazo de dependencias circulares (blanco/gris/negro, la hermana grafo de Floyd) y el orden de ejecución del proyecto (Kahn). Pero BFS mide caminos en número de aristas, y en la vida real las aristas no cuestan lo mismo: pasar por una tarea de 8 horas no es como pasar por una de 1. Cuando las aristas tienen peso, hace falta algo mejor — y ese algo, Dijkstra, reutiliza la cola de prioridad heapq del módulo 4. Es la próxima lección.

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